From aea8fa357b06123d1e76590803be3e2d4dca1a8d Mon Sep 17 00:00:00 2001 From: Larry Hastings Date: Mon, 25 May 2015 13:05:48 -0700 Subject: Added a section for news items for 3.6. --- Misc/NEWS | 12 ++++++++++++ 1 file changed, 12 insertions(+) diff --git a/Misc/NEWS b/Misc/NEWS index a50d0d9..a6d0dc2 100644 --- a/Misc/NEWS +++ b/Misc/NEWS @@ -2,6 +2,18 @@ Python News +++++++++++ +What's New in Python 3.6.0 alpha 1? +=================================== + +Release date: XXXX-XX-XX + +Core and Builtins +----------------- + +Library +------- + + What's New in Python 3.5.0 beta 2? ================================== -- cgit v0.12 From d0c2a20b24a1317343620c0f4e318733745b97df Mon Sep 17 00:00:00 2001 From: Larry Hastings Date: Mon, 25 May 2015 16:49:01 -0700 Subject: Version bump for trunk to 3.6.0a0. Welcome to the future! --- Include/patchlevel.h | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-) diff --git a/Include/patchlevel.h b/Include/patchlevel.h index b5cac68..246eba8 100644 --- a/Include/patchlevel.h +++ b/Include/patchlevel.h @@ -17,13 +17,13 @@ /* Version parsed out into numeric values */ /*--start constants--*/ #define PY_MAJOR_VERSION 3 -#define PY_MINOR_VERSION 5 +#define PY_MINOR_VERSION 6 #define PY_MICRO_VERSION 0 -#define PY_RELEASE_LEVEL PY_RELEASE_LEVEL_BETA -#define PY_RELEASE_SERIAL 1 +#define PY_RELEASE_LEVEL PY_RELEASE_LEVEL_ALPHA +#define PY_RELEASE_SERIAL 0 /* Version as a string */ -#define PY_VERSION "3.5.0b1+" +#define PY_VERSION "3.6.0a0" /*--end constants--*/ /* Version as a single 4-byte hex number, e.g. 0x010502B2 == 1.5.2b2. -- cgit v0.12 From c074e9d765505df971fc89e21d512b40f85e1d6b Mon Sep 17 00:00:00 2001 From: Raymond Hettinger Date: Tue, 26 May 2015 01:47:58 -0700 Subject: Issue #24286: Forward port dict view abstract base class tests. --- Lib/test/test_collections.py | 7 +++++++ Lib/test/test_dictviews.py | 22 ++++++++++++++++++++++ 2 files changed, 29 insertions(+) diff --git a/Lib/test/test_collections.py b/Lib/test/test_collections.py index ec86466..ac7b9af 100644 --- a/Lib/test/test_collections.py +++ b/Lib/test/test_collections.py @@ -1867,6 +1867,13 @@ class TestOrderedDict(unittest.TestCase): od = OrderedDict(**d) self.assertGreater(sys.getsizeof(od), sys.getsizeof(d)) + def test_views(self): + # See http://bugs.python.org/issue24286 + s = 'the quick brown fox jumped over a lazy dog yesterday before dawn'.split() + od = OrderedDict.fromkeys(s) + self.assertEqual(od.keys(), dict(od).keys()) + self.assertEqual(od.items(), dict(od).items()) + def test_override_update(self): # Verify that subclasses can override update() without breaking __init__() class MyOD(OrderedDict): diff --git a/Lib/test/test_dictviews.py b/Lib/test/test_dictviews.py index 280353a..d96832e 100644 --- a/Lib/test/test_dictviews.py +++ b/Lib/test/test_dictviews.py @@ -1,3 +1,4 @@ +import collections import unittest class DictSetTest(unittest.TestCase): @@ -197,6 +198,27 @@ class DictSetTest(unittest.TestCase): d[42] = d.values() self.assertRaises(RuntimeError, repr, d) + def test_abc_registry(self): + d = dict(a=1) + + self.assertIsInstance(d.keys(), collections.KeysView) + self.assertIsInstance(d.keys(), collections.MappingView) + self.assertIsInstance(d.keys(), collections.Set) + self.assertIsInstance(d.keys(), collections.Sized) + self.assertIsInstance(d.keys(), collections.Iterable) + self.assertIsInstance(d.keys(), collections.Container) + + self.assertIsInstance(d.values(), collections.ValuesView) + self.assertIsInstance(d.values(), collections.MappingView) + self.assertIsInstance(d.values(), collections.Sized) + + self.assertIsInstance(d.items(), collections.ItemsView) + self.assertIsInstance(d.items(), collections.MappingView) + self.assertIsInstance(d.items(), collections.Set) + self.assertIsInstance(d.items(), collections.Sized) + self.assertIsInstance(d.items(), collections.Iterable) + self.assertIsInstance(d.items(), collections.Container) + if __name__ == "__main__": unittest.main() -- cgit v0.12 From 944db38cb720b511aad5d7850dec71402e7e2725 Mon Sep 17 00:00:00 2001 From: Raymond Hettinger Date: Tue, 26 May 2015 10:35:15 -0700 Subject: Issue #23509: Speed up Counter operators (Based on patch by Serhiy Storchaka.) --- Lib/collections/__init__.py | 12 ++++++++++-- 1 file changed, 10 insertions(+), 2 deletions(-) diff --git a/Lib/collections/__init__.py b/Lib/collections/__init__.py index fc60e13..9c22d86 100644 --- a/Lib/collections/__init__.py +++ b/Lib/collections/__init__.py @@ -736,14 +736,22 @@ class Counter(dict): def __pos__(self): 'Adds an empty counter, effectively stripping negative and zero counts' - return self + Counter() + result = Counter() + for elem, count in self.items(): + if count > 0: + result[elem] = count + return result def __neg__(self): '''Subtracts from an empty counter. Strips positive and zero counts, and flips the sign on negative counts. ''' - return Counter() - self + result = Counter() + for elem, count in self.items(): + if count < 0: + result[elem] = 0 - count + return result def _keep_positive(self): '''Internal method to strip elements with a negative or zero count''' -- cgit v0.12 From 8651a504752f3265817d0fa5def1b83994888821 Mon Sep 17 00:00:00 2001 From: Raymond Hettinger Date: Wed, 27 May 2015 10:37:20 -0700 Subject: Issue #23359: Specialize set_lookkey intoa lookup function and an insert function. --- Misc/NEWS | 3 ++ Objects/setobject.c | 145 +++++++++++++++++++++++++++++++++++++--------------- 2 files changed, 107 insertions(+), 41 deletions(-) diff --git a/Misc/NEWS b/Misc/NEWS index a01c238..b712b4d 100644 --- a/Misc/NEWS +++ b/Misc/NEWS @@ -42,6 +42,9 @@ Core and Builtins - Issue #24268: PEP 489: Multi-phase extension module initialization. Patch by Petr Viktorin. +- Issue #23359: Optimize set object internals by specializing the + hash table search into a lookup function and an insert function. + - Issue #23955: Add pyvenv.cfg option to suppress registry/environment lookup for generating sys.path on Windows. diff --git a/Objects/setobject.c b/Objects/setobject.c index 1805deb..e1aa417 100644 --- a/Objects/setobject.c +++ b/Objects/setobject.c @@ -52,7 +52,6 @@ static setentry * set_lookkey(PySetObject *so, PyObject *key, Py_hash_t hash) { setentry *table = so->table; - setentry *freeslot = NULL; setentry *entry; size_t perturb = hash; size_t mask = so->mask; @@ -86,14 +85,12 @@ set_lookkey(PySetObject *so, PyObject *key, Py_hash_t hash) return entry; mask = so->mask; /* help avoid a register spill */ } - if (entry->hash == -1 && freeslot == NULL) - freeslot = entry; if (i + LINEAR_PROBES <= mask) { for (j = 0 ; j < LINEAR_PROBES ; j++) { entry++; - if (entry->key == NULL) - goto found_null; + if (entry->hash == 0 && entry->key == NULL) + return entry; if (entry->hash == hash) { PyObject *startkey = entry->key; assert(startkey != dummy); @@ -114,6 +111,89 @@ set_lookkey(PySetObject *so, PyObject *key, Py_hash_t hash) return entry; mask = so->mask; } + } + } + + perturb >>= PERTURB_SHIFT; + i = (i * 5 + 1 + perturb) & mask; + + entry = &table[i]; + if (entry->hash == 0 && entry->key == NULL) + return entry; + } +} + +/* +Internal routine to insert a new key into the table. +Used by the public insert routine. +Eats a reference to key. +*/ +static int +set_insert_key(PySetObject *so, PyObject *key, Py_hash_t hash) +{ + setentry *table = so->table; + setentry *freeslot = NULL; + setentry *entry; + size_t perturb = hash; + size_t mask = so->mask; + size_t i = (size_t)hash & mask; /* Unsigned for defined overflow behavior */ + size_t j; + int cmp; + + entry = &table[i]; + if (entry->key == NULL) + goto found_null; + + while (1) { + if (entry->hash == hash) { + PyObject *startkey = entry->key; + /* startkey cannot be a dummy because the dummy hash field is -1 */ + assert(startkey != dummy); + if (startkey == key) + goto found_active; + if (PyUnicode_CheckExact(startkey) + && PyUnicode_CheckExact(key) + && unicode_eq(startkey, key)) + goto found_active; + Py_INCREF(startkey); + cmp = PyObject_RichCompareBool(startkey, key, Py_EQ); + Py_DECREF(startkey); + if (cmp < 0) /* unlikely */ + return -1; + if (table != so->table || entry->key != startkey) /* unlikely */ + return set_insert_key(so, key, hash); + if (cmp > 0) /* likely */ + goto found_active; + mask = so->mask; /* help avoid a register spill */ + } + if (entry->hash == -1 && freeslot == NULL) + freeslot = entry; + + if (i + LINEAR_PROBES <= mask) { + for (j = 0 ; j < LINEAR_PROBES ; j++) { + entry++; + if (entry->hash == 0 && entry->key == NULL) + goto found_null; + if (entry->hash == hash) { + PyObject *startkey = entry->key; + assert(startkey != dummy); + if (startkey == key) + goto found_active; + if (PyUnicode_CheckExact(startkey) + && PyUnicode_CheckExact(key) + && unicode_eq(startkey, key)) + goto found_active; + Py_INCREF(startkey); + cmp = PyObject_RichCompareBool(startkey, key, Py_EQ); + Py_DECREF(startkey); + if (cmp < 0) + return -1; + if (table != so->table || entry->key != startkey) + return set_insert_key(so, key, hash); + if (cmp > 0) + goto found_active; + mask = so->mask; + } if (entry->hash == -1 && freeslot == NULL) freeslot = entry; } @@ -123,11 +203,26 @@ set_lookkey(PySetObject *so, PyObject *key, Py_hash_t hash) i = (i * 5 + 1 + perturb) & mask; entry = &table[i]; - if (entry->key == NULL) + if (entry->hash == 0 && entry->key == NULL) goto found_null; } + found_null: - return freeslot == NULL ? entry : freeslot; + if (freeslot == NULL) { + /* UNUSED */ + so->fill++; + } else { + /* DUMMY */ + entry = freeslot; + } + so->used++; + entry->key = key; + entry->hash = hash; + return 0; + + found_active: + Py_DECREF(key); + return 0; } /* @@ -172,38 +267,6 @@ set_insert_clean(PySetObject *so, PyObject *key, Py_hash_t hash) /* ======== End logic for probing the hash table ========================== */ /* ======================================================================== */ - -/* -Internal routine to insert a new key into the table. -Used by the public insert routine. -Eats a reference to key. -*/ -static int -set_insert_key(PySetObject *so, PyObject *key, Py_hash_t hash) -{ - setentry *entry; - - entry = set_lookkey(so, key, hash); - if (entry == NULL) - return -1; - if (entry->key == NULL) { - /* UNUSED */ - entry->key = key; - entry->hash = hash; - so->fill++; - so->used++; - } else if (entry->key == dummy) { - /* DUMMY */ - entry->key = key; - entry->hash = hash; - so->used++; - } else { - /* ACTIVE */ - Py_DECREF(key); - } - return 0; -} - /* Restructure the table by allocating a new table and reinserting all keys again. When entries have been deleted, the new table may @@ -345,7 +408,7 @@ set_discard_entry(PySetObject *so, setentry *oldentry) entry = set_lookkey(so, oldentry->key, oldentry->hash); if (entry == NULL) return -1; - if (entry->key == NULL || entry->key == dummy) + if (entry->key == NULL) return DISCARD_NOTFOUND; old_key = entry->key; entry->key = dummy; @@ -623,7 +686,7 @@ set_contains_entry(PySetObject *so, setentry *entry) if (lu_entry == NULL) return -1; key = lu_entry->key; - return key != NULL && key != dummy; + return key != NULL; } static int -- cgit v0.12 From d1da50777498a50ef4e6866c24a6c7e1c469976c Mon Sep 17 00:00:00 2001 From: Yury Selivanov Date: Wed, 27 May 2015 22:09:10 -0400 Subject: Add whatsnew for 3.6 --- Doc/whatsnew/3.6.rst | 158 +++++++++++++++++++++++++++++++++++++++++++++++++ Doc/whatsnew/index.rst | 1 + 2 files changed, 159 insertions(+) create mode 100644 Doc/whatsnew/3.6.rst diff --git a/Doc/whatsnew/3.6.rst b/Doc/whatsnew/3.6.rst new file mode 100644 index 0000000..7453bf4 --- /dev/null +++ b/Doc/whatsnew/3.6.rst @@ -0,0 +1,158 @@ +**************************** + What's New In Python 3.6 +**************************** + +:Release: |release| +:Date: |today| + +.. Rules for maintenance: + + * Anyone can add text to this document. Do not spend very much time + on the wording of your changes, because your text will probably + get rewritten to some degree. + + * The maintainer will go through Misc/NEWS periodically and add + changes; it's therefore more important to add your changes to + Misc/NEWS than to this file. + + * This is not a complete list of every single change; completeness + is the purpose of Misc/NEWS. Some changes I consider too small + or esoteric to include. If such a change is added to the text, + I'll just remove it. (This is another reason you shouldn't spend + too much time on writing your addition.) + + * If you want to draw your new text to the attention of the + maintainer, add 'XXX' to the beginning of the paragraph or + section. + + * It's OK to just add a fragmentary note about a change. For + example: "XXX Describe the transmogrify() function added to the + socket module." The maintainer will research the change and + write the necessary text. + + * You can comment out your additions if you like, but it's not + necessary (especially when a final release is some months away). + + * Credit the author of a patch or bugfix. Just the name is + sufficient; the e-mail address isn't necessary. + + * It's helpful to add the bug/patch number as a comment: + + XXX Describe the transmogrify() function added to the socket + module. + (Contributed by P.Y. Developer in :issue:`12345`.) + + This saves the maintainer the effort of going through the Mercurial log + when researching a change. + +This article explains the new features in Python 3.6, compared to 3.5. + +For full details, see the :source:`Misc/NEWS` file. + +.. note:: + + Prerelease users should be aware that this document is currently in draft + form. It will be updated substantially as Python 3.6 moves towards release, + so it's worth checking back even after reading earlier versions. + + +Summary -- Release highlights +============================= + +.. This section singles out the most important changes in Python 3.6. + Brevity is key. + +* None yet. + +.. PEP-sized items next. + +.. _pep-4XX: + +.. PEP 4XX: Virtual Environments +.. ============================= + + +.. (Implemented by Foo Bar.) + +.. .. seealso:: + + :pep:`4XX` - Python Virtual Environments + PEP written by Carl Meyer + + +Other Language Changes +====================== + +* None yet. + + +New Modules +=========== + +* None yet. + + +Improved Modules +================ + +* None yet. + + +Optimizations +============= + +* None yet. + + +Build and C API Changes +======================= + +* None yet. + + +Deprecated +========== + +Deprecated Python modules, functions and methods +------------------------------------------------ + +* None yet. + + +Deprecated functions and types of the C API +------------------------------------------- + +* None yet. + + +Deprecated features +------------------- + +* None yet. + + +Removed +======= + +API and Feature Removals +------------------------ + +* None yet. + + +Porting to Python 3.6 +===================== + +This section lists previously described changes and other bugfixes +that may require changes to your code. + +Changes in the Python API +------------------------- + +* None yet. + + +Changes in the C API +-------------------- + +* None yet. diff --git a/Doc/whatsnew/index.rst b/Doc/whatsnew/index.rst index edb5502..7c92524 100644 --- a/Doc/whatsnew/index.rst +++ b/Doc/whatsnew/index.rst @@ -11,6 +11,7 @@ anyone wishing to stay up-to-date after a new release. .. toctree:: :maxdepth: 2 + 3.6.rst 3.5.rst 3.4.rst 3.3.rst -- cgit v0.12 From a8c22a0c323a330eddd3c1f1316aa01e77480474 Mon Sep 17 00:00:00 2001 From: Benjamin Peterson Date: Wed, 27 May 2015 23:29:00 -0500 Subject: update configure version to 3.6 --- configure | 20 ++++++++++---------- configure.ac | 2 +- 2 files changed, 11 insertions(+), 11 deletions(-) diff --git a/configure b/configure index b6bcbbe..8a8f683 100755 --- a/configure +++ b/configure @@ -1,6 +1,6 @@ #! /bin/sh # Guess values for system-dependent variables and create Makefiles. -# Generated by GNU Autoconf 2.69 for python 3.5. +# Generated by GNU Autoconf 2.69 for python 3.6. # # Report bugs to . # @@ -580,8 +580,8 @@ MAKEFLAGS= # Identity of this package. PACKAGE_NAME='python' PACKAGE_TARNAME='python' -PACKAGE_VERSION='3.5' -PACKAGE_STRING='python 3.5' +PACKAGE_VERSION='3.6' +PACKAGE_STRING='python 3.6' PACKAGE_BUGREPORT='http://bugs.python.org/' PACKAGE_URL='' @@ -1378,7 +1378,7 @@ if test "$ac_init_help" = "long"; then # Omit some internal or obsolete options to make the list less imposing. # This message is too long to be a string in the A/UX 3.1 sh. cat <<_ACEOF -\`configure' configures python 3.5 to adapt to many kinds of systems. +\`configure' configures python 3.6 to adapt to many kinds of systems. Usage: $0 [OPTION]... [VAR=VALUE]... @@ -1443,7 +1443,7 @@ fi if test -n "$ac_init_help"; then case $ac_init_help in - short | recursive ) echo "Configuration of python 3.5:";; + short | recursive ) echo "Configuration of python 3.6:";; esac cat <<\_ACEOF @@ -1597,7 +1597,7 @@ fi test -n "$ac_init_help" && exit $ac_status if $ac_init_version; then cat <<\_ACEOF -python configure 3.5 +python configure 3.6 generated by GNU Autoconf 2.69 Copyright (C) 2012 Free Software Foundation, Inc. @@ -2436,7 +2436,7 @@ cat >config.log <<_ACEOF This file contains any messages produced by compilers while running configure, to aid debugging if configure makes a mistake. -It was created by python $as_me 3.5, which was +It was created by python $as_me 3.6, which was generated by GNU Autoconf 2.69. Invocation command line was $ $0 $@ @@ -3009,7 +3009,7 @@ rm confdefs.h mv confdefs.h.new confdefs.h -VERSION=3.5 +VERSION=3.6 # Version number of Python's own shared library file. @@ -16540,7 +16540,7 @@ cat >>$CONFIG_STATUS <<\_ACEOF || ac_write_fail=1 # report actual input values of CONFIG_FILES etc. instead of their # values after options handling. ac_log=" -This file was extended by python $as_me 3.5, which was +This file was extended by python $as_me 3.6, which was generated by GNU Autoconf 2.69. Invocation command line was CONFIG_FILES = $CONFIG_FILES @@ -16602,7 +16602,7 @@ _ACEOF cat >>$CONFIG_STATUS <<_ACEOF || ac_write_fail=1 ac_cs_config="`$as_echo "$ac_configure_args" | sed 's/^ //; s/[\\""\`\$]/\\\\&/g'`" ac_cs_version="\\ -python config.status 3.5 +python config.status 3.6 configured by $0, generated by GNU Autoconf 2.69, with options \\"\$ac_cs_config\\" diff --git a/configure.ac b/configure.ac index 4030e33..3e9d31a 100644 --- a/configure.ac +++ b/configure.ac @@ -3,7 +3,7 @@ dnl * Please run autoreconf to test your changes! * dnl *********************************************** # Set VERSION so we only need to edit in one place (i.e., here) -m4_define(PYTHON_VERSION, 3.5) +m4_define(PYTHON_VERSION, 3.6) AC_PREREQ(2.65) -- cgit v0.12 From ffb40e5ec376aa755e92edb00c7db361f3007b6c Mon Sep 17 00:00:00 2001 From: Ned Deily Date: Wed, 27 May 2015 22:00:46 -0700 Subject: More version bumping to 3.6. With the creation of the 3.5 branch earlier in the process, it is necessary to do some of the version bumps now rather than at final release time (for example, the equivalent of the 3.4->3.5 bumps in f2bf12fa22c1). (Some of those changes have already been made, for example in 30f5e7ec6afe.) --- Doc/tutorial/interpreter.rst | 14 +++++++------- Doc/tutorial/stdlib.rst | 2 +- Doc/tutorial/stdlib2.rst | 2 +- README | 16 ++++++++-------- 4 files changed, 17 insertions(+), 17 deletions(-) diff --git a/Doc/tutorial/interpreter.rst b/Doc/tutorial/interpreter.rst index d5789a6..db0be32 100644 --- a/Doc/tutorial/interpreter.rst +++ b/Doc/tutorial/interpreter.rst @@ -1,4 +1,4 @@ -.. _tut-using: +3.6.. _tut-using: **************************** Using the Python Interpreter @@ -10,13 +10,13 @@ Using the Python Interpreter Invoking the Interpreter ======================== -The Python interpreter is usually installed as :file:`/usr/local/bin/python3.5` +The Python interpreter is usually installed as :file:`/usr/local/bin/python3.6` on those machines where it is available; putting :file:`/usr/local/bin` in your Unix shell's search path makes it possible to start it by typing the command: .. code-block:: text - python3.5 + python3.6 to the shell. [#]_ Since the choice of the directory where the interpreter lives is an installation option, other places are possible; check with your local @@ -24,11 +24,11 @@ Python guru or system administrator. (E.g., :file:`/usr/local/python` is a popular alternative location.) On Windows machines, the Python installation is usually placed in -:file:`C:\\Python35`, though you can change this when you're running the +:file:`C:\\Python36`, though you can change this when you're running the installer. To add this directory to your path, you can type the following command into the command prompt in a DOS box:: - set path=%path%;C:\python35 + set path=%path%;C:\python36 Typing an end-of-file character (:kbd:`Control-D` on Unix, :kbd:`Control-Z` on Windows) at the primary prompt causes the interpreter to exit with a zero exit @@ -96,8 +96,8 @@ with the *secondary prompt*, by default three dots (``...``). The interpreter prints a welcome message stating its version number and a copyright notice before printing the first prompt:: - $ python3.5 - Python 3.5 (default, Sep 16 2015, 09:25:04) + $ python3.6 + Python 3.6 (default, Sep 16 2015, 09:25:04) [GCC 4.8.2] on linux Type "help", "copyright", "credits" or "license" for more information. >>> diff --git a/Doc/tutorial/stdlib.rst b/Doc/tutorial/stdlib.rst index 598859d..405d799 100644 --- a/Doc/tutorial/stdlib.rst +++ b/Doc/tutorial/stdlib.rst @@ -15,7 +15,7 @@ operating system:: >>> import os >>> os.getcwd() # Return the current working directory - 'C:\\Python35' + 'C:\\Python36' >>> os.chdir('/server/accesslogs') # Change current working directory >>> os.system('mkdir today') # Run the command mkdir in the system shell 0 diff --git a/Doc/tutorial/stdlib2.rst b/Doc/tutorial/stdlib2.rst index f7d2a0a..71194b0 100644 --- a/Doc/tutorial/stdlib2.rst +++ b/Doc/tutorial/stdlib2.rst @@ -277,7 +277,7 @@ applications include caching objects that are expensive to create:: Traceback (most recent call last): File "", line 1, in d['primary'] # entry was automatically removed - File "C:/python35/lib/weakref.py", line 46, in __getitem__ + File "C:/python36/lib/weakref.py", line 46, in __getitem__ o = self.data[key]() KeyError: 'primary' diff --git a/README b/README index 87430b7..04c282e 100644 --- a/README +++ b/README @@ -1,5 +1,5 @@ -This is Python version 3.5.0 beta 1 -=================================== +This is Python version 3.6.0 alpha 1 +==================================== Copyright (c) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012, 2013, 2014, 2015 Python Software Foundation. All rights reserved. @@ -50,9 +50,9 @@ What's New ---------- We try to have a comprehensive overview of the changes in the "What's New in -Python 3.5" document, found at +Python 3.6" document, found at - http://docs.python.org/3.5/whatsnew/3.5.html + http://docs.python.org/3.6/whatsnew/3.6.html For a more detailed change log, read Misc/NEWS (though this file, too, is incomplete, and also doesn't list anything merged in from the 2.7 release under @@ -65,9 +65,9 @@ entitled "Installing multiple versions". Documentation ------------- -Documentation for Python 3.5 is online, updated daily: +Documentation for Python 3.6 is online, updated daily: - http://docs.python.org/3.5/ + http://docs.python.org/3.6/ It can also be downloaded in many formats for faster access. The documentation is downloadable in HTML, PDF, and reStructuredText formats; the latter version @@ -92,7 +92,7 @@ backported versions of certain key Python 3.x features. A source-to-source translation tool, "2to3", can take care of the mundane task of converting large amounts of source code. It is not a complete solution but is complemented by the deprecation warnings in 2.6. See -http://docs.python.org/3.5/library/2to3.html for more information. +http://docs.python.org/3.6/library/2to3.html for more information. Testing @@ -130,7 +130,7 @@ same prefix you must decide which version (if any) is your "primary" version. Install that version using "make install". Install all other versions using "make altinstall". -For example, if you want to install Python 2.6, 2.7 and 3.5 with 2.7 being the +For example, if you want to install Python 2.6, 2.7 and 3.6 with 2.7 being the primary version, you would execute "make install" in your 2.7 build directory and "make altinstall" in the others. -- cgit v0.12 From 6e6883f11ae8d0beaed3bc32537b977236c40170 Mon Sep 17 00:00:00 2001 From: Serhiy Storchaka Date: Thu, 28 May 2015 20:45:29 +0300 Subject: Issue #24309: Removed Python 2 idioms. --- Lib/string.py | 9 ++------- 1 file changed, 2 insertions(+), 7 deletions(-) diff --git a/Lib/string.py b/Lib/string.py index f3365c6..e7b692d 100644 --- a/Lib/string.py +++ b/Lib/string.py @@ -112,10 +112,7 @@ class Template(metaclass=_TemplateMetaclass): # Check the most common path first. named = mo.group('named') or mo.group('braced') if named is not None: - val = mapping[named] - # We use this idiom instead of str() because the latter will - # fail if val is a Unicode containing non-ASCII characters. - return '%s' % (val,) + return str(mapping[named]) if mo.group('escaped') is not None: return self.delimiter if mo.group('invalid') is not None: @@ -142,9 +139,7 @@ class Template(metaclass=_TemplateMetaclass): named = mo.group('named') or mo.group('braced') if named is not None: try: - # We use this idiom instead of str() because the latter - # will fail if val is a Unicode containing non-ASCII - return '%s' % (mapping[named],) + return str(mapping[named]) except KeyError: return mo.group() if mo.group('escaped') is not None: -- cgit v0.12 From 26f7057b360431d5e75145033f3688029257efd1 Mon Sep 17 00:00:00 2001 From: Yury Selivanov Date: Thu, 28 May 2015 14:06:12 -0400 Subject: Issue 24297: Add a unittest that Lib/symbol.py is in sync with Grammar --- Lib/test/test_symbol.py | 45 +++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 45 insertions(+) create mode 100644 Lib/test/test_symbol.py diff --git a/Lib/test/test_symbol.py b/Lib/test/test_symbol.py new file mode 100644 index 0000000..4475bbc --- /dev/null +++ b/Lib/test/test_symbol.py @@ -0,0 +1,45 @@ +import unittest +from test import support +import filecmp +import os +import sys +import subprocess + + +SYMBOL_FILE = support.findfile('symbol.py') +GRAMMAR_FILE = os.path.join(os.path.dirname(__file__), + '..', '..', 'Include', 'graminit.h') +TEST_PY_FILE = 'symbol_test.py' + + +class TestSymbolGeneration(unittest.TestCase): + + def _copy_file_without_generated_symbols(self, source_file, dest_file): + with open(source_file, 'rb') as fp: + lines = fp.readlines() + nl = lines[0][len(lines[0].rstrip()):] + with open(dest_file, 'wb') as fp: + fp.writelines(lines[:lines.index(b"#--start constants--" + nl) + 1]) + fp.writelines(lines[lines.index(b"#--end constants--" + nl):]) + + def _generate_symbols(self, grammar_file, target_symbol_py_file): + proc = subprocess.Popen([sys.executable, + SYMBOL_FILE, + grammar_file, + target_symbol_py_file], stderr=subprocess.PIPE) + stderr = proc.communicate()[1] + return proc.returncode, stderr + + @unittest.skipIf(not os.path.exists(GRAMMAR_FILE), + 'test only works from source build directory') + def test_real_grammar_and_symbol_file(self): + self._copy_file_without_generated_symbols(SYMBOL_FILE, TEST_PY_FILE) + self.addCleanup(support.unlink, TEST_PY_FILE) + self.assertFalse(filecmp.cmp(SYMBOL_FILE, TEST_PY_FILE)) + self.assertEqual((0, b''), self._generate_symbols(GRAMMAR_FILE, + TEST_PY_FILE)) + self.assertTrue(filecmp.cmp(SYMBOL_FILE, TEST_PY_FILE)) + + +if __name__ == "__main__": + unittest.main() -- cgit v0.12 From 7a219110e6b9972a96e78e389e243c5cecfcfccc Mon Sep 17 00:00:00 2001 From: Yury Selivanov Date: Thu, 28 May 2015 17:10:29 -0400 Subject: docs/whatsnew/3.6: Mention that 'async' and 'await' will be keywords in 3.7 --- Doc/whatsnew/3.6.rst | 8 ++++++++ 1 file changed, 8 insertions(+) diff --git a/Doc/whatsnew/3.6.rst b/Doc/whatsnew/3.6.rst index 7453bf4..375d94e 100644 --- a/Doc/whatsnew/3.6.rst +++ b/Doc/whatsnew/3.6.rst @@ -113,6 +113,14 @@ Build and C API Changes Deprecated ========== +New Keywords +------------ + +``async`` and ``await`` are not recommended to be used as variable, class or +function names. Introduced by :pep:`492` in Python 3.5, they will become +proper keywords in Python 3.7. + + Deprecated Python modules, functions and methods ------------------------------------------------ -- cgit v0.12 From 41a6a625d488fee413427f9bf682c199dce97be7 Mon Sep 17 00:00:00 2001 From: Zachary Ware Date: Thu, 28 May 2015 17:30:03 -0500 Subject: Update Windows build for 3.6 --- PC/example_nt/example.vcproj | 4 +- PC/pyconfig.h | 4 +- PC/python3.def | 1402 +++++++++++++++++++++--------------------- PCbuild/prepare_ssl.bat | 4 +- 4 files changed, 707 insertions(+), 707 deletions(-) diff --git a/PC/example_nt/example.vcproj b/PC/example_nt/example.vcproj index d82f76e..958eb78 100644 --- a/PC/example_nt/example.vcproj +++ b/PC/example_nt/example.vcproj @@ -39,7 +39,7 @@ Date: Fri, 29 May 2015 22:21:39 -0600 Subject: Issue #16991: Add a C implementation of collections.OrderedDict. --- Include/Python.h | 1 + Include/dictobject.h | 15 +- Include/odictobject.h | 42 + Lib/collections/__init__.py | 21 +- Lib/test/test_collections.py | 202 +++- Makefile.pre.in | 1 + Misc/NEWS | 2 + Modules/_collectionsmodule.c | 3 + Objects/dict-common.h | 22 + Objects/dictobject.c | 337 +++--- Objects/object.c | 15 + Objects/odictobject.c | 2394 ++++++++++++++++++++++++++++++++++++++++++ 12 files changed, 2860 insertions(+), 195 deletions(-) create mode 100644 Include/odictobject.h create mode 100644 Objects/dict-common.h create mode 100644 Objects/odictobject.c diff --git a/Include/Python.h b/Include/Python.h index 46d2ece..858dbd1 100644 --- a/Include/Python.h +++ b/Include/Python.h @@ -85,6 +85,7 @@ #include "tupleobject.h" #include "listobject.h" #include "dictobject.h" +#include "odictobject.h" #include "enumobject.h" #include "setobject.h" #include "methodobject.h" diff --git a/Include/dictobject.h b/Include/dictobject.h index 1f4dedb..17262fe 100644 --- a/Include/dictobject.h +++ b/Include/dictobject.h @@ -27,6 +27,11 @@ typedef struct { PyObject **ma_values; } PyDictObject; +typedef struct { + PyObject_HEAD + PyDictObject *dv_dict; +} _PyDictViewObject; + #endif /* Py_LIMITED_API */ PyAPI_DATA(PyTypeObject) PyDict_Type; @@ -40,9 +45,9 @@ PyAPI_DATA(PyTypeObject) PyDictValues_Type; #define PyDict_Check(op) \ PyType_FastSubclass(Py_TYPE(op), Py_TPFLAGS_DICT_SUBCLASS) #define PyDict_CheckExact(op) (Py_TYPE(op) == &PyDict_Type) -#define PyDictKeys_Check(op) (Py_TYPE(op) == &PyDictKeys_Type) -#define PyDictItems_Check(op) (Py_TYPE(op) == &PyDictItems_Type) -#define PyDictValues_Check(op) (Py_TYPE(op) == &PyDictValues_Type) +#define PyDictKeys_Check(op) (PyObject_IsInstance(op, (PyObject *)&PyDictKeys_Type)) +#define PyDictItems_Check(op) (PyObject_IsInstance(op, (PyObject *)&PyDictItems_Type)) +#define PyDictValues_Check(op) (PyObject_IsInstance(op, (PyObject *)&PyDictValues_Type)) /* This excludes Values, since they are not sets. */ # define PyDictViewSet_Check(op) \ (PyDictKeys_Check(op) || PyDictItems_Check(op)) @@ -75,6 +80,7 @@ PyDictKeysObject *_PyDict_NewKeysForClass(void); PyAPI_FUNC(PyObject *) PyObject_GenericGetDict(PyObject *, void *); PyAPI_FUNC(int) _PyDict_Next( PyObject *mp, Py_ssize_t *pos, PyObject **key, PyObject **value, Py_hash_t *hash); +PyObject *_PyDictView_New(PyObject *, PyTypeObject *); #endif PyAPI_FUNC(PyObject *) PyDict_Keys(PyObject *mp); PyAPI_FUNC(PyObject *) PyDict_Values(PyObject *mp); @@ -88,6 +94,9 @@ PyAPI_FUNC(PyObject *) _PyDict_NewPresized(Py_ssize_t minused); PyAPI_FUNC(void) _PyDict_MaybeUntrack(PyObject *mp); PyAPI_FUNC(int) _PyDict_HasOnlyStringKeys(PyObject *mp); Py_ssize_t _PyDict_KeysSize(PyDictKeysObject *keys); +PyObject *_PyDict_SizeOf(PyDictObject *); +PyObject *_PyDict_Pop(PyDictObject *, PyObject *, PyObject *); +PyObject *_PyDict_FromKeys(PyObject *, PyObject *, PyObject *); #define _PyDict_HasSplitTable(d) ((d)->ma_values != NULL) PyAPI_FUNC(int) PyDict_ClearFreeList(void); diff --git a/Include/odictobject.h b/Include/odictobject.h new file mode 100644 index 0000000..a32fbc5 --- /dev/null +++ b/Include/odictobject.h @@ -0,0 +1,42 @@ +#ifndef Py_ODICTOBJECT_H +#define Py_ODICTOBJECT_H +#ifdef __cplusplus +extern "C" { +#endif + + +/* OrderedDict */ + +#ifndef Py_LIMITED_API + +typedef struct _odictobject PyODictObject; + +PyAPI_DATA(PyTypeObject) PyODict_Type; +PyAPI_DATA(PyTypeObject) PyODictIter_Type; +PyAPI_DATA(PyTypeObject) PyODictKeys_Type; +PyAPI_DATA(PyTypeObject) PyODictItems_Type; +PyAPI_DATA(PyTypeObject) PyODictValues_Type; + +#endif /* Py_LIMITED_API */ + +#define PyODict_Check(op) PyObject_IsInstance(op, (PyObject *)&PyODict_Type) +#define PyODict_CheckExact(op) (Py_TYPE(op) == &PyODict_Type) +#define PyODict_SIZE(op) ((PyDictObject *)op)->ma_used +#define PyODict_HasKey(od, key) (PyMapping_HasKey(PyObject *)od, key) + +PyAPI_FUNC(PyObject *) PyODict_New(void); +PyAPI_FUNC(int) PyODict_SetItem(PyObject *od, PyObject *key, PyObject *item); +PyAPI_FUNC(int) PyODict_DelItem(PyObject *od, PyObject *key); + +/* wrappers around PyDict* functions */ +#define PyODict_GetItem(od, key) PyDict_GetItem((PyObject *)od, key) +#define PyODict_Contains(od, key) PyDict_Contains((PyObject *)od, key) +#define PyODict_Size(od) PyDict_Size((PyObject *)od) +#define PyODict_GetItemString(od, key) \ + PyDict_GetItemString((PyObject *)od, key) +#define Py_ODict_GetItemId(od, key) _PyDict_GetItemId((PyObject *)od, key) + +#ifdef __cplusplus +} +#endif +#endif /* !Py_ODICTOBJECT_H */ diff --git a/Lib/collections/__init__.py b/Lib/collections/__init__.py index 9c22d86..80dc4f6 100644 --- a/Lib/collections/__init__.py +++ b/Lib/collections/__init__.py @@ -7,7 +7,6 @@ from _collections_abc import * import _collections_abc __all__ += _collections_abc.__all__ -from _collections import deque, defaultdict from operator import itemgetter as _itemgetter, eq as _eq from keyword import iskeyword as _iskeyword import sys as _sys @@ -16,7 +15,18 @@ from _weakref import proxy as _proxy from itertools import repeat as _repeat, chain as _chain, starmap as _starmap from reprlib import recursive_repr as _recursive_repr -MutableSequence.register(deque) +try: + from _collections import deque +except ImportError: + pass +else: + MutableSequence.register(deque) + +try: + from _collections import defaultdict +except ImportError: + pass + ################################################################################ ### OrderedDict @@ -264,6 +274,13 @@ class OrderedDict(dict): return dict.__eq__(self, other) +try: + from _collections import OrderedDict +except ImportError: + # Leave the pure Python version in place. + pass + + ################################################################################ ### namedtuple ################################################################################ diff --git a/Lib/test/test_collections.py b/Lib/test/test_collections.py index 58d2e9c..c6db13e 100644 --- a/Lib/test/test_collections.py +++ b/Lib/test/test_collections.py @@ -1,7 +1,8 @@ """Unit tests for collections.py.""" import unittest, doctest, operator -from test.support import TESTFN, forget, unlink +from test.support import TESTFN, forget, unlink, import_fresh_module +import contextlib import inspect from test import support from collections import namedtuple, Counter, OrderedDict, _count_elements @@ -1609,9 +1610,24 @@ class TestCounter(unittest.TestCase): ### OrderedDict ################################################################################ -class TestOrderedDict(unittest.TestCase): +py_coll = import_fresh_module('collections', blocked=['_collections']) +c_coll = import_fresh_module('collections', fresh=['_collections']) + + +@contextlib.contextmanager +def replaced_module(name, replacement): + original_module = sys.modules[name] + sys.modules[name] = replacement + try: + yield + finally: + sys.modules[name] = original_module + + +class OrderedDictTests: def test_init(self): + OrderedDict = self.module.OrderedDict with self.assertRaises(TypeError): OrderedDict([('a', 1), ('b', 2)], None) # too many args pairs = [('a', 1), ('b', 2), ('c', 3), ('d', 4), ('e', 5)] @@ -1635,6 +1651,7 @@ class TestOrderedDict(unittest.TestCase): [('a', 1), ('b', 2), ('c', 3), ('d', 4), ('e', 5), ('f', 6), ('g', 7)]) def test_update(self): + OrderedDict = self.module.OrderedDict with self.assertRaises(TypeError): OrderedDict().update([('a', 1), ('b', 2)], None) # too many args pairs = [('a', 1), ('b', 2), ('c', 3), ('d', 4), ('e', 5)] @@ -1675,11 +1692,17 @@ class TestOrderedDict(unittest.TestCase): self.assertRaises(TypeError, OrderedDict().update, (), ()) self.assertRaises(TypeError, OrderedDict.update) + self.assertRaises(TypeError, OrderedDict().update, 42) + self.assertRaises(TypeError, OrderedDict().update, (), ()) + self.assertRaises(TypeError, OrderedDict.update) + def test_abc(self): + OrderedDict = self.module.OrderedDict self.assertIsInstance(OrderedDict(), MutableMapping) self.assertTrue(issubclass(OrderedDict, MutableMapping)) def test_clear(self): + OrderedDict = self.module.OrderedDict pairs = [('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)] shuffle(pairs) od = OrderedDict(pairs) @@ -1688,6 +1711,7 @@ class TestOrderedDict(unittest.TestCase): self.assertEqual(len(od), 0) def test_delitem(self): + OrderedDict = self.module.OrderedDict pairs = [('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)] od = OrderedDict(pairs) del od['a'] @@ -1697,6 +1721,7 @@ class TestOrderedDict(unittest.TestCase): self.assertEqual(list(od.items()), pairs[:2] + pairs[3:]) def test_setitem(self): + OrderedDict = self.module.OrderedDict od = OrderedDict([('d', 1), ('b', 2), ('c', 3), ('a', 4), ('e', 5)]) od['c'] = 10 # existing element od['f'] = 20 # new element @@ -1704,6 +1729,7 @@ class TestOrderedDict(unittest.TestCase): [('d', 1), ('b', 2), ('c', 10), ('a', 4), ('e', 5), ('f', 20)]) def test_iterators(self): + OrderedDict = self.module.OrderedDict pairs = [('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)] shuffle(pairs) od = OrderedDict(pairs) @@ -1720,6 +1746,11 @@ class TestOrderedDict(unittest.TestCase): self.assertEqual(list(reversed(od.items())), list(reversed(pairs))) def test_detect_deletion_during_iteration(self): + # XXX This test should also work under cOrderedDict. + if self.module is c_coll: + raise unittest.SkipTest("only valid for pure Python OrderedDict") + + OrderedDict = self.module.OrderedDict od = OrderedDict.fromkeys('abc') it = iter(od) key = next(it) @@ -1729,7 +1760,21 @@ class TestOrderedDict(unittest.TestCase): # The only guarantee that the next() will not succeed next(it) + def test_sorted_iterators(self): + OrderedDict = self.module.OrderedDict + with self.assertRaises(TypeError): + OrderedDict([('a', 1), ('b', 2)], None) + pairs = [('a', 1), ('b', 2), ('c', 3), ('d', 4), ('e', 5)] + od = OrderedDict(pairs) + self.assertEqual(sorted(od), [t[0] for t in pairs]) + self.assertEqual(sorted(od.keys()), [t[0] for t in pairs]) + self.assertEqual(sorted(od.values()), [t[1] for t in pairs]) + self.assertEqual(sorted(od.items()), pairs) + self.assertEqual(sorted(reversed(od)), + sorted([t[0] for t in reversed(pairs)])) + def test_popitem(self): + OrderedDict = self.module.OrderedDict pairs = [('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)] shuffle(pairs) od = OrderedDict(pairs) @@ -1739,7 +1784,18 @@ class TestOrderedDict(unittest.TestCase): od.popitem() self.assertEqual(len(od), 0) + def test_popitem_last(self): + OrderedDict = self.module.OrderedDict + pairs = [(i, i) for i in range(30)] + + obj = OrderedDict(pairs) + for i in range(8): + obj.popitem(True) + obj.popitem(True) + self.assertEqual(len(obj), 21) + def test_pop(self): + OrderedDict = self.module.OrderedDict pairs = [('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)] shuffle(pairs) od = OrderedDict(pairs) @@ -1764,6 +1820,7 @@ class TestOrderedDict(unittest.TestCase): m.pop('a') def test_equality(self): + OrderedDict = self.module.OrderedDict pairs = [('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)] shuffle(pairs) od1 = OrderedDict(pairs) @@ -1779,6 +1836,7 @@ class TestOrderedDict(unittest.TestCase): self.assertNotEqual(od1, OrderedDict(pairs[:-1])) def test_copying(self): + OrderedDict = self.module.OrderedDict # Check that ordered dicts are copyable, deepcopyable, picklable, # and have a repr/eval round-trip pairs = [('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)] @@ -1787,12 +1845,17 @@ class TestOrderedDict(unittest.TestCase): msg = "\ncopy: %s\nod: %s" % (dup, od) self.assertIsNot(dup, od, msg) self.assertEqual(dup, od) + self.assertEqual(list(dup.items()), list(od.items())) + self.assertEqual(len(dup), len(od)) + self.assertEqual(type(dup), type(od)) check(od.copy()) check(copy.copy(od)) check(copy.deepcopy(od)) - for proto in range(pickle.HIGHEST_PROTOCOL + 1): - with self.subTest(proto=proto): - check(pickle.loads(pickle.dumps(od, proto))) + # pickle directly pulls the module, so we have to fake it + with replaced_module('collections', self.module): + for proto in range(pickle.HIGHEST_PROTOCOL + 1): + with self.subTest(proto=proto): + check(pickle.loads(pickle.dumps(od, proto))) check(eval(repr(od))) update_test = OrderedDict() update_test.update(od) @@ -1800,6 +1863,7 @@ class TestOrderedDict(unittest.TestCase): check(OrderedDict(od)) def test_yaml_linkage(self): + OrderedDict = self.module.OrderedDict # Verify that __reduce__ is setup in a way that supports PyYAML's dump() feature. # In yaml, lists are native but tuples are not. pairs = [('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)] @@ -1809,6 +1873,7 @@ class TestOrderedDict(unittest.TestCase): self.assertTrue(all(type(pair)==list for pair in od.__reduce__()[1])) def test_reduce_not_too_fat(self): + OrderedDict = self.module.OrderedDict # do not save instance dictionary if not needed pairs = [('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)] od = OrderedDict(pairs) @@ -1817,15 +1882,20 @@ class TestOrderedDict(unittest.TestCase): self.assertIsNotNone(od.__reduce__()[2]) def test_pickle_recursive(self): + OrderedDict = self.module.OrderedDict od = OrderedDict() od[1] = od - for proto in range(-1, pickle.HIGHEST_PROTOCOL + 1): - dup = pickle.loads(pickle.dumps(od, proto)) - self.assertIsNot(dup, od) - self.assertEqual(list(dup.keys()), [1]) - self.assertIs(dup[1], dup) + + # pickle directly pulls the module, so we have to fake it + with replaced_module('collections', self.module): + for proto in range(-1, pickle.HIGHEST_PROTOCOL + 1): + dup = pickle.loads(pickle.dumps(od, proto)) + self.assertIsNot(dup, od) + self.assertEqual(list(dup.keys()), [1]) + self.assertIs(dup[1], dup) def test_repr(self): + OrderedDict = self.module.OrderedDict od = OrderedDict([('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)]) self.assertEqual(repr(od), "OrderedDict([('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)])") @@ -1833,6 +1903,7 @@ class TestOrderedDict(unittest.TestCase): self.assertEqual(repr(OrderedDict()), "OrderedDict()") def test_repr_recursive(self): + OrderedDict = self.module.OrderedDict # See issue #9826 od = OrderedDict.fromkeys('abc') od['x'] = od @@ -1840,6 +1911,7 @@ class TestOrderedDict(unittest.TestCase): "OrderedDict([('a', None), ('b', None), ('c', None), ('x', ...)])") def test_setdefault(self): + OrderedDict = self.module.OrderedDict pairs = [('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)] shuffle(pairs) od = OrderedDict(pairs) @@ -1858,16 +1930,19 @@ class TestOrderedDict(unittest.TestCase): self.assertEqual(Missing().setdefault(5, 9), 9) def test_reinsert(self): + OrderedDict = self.module.OrderedDict # Given insert a, insert b, delete a, re-insert a, # verify that a is now later than b. od = OrderedDict() od['a'] = 1 od['b'] = 2 del od['a'] + self.assertEqual(list(od.items()), [('b', 2)]) od['a'] = 1 self.assertEqual(list(od.items()), [('b', 2), ('a', 1)]) def test_move_to_end(self): + OrderedDict = self.module.OrderedDict od = OrderedDict.fromkeys('abcde') self.assertEqual(list(od), list('abcde')) od.move_to_end('c') @@ -1880,14 +1955,18 @@ class TestOrderedDict(unittest.TestCase): self.assertEqual(list(od), list('cabde')) with self.assertRaises(KeyError): od.move_to_end('x') + with self.assertRaises(KeyError): + od.move_to_end('x', 0) def test_sizeof(self): + OrderedDict = self.module.OrderedDict # Wimpy test: Just verify the reported size is larger than a regular dict d = dict(a=1) od = OrderedDict(**d) self.assertGreater(sys.getsizeof(od), sys.getsizeof(d)) def test_views(self): + OrderedDict = self.module.OrderedDict # See http://bugs.python.org/issue24286 s = 'the quick brown fox jumped over a lazy dog yesterday before dawn'.split() od = OrderedDict.fromkeys(s) @@ -1895,6 +1974,7 @@ class TestOrderedDict(unittest.TestCase): self.assertEqual(od.items(), dict(od).items()) def test_override_update(self): + OrderedDict = self.module.OrderedDict # Verify that subclasses can override update() without breaking __init__() class MyOD(OrderedDict): def update(self, *args, **kwds): @@ -1902,18 +1982,101 @@ class TestOrderedDict(unittest.TestCase): items = [('a', 1), ('c', 3), ('b', 2)] self.assertEqual(list(MyOD(items).items()), items) -class GeneralMappingTests(mapping_tests.BasicTestMappingProtocol): - type2test = OrderedDict + +class PurePythonOrderedDictTests(OrderedDictTests, unittest.TestCase): + + module = py_coll + + +@unittest.skipUnless(c_coll, 'requires the C version of the collections module') +class CPythonOrderedDictTests(OrderedDictTests, unittest.TestCase): + + module = c_coll + + def test_delitem_hash_collision(self): + OrderedDict = self.module.OrderedDict + + class Key: + def __init__(self, hash): + self._hash = hash + self.value = str(id(self)) + def __hash__(self): + return self._hash + def __eq__(self, other): + try: + return self.value == other.value + except AttributeError: + return False + def __repr__(self): + return self.value + + def blocking_hash(hash): + # See the collision-handling in lookdict (in Objects/dictobject.c). + MINSIZE = 8 + i = (hash & MINSIZE-1) + return (i << 2) + i + hash + 1 + + COLLIDING = 1 + + key = Key(COLLIDING) + colliding = Key(COLLIDING) + blocking = Key(blocking_hash(COLLIDING)) + + od = OrderedDict() + od[key] = ... + od[blocking] = ... + od[colliding] = ... + od['after'] = ... + + del od[blocking] + del od[colliding] + self.assertEqual(list(od.items()), [(key, ...), ('after', ...)]) + + +class PurePythonGeneralMappingTests(mapping_tests.BasicTestMappingProtocol): + + @classmethod + def setUpClass(cls): + cls.type2test = py_coll.OrderedDict def test_popitem(self): d = self._empty_mapping() self.assertRaises(KeyError, d.popitem) -class MyOrderedDict(OrderedDict): - pass -class SubclassMappingTests(mapping_tests.BasicTestMappingProtocol): - type2test = MyOrderedDict +@unittest.skipUnless(c_coll, 'requires the C version of the collections module') +class CPythonGeneralMappingTests(mapping_tests.BasicTestMappingProtocol): + + @classmethod + def setUpClass(cls): + cls.type2test = c_coll.OrderedDict + + def test_popitem(self): + d = self._empty_mapping() + self.assertRaises(KeyError, d.popitem) + + +class PurePythonSubclassMappingTests(mapping_tests.BasicTestMappingProtocol): + + @classmethod + def setUpClass(cls): + class MyOrderedDict(py_coll.OrderedDict): + pass + cls.type2test = MyOrderedDict + + def test_popitem(self): + d = self._empty_mapping() + self.assertRaises(KeyError, d.popitem) + + +@unittest.skipUnless(c_coll, 'requires the C version of the collections module') +class CPythonSubclassMappingTests(mapping_tests.BasicTestMappingProtocol): + + @classmethod + def setUpClass(cls): + class MyOrderedDict(c_coll.OrderedDict): + pass + cls.type2test = MyOrderedDict def test_popitem(self): d = self._empty_mapping() @@ -1930,8 +2093,11 @@ def test_main(verbose=None): NamedTupleDocs = doctest.DocTestSuite(module=collections) test_classes = [TestNamedTuple, NamedTupleDocs, TestOneTrickPonyABCs, TestCollectionABCs, TestCounter, TestChainMap, - TestOrderedDict, GeneralMappingTests, SubclassMappingTests, - TestUserObjects] + PurePythonOrderedDictTests, CPythonOrderedDictTests, + PurePythonGeneralMappingTests, CPythonGeneralMappingTests, + PurePythonSubclassMappingTests, CPythonSubclassMappingTests, + TestUserObjects, + ] support.run_unittest(*test_classes) support.run_doctest(collections, verbose) diff --git a/Makefile.pre.in b/Makefile.pre.in index 5db048a..ce2c0aa2 100644 --- a/Makefile.pre.in +++ b/Makefile.pre.in @@ -437,6 +437,7 @@ OBJECT_OBJS= \ Objects/listobject.o \ Objects/longobject.o \ Objects/dictobject.o \ + Objects/odictobject.o \ Objects/memoryobject.o \ Objects/methodobject.o \ Objects/moduleobject.o \ diff --git a/Misc/NEWS b/Misc/NEWS index 4db77b4..a317511 100644 --- a/Misc/NEWS +++ b/Misc/NEWS @@ -35,6 +35,8 @@ Library - Issue #24326: Fixed audioop.ratecv() with non-default weightB argument. Original patch by David Moore. +- Issue #16991: Add a C implementation of OrderedDict. + What's New in Python 3.5.0 beta 1? ================================== diff --git a/Modules/_collectionsmodule.c b/Modules/_collectionsmodule.c index 2b70b2b..c1fd8b9 100644 --- a/Modules/_collectionsmodule.c +++ b/Modules/_collectionsmodule.c @@ -2263,6 +2263,9 @@ PyInit__collections(void) Py_INCREF(&defdict_type); PyModule_AddObject(m, "defaultdict", (PyObject *)&defdict_type); + Py_INCREF(&PyODict_Type); + PyModule_AddObject(m, "OrderedDict", (PyObject *)&PyODict_Type); + if (PyType_Ready(&dequeiter_type) < 0) return NULL; Py_INCREF(&dequeiter_type); diff --git a/Objects/dict-common.h b/Objects/dict-common.h new file mode 100644 index 0000000..2912eb9 --- /dev/null +++ b/Objects/dict-common.h @@ -0,0 +1,22 @@ +#ifndef Py_DICT_COMMON_H +#define Py_DICT_COMMON_H + +typedef struct { + /* Cached hash code of me_key. */ + Py_hash_t me_hash; + PyObject *me_key; + PyObject *me_value; /* This field is only meaningful for combined tables */ +} PyDictKeyEntry; + +typedef PyDictKeyEntry *(*dict_lookup_func) +(PyDictObject *mp, PyObject *key, Py_hash_t hash, PyObject ***value_addr); + +struct _dictkeysobject { + Py_ssize_t dk_refcnt; + Py_ssize_t dk_size; + dict_lookup_func dk_lookup; + Py_ssize_t dk_usable; + PyDictKeyEntry dk_entries[1]; +}; + +#endif diff --git a/Objects/dictobject.c b/Objects/dictobject.c index 0548224..3791d5b 100644 --- a/Objects/dictobject.c +++ b/Objects/dictobject.c @@ -67,6 +67,7 @@ to the combined-table form. #define PyDict_MINSIZE_COMBINED 8 #include "Python.h" +#include "dict-common.h" #include "stringlib/eq.h" /*[clinic input] @@ -74,24 +75,6 @@ class dict "PyDictObject *" "&PyDict_Type" [clinic start generated code]*/ /*[clinic end generated code: output=da39a3ee5e6b4b0d input=f157a5a0ce9589d6]*/ -typedef struct { - /* Cached hash code of me_key. */ - Py_hash_t me_hash; - PyObject *me_key; - PyObject *me_value; /* This field is only meaningful for combined tables */ -} PyDictKeyEntry; - -typedef PyDictKeyEntry *(*dict_lookup_func) -(PyDictObject *mp, PyObject *key, Py_hash_t hash, PyObject ***value_addr); - -struct _dictkeysobject { - Py_ssize_t dk_refcnt; - Py_ssize_t dk_size; - dict_lookup_func dk_lookup; - Py_ssize_t dk_usable; - PyDictKeyEntry dk_entries[1]; -}; - /* To ensure the lookup algorithm terminates, there must be at least one Unused @@ -1425,6 +1408,141 @@ _PyDict_Next(PyObject *op, Py_ssize_t *ppos, PyObject **pkey, return 1; } +/* Internal version of dict.pop(). */ +PyObject * +_PyDict_Pop(PyDictObject *mp, PyObject *key, PyObject *deflt) +{ + Py_hash_t hash; + PyObject *old_value, *old_key; + PyDictKeyEntry *ep; + PyObject **value_addr; + + if (mp->ma_used == 0) { + if (deflt) { + Py_INCREF(deflt); + return deflt; + } + _PyErr_SetKeyError(key); + return NULL; + } + if (!PyUnicode_CheckExact(key) || + (hash = ((PyASCIIObject *) key)->hash) == -1) { + hash = PyObject_Hash(key); + if (hash == -1) + return NULL; + } + ep = (mp->ma_keys->dk_lookup)(mp, key, hash, &value_addr); + if (ep == NULL) + return NULL; + old_value = *value_addr; + if (old_value == NULL) { + if (deflt) { + Py_INCREF(deflt); + return deflt; + } + _PyErr_SetKeyError(key); + return NULL; + } + *value_addr = NULL; + mp->ma_used--; + if (!_PyDict_HasSplitTable(mp)) { + ENSURE_ALLOWS_DELETIONS(mp); + old_key = ep->me_key; + Py_INCREF(dummy); + ep->me_key = dummy; + Py_DECREF(old_key); + } + return old_value; +} + +/* Internal version of dict.from_keys(). It is subclass-friendly. */ +PyObject * +_PyDict_FromKeys(PyObject *cls, PyObject *iterable, PyObject *value) +{ + PyObject *it; /* iter(iterable) */ + PyObject *key; + PyObject *d; + int status; + + d = PyObject_CallObject(cls, NULL); + if (d == NULL) + return NULL; + + if (PyDict_CheckExact(d) && ((PyDictObject *)d)->ma_used == 0) { + if (PyDict_CheckExact(iterable)) { + PyDictObject *mp = (PyDictObject *)d; + PyObject *oldvalue; + Py_ssize_t pos = 0; + PyObject *key; + Py_hash_t hash; + + if (dictresize(mp, Py_SIZE(iterable))) { + Py_DECREF(d); + return NULL; + } + + while (_PyDict_Next(iterable, &pos, &key, &oldvalue, &hash)) { + if (insertdict(mp, key, hash, value)) { + Py_DECREF(d); + return NULL; + } + } + return d; + } + if (PyAnySet_CheckExact(iterable)) { + PyDictObject *mp = (PyDictObject *)d; + Py_ssize_t pos = 0; + PyObject *key; + Py_hash_t hash; + + if (dictresize(mp, PySet_GET_SIZE(iterable))) { + Py_DECREF(d); + return NULL; + } + + while (_PySet_NextEntry(iterable, &pos, &key, &hash)) { + if (insertdict(mp, key, hash, value)) { + Py_DECREF(d); + return NULL; + } + } + return d; + } + } + + it = PyObject_GetIter(iterable); + if (it == NULL){ + Py_DECREF(d); + return NULL; + } + + if (PyDict_CheckExact(d)) { + while ((key = PyIter_Next(it)) != NULL) { + status = PyDict_SetItem(d, key, value); + Py_DECREF(key); + if (status < 0) + goto Fail; + } + } else { + while ((key = PyIter_Next(it)) != NULL) { + status = PyObject_SetItem(d, key, value); + Py_DECREF(key); + if (status < 0) + goto Fail; + } + } + + if (PyErr_Occurred()) + goto Fail; + Py_DECREF(it); + return d; + +Fail: + Py_DECREF(it); + Py_DECREF(d); + return NULL; +} + /* Methods */ static void @@ -1763,88 +1881,7 @@ static PyObject * dict_fromkeys_impl(PyTypeObject *type, PyObject *iterable, PyObject *value) /*[clinic end generated code: output=8fb98e4b10384999 input=b85a667f9bf4669d]*/ { - PyObject *it; /* iter(seq) */ - PyObject *key; - PyObject *d; - int status; - - d = PyObject_CallObject((PyObject *)type, NULL); - if (d == NULL) - return NULL; - - if (PyDict_CheckExact(d) && ((PyDictObject *)d)->ma_used == 0) { - if (PyDict_CheckExact(iterable)) { - PyDictObject *mp = (PyDictObject *)d; - PyObject *oldvalue; - Py_ssize_t pos = 0; - PyObject *key; - Py_hash_t hash; - - if (dictresize(mp, Py_SIZE(iterable))) { - Py_DECREF(d); - return NULL; - } - - while (_PyDict_Next(iterable, &pos, &key, &oldvalue, &hash)) { - if (insertdict(mp, key, hash, value)) { - Py_DECREF(d); - return NULL; - } - } - return d; - } - if (PyAnySet_CheckExact(iterable)) { - PyDictObject *mp = (PyDictObject *)d; - Py_ssize_t pos = 0; - PyObject *key; - Py_hash_t hash; - - if (dictresize(mp, PySet_GET_SIZE(iterable))) { - Py_DECREF(d); - return NULL; - } - - while (_PySet_NextEntry(iterable, &pos, &key, &hash)) { - if (insertdict(mp, key, hash, value)) { - Py_DECREF(d); - return NULL; - } - } - return d; - } - } - - it = PyObject_GetIter(iterable); - if (it == NULL){ - Py_DECREF(d); - return NULL; - } - - if (PyDict_CheckExact(d)) { - while ((key = PyIter_Next(it)) != NULL) { - status = PyDict_SetItem(d, key, value); - Py_DECREF(key); - if (status < 0) - goto Fail; - } - } else { - while ((key = PyIter_Next(it)) != NULL) { - status = PyObject_SetItem(d, key, value); - Py_DECREF(key); - if (status < 0) - goto Fail; - } - } - - if (PyErr_Occurred()) - goto Fail; - Py_DECREF(it); - return d; - -Fail: - Py_DECREF(it); - Py_DECREF(d); - return NULL; + return _PyDict_FromKeys((PyObject *)type, iterable, value); } static int @@ -2356,50 +2393,12 @@ dict_clear(PyDictObject *mp) static PyObject * dict_pop(PyDictObject *mp, PyObject *args) { - Py_hash_t hash; - PyObject *old_value, *old_key; PyObject *key, *deflt = NULL; - PyDictKeyEntry *ep; - PyObject **value_addr; if(!PyArg_UnpackTuple(args, "pop", 1, 2, &key, &deflt)) return NULL; - if (mp->ma_used == 0) { - if (deflt) { - Py_INCREF(deflt); - return deflt; - } - _PyErr_SetKeyError(key); - return NULL; - } - if (!PyUnicode_CheckExact(key) || - (hash = ((PyASCIIObject *) key)->hash) == -1) { - hash = PyObject_Hash(key); - if (hash == -1) - return NULL; - } - ep = (mp->ma_keys->dk_lookup)(mp, key, hash, &value_addr); - if (ep == NULL) - return NULL; - old_value = *value_addr; - if (old_value == NULL) { - if (deflt) { - Py_INCREF(deflt); - return deflt; - } - _PyErr_SetKeyError(key); - return NULL; - } - *value_addr = NULL; - mp->ma_used--; - if (!_PyDict_HasSplitTable(mp)) { - ENSURE_ALLOWS_DELETIONS(mp); - old_key = ep->me_key; - Py_INCREF(dummy); - ep->me_key = dummy; - Py_DECREF(old_key); - } - return old_value; + + return _PyDict_Pop(mp, key, deflt); } static PyObject * @@ -2506,8 +2505,8 @@ dict_tp_clear(PyObject *op) static PyObject *dictiter_new(PyDictObject *, PyTypeObject *); -static PyObject * -dict_sizeof(PyDictObject *mp) +PyObject * +_PyDict_SizeOf(PyDictObject *mp) { Py_ssize_t size, res; @@ -2575,7 +2574,7 @@ static PyMethodDef mapp_methods[] = { DICT___CONTAINS___METHODDEF {"__getitem__", (PyCFunction)dict_subscript, METH_O | METH_COEXIST, getitem__doc__}, - {"__sizeof__", (PyCFunction)dict_sizeof, METH_NOARGS, + {"__sizeof__", (PyCFunction)_PyDict_SizeOf, METH_NOARGS, sizeof__doc__}, {"get", (PyCFunction)dict_get, METH_VARARGS, get__doc__}, @@ -3104,8 +3103,8 @@ static PyObject *dictiter_iternextitem(dictiterobject *di) value = *value_ptr; Py_INCREF(key); Py_INCREF(value); - PyTuple_SET_ITEM(result, 0, key); - PyTuple_SET_ITEM(result, 1, value); + PyTuple_SET_ITEM(result, 0, key); /* steals reference */ + PyTuple_SET_ITEM(result, 1, value); /* steals reference */ return result; fail: @@ -3200,28 +3199,22 @@ dictiter_reduce(dictiterobject *di) /* The instance lay-out is the same for all three; but the type differs. */ -typedef struct { - PyObject_HEAD - PyDictObject *dv_dict; -} dictviewobject; - - static void -dictview_dealloc(dictviewobject *dv) +dictview_dealloc(_PyDictViewObject *dv) { Py_XDECREF(dv->dv_dict); PyObject_GC_Del(dv); } static int -dictview_traverse(dictviewobject *dv, visitproc visit, void *arg) +dictview_traverse(_PyDictViewObject *dv, visitproc visit, void *arg) { Py_VISIT(dv->dv_dict); return 0; } static Py_ssize_t -dictview_len(dictviewobject *dv) +dictview_len(_PyDictViewObject *dv) { Py_ssize_t len = 0; if (dv->dv_dict != NULL) @@ -3229,10 +3222,10 @@ dictview_len(dictviewobject *dv) return len; } -static PyObject * -dictview_new(PyObject *dict, PyTypeObject *type) +PyObject * +_PyDictView_New(PyObject *dict, PyTypeObject *type) { - dictviewobject *dv; + _PyDictViewObject *dv; if (dict == NULL) { PyErr_BadInternalCall(); return NULL; @@ -3244,7 +3237,7 @@ dictview_new(PyObject *dict, PyTypeObject *type) type->tp_name, dict->ob_type->tp_name); return NULL; } - dv = PyObject_GC_New(dictviewobject, type); + dv = PyObject_GC_New(_PyDictViewObject, type); if (dv == NULL) return NULL; Py_INCREF(dict); @@ -3348,7 +3341,7 @@ dictview_richcompare(PyObject *self, PyObject *other, int op) } static PyObject * -dictview_repr(dictviewobject *dv) +dictview_repr(_PyDictViewObject *dv) { PyObject *seq; PyObject *result; @@ -3365,7 +3358,7 @@ dictview_repr(dictviewobject *dv) /*** dict_keys ***/ static PyObject * -dictkeys_iter(dictviewobject *dv) +dictkeys_iter(_PyDictViewObject *dv) { if (dv->dv_dict == NULL) { Py_RETURN_NONE; @@ -3374,7 +3367,7 @@ dictkeys_iter(dictviewobject *dv) } static int -dictkeys_contains(dictviewobject *dv, PyObject *obj) +dictkeys_contains(_PyDictViewObject *dv, PyObject *obj) { if (dv->dv_dict == NULL) return 0; @@ -3499,7 +3492,7 @@ dictviews_isdisjoint(PyObject *self, PyObject *other) PyObject *item = NULL; if (self == other) { - if (dictview_len((dictviewobject *)self) == 0) + if (dictview_len((_PyDictViewObject *)self) == 0) Py_RETURN_TRUE; else Py_RETURN_FALSE; @@ -3508,7 +3501,7 @@ dictviews_isdisjoint(PyObject *self, PyObject *other) /* Iterate over the shorter object (only if other is a set, * because PySequence_Contains may be expensive otherwise): */ if (PyAnySet_Check(other) || PyDictViewSet_Check(other)) { - Py_ssize_t len_self = dictview_len((dictviewobject *)self); + Py_ssize_t len_self = dictview_len((_PyDictViewObject *)self); Py_ssize_t len_other = PyObject_Size(other); if (len_other == -1) return NULL; @@ -3555,7 +3548,7 @@ static PyMethodDef dictkeys_methods[] = { PyTypeObject PyDictKeys_Type = { PyVarObject_HEAD_INIT(&PyType_Type, 0) "dict_keys", /* tp_name */ - sizeof(dictviewobject), /* tp_basicsize */ + sizeof(_PyDictViewObject), /* tp_basicsize */ 0, /* tp_itemsize */ /* methods */ (destructor)dictview_dealloc, /* tp_dealloc */ @@ -3588,13 +3581,13 @@ PyTypeObject PyDictKeys_Type = { static PyObject * dictkeys_new(PyObject *dict) { - return dictview_new(dict, &PyDictKeys_Type); + return _PyDictView_New(dict, &PyDictKeys_Type); } /*** dict_items ***/ static PyObject * -dictitems_iter(dictviewobject *dv) +dictitems_iter(_PyDictViewObject *dv) { if (dv->dv_dict == NULL) { Py_RETURN_NONE; @@ -3603,7 +3596,7 @@ dictitems_iter(dictviewobject *dv) } static int -dictitems_contains(dictviewobject *dv, PyObject *obj) +dictitems_contains(_PyDictViewObject *dv, PyObject *obj) { PyObject *key, *value, *found; if (dv->dv_dict == NULL) @@ -3641,7 +3634,7 @@ static PyMethodDef dictitems_methods[] = { PyTypeObject PyDictItems_Type = { PyVarObject_HEAD_INIT(&PyType_Type, 0) "dict_items", /* tp_name */ - sizeof(dictviewobject), /* tp_basicsize */ + sizeof(_PyDictViewObject), /* tp_basicsize */ 0, /* tp_itemsize */ /* methods */ (destructor)dictview_dealloc, /* tp_dealloc */ @@ -3674,13 +3667,13 @@ PyTypeObject PyDictItems_Type = { static PyObject * dictitems_new(PyObject *dict) { - return dictview_new(dict, &PyDictItems_Type); + return _PyDictView_New(dict, &PyDictItems_Type); } /*** dict_values ***/ static PyObject * -dictvalues_iter(dictviewobject *dv) +dictvalues_iter(_PyDictViewObject *dv) { if (dv->dv_dict == NULL) { Py_RETURN_NONE; @@ -3706,7 +3699,7 @@ static PyMethodDef dictvalues_methods[] = { PyTypeObject PyDictValues_Type = { PyVarObject_HEAD_INIT(&PyType_Type, 0) "dict_values", /* tp_name */ - sizeof(dictviewobject), /* tp_basicsize */ + sizeof(_PyDictViewObject), /* tp_basicsize */ 0, /* tp_itemsize */ /* methods */ (destructor)dictview_dealloc, /* tp_dealloc */ @@ -3739,7 +3732,7 @@ PyTypeObject PyDictValues_Type = { static PyObject * dictvalues_new(PyObject *dict) { - return dictview_new(dict, &PyDictValues_Type); + return _PyDictView_New(dict, &PyDictValues_Type); } /* Returns NULL if cannot allocate a new PyDictKeysObject, diff --git a/Objects/object.c b/Objects/object.c index c1d7a05..be12be5 100644 --- a/Objects/object.c +++ b/Objects/object.c @@ -1607,6 +1607,21 @@ _Py_ReadyTypes(void) if (PyType_Ready(&PyDict_Type) < 0) Py_FatalError("Can't initialize dict type"); + if (PyType_Ready(&PyODict_Type) < 0) + Py_FatalError("Can't initialize OrderedDict type"); + + if (PyType_Ready(&PyODictKeys_Type) < 0) + Py_FatalError("Can't initialize odict_keys type"); + + if (PyType_Ready(&PyODictItems_Type) < 0) + Py_FatalError("Can't initialize odict_items type"); + + if (PyType_Ready(&PyODictValues_Type) < 0) + Py_FatalError("Can't initialize odict_values type"); + + if (PyType_Ready(&PyODictIter_Type) < 0) + Py_FatalError("Can't initialize odict_keyiterator type"); + if (PyType_Ready(&PySet_Type) < 0) Py_FatalError("Can't initialize set type"); diff --git a/Objects/odictobject.c b/Objects/odictobject.c new file mode 100644 index 0000000..3648913 --- /dev/null +++ b/Objects/odictobject.c @@ -0,0 +1,2394 @@ +/* Ordered Dictionary object implementation. + +This implementation is necessarily explicitly equivalent to the pure Python +OrderedDict class in Lib/collections/__init__.py. The strategy there +involves using a doubly-linked-list to capture the order. We keep to that +strategy, using a lower-level linked-list. + +About the Linked-List +===================== + +For the linked list we use a basic doubly-linked-list. Using a circularly- +linked-list does have some benefits, but they don't apply so much here +since OrderedDict is focused on the ends of the list (for the most part). +Furthermore, there are some features of generic linked-lists that we simply +don't need for OrderedDict. Thus a simple custom implementation meets our +needs. Alternatives to our simple approach include the QCIRCLE_* +macros from BSD's queue.h, and the linux's list.h. + +Getting O(1) Node Lookup +------------------------ + +One invariant of Python's OrderedDict is that it preserves time complexity +of dict's methods, particularly the O(1) operations. Simply adding a +linked-list on top of dict is not sufficient here; operations for nodes in +the middle of the linked-list implicitly require finding the node first. +With a simple linked-list like we're using, that is an O(n) operation. +Consequently, methods like __delitem__() would change from O(1) to O(n), +which is unacceptable. + +In order to preserve O(1) performance for node removal (finding nodes), we +must do better than just looping through the linked-list. Here are options +we've considered: + +1. use a second dict to map keys to nodes (a la the pure Python version). +2. keep a simple hash table mirroring the order of dict's, mapping each key + to the corresponding node in the linked-list. +3. use a version of shared keys (split dict) that allows non-unicode keys. +4. have the value stored for each key be a (value, node) pair, and adjust + __getitem__(), get(), etc. accordingly. + +The approach with the least performance impact (time and space) is #2, +mirroring the key order of dict's dk_enties with an array of node pointers. +While lookdict() and friends (dk_lookup) don't give us the index into the +array, we make use of pointer arithmetic to get that index. An alternative +would be to refactor lookdict() to provide the index, explicitly exposing +the implementation detail. We could even just use a custom lookup function +for OrderedDict that facilitates our need. However, both approaches are +significantly more complicated than just using pointer arithmetic. + +The catch with mirroring the hash table ordering is that we have to keep +the ordering in sync through any dict resizes. However, that order only +matters during node lookup. We can simply defer any potential resizing +until we need to do a lookup. + +Linked-List Nodes +----------------- + +The current implementation stores a pointer to the associated key only. +One alternative would be to store a pointer to the PyDictKeyEntry instead. +This would save one pointer de-reference per item, which is nice during +calls to values() and items(). However, it adds unnecessary overhead +otherwise, so we stick with just the key. + +Linked-List API +--------------- + +As noted, the linked-list implemented here does not have all the bells and +whistles. However, we recognize that the implementation may need to +change to accommodate performance improvements or extra functionality. To +that end, We use a simple API to interact with the linked-list. Here's a +summary of the methods/macros: + +Node info: + +* _odictnode_KEY(node) +* _odictnode_VALUE(od, node) +* _odictnode_PREV(node) +* _odictnode_NEXT(node) + +Linked-List info: + +* _odict_FIRST(od) +* _odict_LAST(od) +* _odict_EMPTY(od) +* _odict_FOREACH(od, node) - used in place of `for (node=...)` + +For adding nodes: + +* _odict_add_head(od, node) +* _odict_add_tail(od, node) +* _odict_add_new_node(od, key) + +For removing nodes: + +* _odict_pop_node(od, node, key) +* _odict_clear_node(od, node) +* _odict_clear_nodes(od, clear_each) + +Others: + +* _odict_initialize(od) +* _odict_find_node(od, key) +* _odict_keys_equal(od1, od2) + +Used, but specific to the linked-list implementation: + +* _odict_free_fast_nodes(od) + +And here's a look at how the linked-list relates to the OrderedDict API: + +============ === === ==== ==== ==== === ==== ===== ==== ==== === ==== === === +method key val prev next mem 1st last empty iter find add rmv clr keq +============ === === ==== ==== ==== === ==== ===== ==== ==== === ==== === === +__del__ ~ X +__delitem__ free ~ node +__eq__ ~ X +__iter__ X X +__new__ X X +__reduce__ X ~ X +__repr__ X X X +__reversed__ X X +__setitem__ key +__sizeof__ size X +clear ~ ~ X +copy X X X +items X X X +keys X X +move_to_end X X X ~ h/t key +pop free key +popitem X X free X X node +setdefault ~ ? ~ +values X X +============ === === ==== ==== ==== === ==== ===== ==== ==== === ==== === === + +__delitem__ is the only method that directly relies on finding an arbitrary +node in the linked-list. Everything else is iteration or relates to the +ends of the linked-list. + +Situation that Endangers Consistency +------------------------------------ +Using a raw linked-list for OrderedDict exposes a key situation that can +cause problems. If a node is stored in a variable, there is a chance that +the node may have been deallocated before the variable gets used, thus +potentially leading to a segmentation fault. A key place where this shows +up is during iteration through the linked list (via _odict_FOREACH or +otherwise). + +A number of solutions are available to resolve this situation: + +* defer looking up the node until as late as possible and certainly after + any code that could possibly result in a deletion; +* if the node is needed both before and after a point where the node might + be removed, do a check before using the node at the "after" location to + see if the node is still valid; +* like the last one, but simply pull the node again to ensure it's right; +* keep the key in the variable instead of the node and then look up the + node using the key at the point where the node is needed (this is what + we do for the iterators). + +Another related problem, preserving consistent ordering during iteration, +is described below. That one is not exclusive to using linked-lists. + + +Challenges from Subclassing dict +================================ + +OrderedDict subclasses dict, which is an unusual relationship between two +builtin types (other than the base object type). Doing so results in +some complication and deserves further explanation. There are two things +to consider here. First, in what circumstances or with what adjustments +can OrderedDict be used as a drop-in replacement for dict (at the C level)? +Second, how can the OrderedDict implementation leverage the dict +implementation effectively without introducing unnecessary coupling or +inefficiencies? + +This second point is reflected here and in the implementation, so the +further focus is on the first point. It is worth noting that for +overridden methods, the dict implementation is deferred to as much as +possible. Furthermore, coupling is limited to as little as is reasonable. + +Concrete API Compatibility +-------------------------- + +Use of the concrete C-API for dict (PyDict_*) with OrderedDict is +problematic. (See http://bugs.python.org/issue10977.) The concrete API +has a number of hard-coded assumptions tied to the dict implementation. +This is, in part, due to performance reasons, which is understandable +given the part dict plays in Python. + +Any attempt to replace dict with OrderedDict for any role in the +interpreter (e.g. **kwds) faces a challenge. Such any effort must +recognize that the instances in affected locations currently interact with +the concrete API. + +Here are some ways to address this challenge: + +1. Change the relevant usage of the concrete API in CPython and add + PyDict_CheckExact() calls to each of the concrete API funcions. +2. Adjust the relevant concrete API functions to explicitly accommodate + OrderedDict. +3. As with #1, add the checks, but improve the abstract API with smart fast + paths for dict and OrderedDict, and refactor CPython to use the abstract + API. Improvements to the abstract API would be valuable regardless. + +Adding the checks to the concrete API would help make any interpreter +switch to OrderedDict less painful for extension modules. However, this +won't work. The equivalent C API call to `dict.__setitem__(obj, k, v)` +is 'PyDict_SetItem(obj, k, v)`. This illustrates how subclasses in C call +the base class's methods, since there is no equivalent of super() in the +C API. Calling into Python for parent class API would work, but some +extension modules already rely on this feature of the concrete API. + +For reference, here is a breakdown of some of the dict concrete API: + +========================== ============= ======================= +concrete API uses abstract API +========================== ============= ======================= +PyDict_Check PyMapping_Check +(PyDict_CheckExact) - +(PyDict_New) - +(PyDictProxy_New) - +PyDict_Clear - +PyDict_Contains PySequence_Contains +PyDict_Copy - +PyDict_SetItem PyObject_SetItem +PyDict_SetItemString PyMapping_SetItemString +PyDict_DelItem PyMapping_DelItem +PyDict_DelItemString PyMapping_DelItemString +PyDict_GetItem - +PyDict_GetItemWithError PyObject_GetItem +_PyDict_GetItemIdWithError - +PyDict_GetItemString PyMapping_GetItemString +PyDict_Items PyMapping_Items +PyDict_Keys PyMapping_Keys +PyDict_Values PyMapping_Values +PyDict_Size PyMapping_Size + PyMapping_Length +PyDict_Next PyIter_Next +_PyDict_Next - +PyDict_Merge - +PyDict_Update - +PyDict_MergeFromSeq2 - +PyDict_ClearFreeList - +- PyMapping_HasKeyString +- PyMapping_HasKey +========================== ============= ======================= + + +The dict Interface Relative to OrderedDict +========================================== + +Since OrderedDict subclasses dict, understanding the various methods and +attributes of dict is important for implementing OrderedDict. + +Relevant Type Slots +------------------- + +================= ================ =================== ================ +slot attribute object dict +================= ================ =================== ================ +tp_dealloc - object_dealloc dict_dealloc +tp_repr __repr__ object_repr dict_repr +sq_contains __contains__ - dict_contains +mp_length __len__ - dict_length +mp_subscript __getitem__ - dict_subscript +mp_ass_subscript __setitem__ - dict_ass_sub + __delitem__ +tp_hash __hash__ _Py_HashPointer ..._HashNotImpl +tp_str __str__ object_str - +tp_getattro __getattribute__ ..._GenericGetAttr (repeated) + __getattr__ +tp_setattro __setattr__ ..._GenericSetAttr (disabled) +tp_doc __doc__ (literal) dictionary_doc +tp_traverse - - dict_traverse +tp_clear - - dict_tp_clear +tp_richcompare __eq__ object_richcompare dict_richcompare + __ne__ +tp_weaklistoffset (__weakref__) - - +tp_iter __iter__ - dict_iter +tp_dictoffset (__dict__) - - +tp_init __init__ object_init dict_init +tp_alloc - PyType_GenericAlloc (repeated) +tp_new __new__ object_new dict_new +tp_free - PyObject_Del PyObject_GC_Del +================= ================ =================== ================ + +Relevant Methods +---------------- + +================ =================== =============== +method object dict +================ =================== =============== +__reduce__ object_reduce - +__sizeof__ object_sizeof dict_sizeof +clear - dict_clear +copy - dict_copy +fromkeys - dict_fromkeys +get - dict_get +items - dictitems_new +keys - dictkeys_new +pop - dict_pop +popitem - dict_popitem +setdefault - dict_setdefault +update - dict_update +values - dictvalues_new +================ =================== =============== + + +Pure Python OrderedDict +======================= + +As already noted, compatibility with the pure Python OrderedDict +implementation is a key goal of this C implementation. To further that +goal, here's a summary of how OrderedDict-specific methods are implemented +in collections/__init__.py. Also provided is an indication of which +methods directly mutate or iterate the object, as well as any relationship +with the underlying linked-list. + +============= ============== == ================ === === ==== +method impl used ll uses inq mut iter +============= ============== == ================ === === ==== +__contains__ dict - - X +__delitem__ OrderedDict Y dict.__delitem__ X +__eq__ OrderedDict N OrderedDict ~ + dict.__eq__ + __iter__ +__getitem__ dict - - X +__iter__ OrderedDict Y - X +__init__ OrderedDict N update +__len__ dict - - X +__ne__ MutableMapping - __eq__ ~ +__reduce__ OrderedDict N OrderedDict ~ + __iter__ + __getitem__ +__repr__ OrderedDict N __class__ ~ + items +__reversed__ OrderedDict Y - X +__setitem__ OrderedDict Y __contains__ X + dict.__setitem__ +__sizeof__ OrderedDict Y __len__ ~ + __dict__ +clear OrderedDict Y dict.clear X +copy OrderedDict N __class__ + __init__ +fromkeys OrderedDict N __setitem__ +get dict - - ~ +items MutableMapping - ItemsView X +keys MutableMapping - KeysView X +move_to_end OrderedDict Y - X +pop OrderedDict N __contains__ X + __getitem__ + __delitem__ +popitem OrderedDict Y dict.pop X +setdefault OrderedDict N __contains__ ~ + __getitem__ + __setitem__ +update MutableMapping - __setitem__ ~ +values MutableMapping - ValuesView X +============= ============== == ================ === === ==== + +__reversed__ and move_to_end are both exclusive to OrderedDict. + + +C OrderedDict Implementation +============================ + +================= ================ +slot impl +================= ================ +tp_dealloc odict_dealloc +tp_repr odict_repr +mp_ass_subscript odict_ass_sub +tp_doc odict_doc +tp_traverse odict_traverse +tp_clear odict_tp_clear +tp_richcompare odict_richcompare +tp_weaklistoffset (offset) +tp_iter odict_iter +tp_dictoffset (offset) +tp_init odict_init +tp_alloc (repeated) +tp_new odict_new +================= ================ + +================= ================ +method impl +================= ================ +__reduce__ odict_reduce +__sizeof__ odict_sizeof +clear odict_clear +copy odict_copy +fromkeys odict_fromkeys +items odictitems_new +keys odictkeys_new +pop odict_pop +popitem odict_popitem +setdefault odict_setdefault +update odict_update +values odictvalues_new +================= ================ + +Inherited unchanged from object/dict: + +================ ========================== +method type field +================ ========================== +- tp_free +__contains__ tp_as_sequence.sq_contains +__getattr__ tp_getattro +__getattribute__ tp_getattro +__getitem__ tp_as_mapping.mp_subscript +__hash__ tp_hash +__len__ tp_as_mapping.mp_length +__setattr__ tp_setattro +__str__ tp_str +get - +================ ========================== + + +Other Challenges +================ + +Preserving Ordering During Iteration +------------------------------------ +During iteration through an OrderedDict, it is possible that items could +get added, removed, or reordered. For a linked-list implementation, as +with some other implementations, that situation may lead to undefined +behavior. The documentation for dict mentions this in the `iter()` section +of http://docs.python.org/3.4/library/stdtypes.html#dictionary-view-objects. +In this implementation we follow dict's lead (as does the pure Python +implementation) for __iter__(), keys(), values(), and items(). + +For internal iteration (using _odict_FOREACH or not), there is still the +risk that not all nodes that we expect to be seen in the loop actually get +seen. Thus, we are careful in each of those places to ensure that they +are. This comes, of course, at a small price at each location. The +solutions are much the same as those detailed in the `Situation that +Endangers Consistency` section above. + + +Potential Optimizations +======================= + +* Allocate the nodes as a block via od_fast_nodes instead of individually. + - Set node->key to NULL to indicate the node is not-in-use. + - Add _odict_EXISTS()? + - How to maintain consistency across resizes? Existing node pointers + would be invalidate after a resize, which is particularly problematic + for the iterators. +* Use a more stream-lined implementation of update() and, likely indirectly, + __init__(). + +*/ + +/* TODO + +sooner: +- reentrancy (make sure everything is at a thread-safe state when calling + into Python). I've already checked this multiple times, but want to + make one more pass. +- add unit tests for reentrancy? + +later: +- make the dict views support the full set API (the pure Python impl does) +- implement a fuller MutableMapping API in C? +- move the MutableMapping implementation to abstract.c? +- optimize mutablemapping_update +- use PyObject_MALLOC (small object allocator) for odict nodes? +- support subclasses better (e.g. in odict_richcompare) + +*/ + +#include "Python.h" +#include "structmember.h" +#include "dict-common.h" +#include + + +typedef struct _odictnode _ODictNode; + +/* PyODictObject */ +struct _odictobject { + /* od_dict is the underlying dict. */ + PyDictObject od_dict; + /* od_first is the first node in the odict, if any. */ + _ODictNode *od_first; + /* od_last is the last node in the odict, if any. */ + _ODictNode *od_last; + /* od_size is the number of entries in od_fast_nodes. */ + Py_ssize_t od_size; /* managed by _odict_resize() */ + /* od_fast_nodes is a hash table that mirrors the dict table. */ + _ODictNode **od_fast_nodes; /* managed by _odict_resize() */ + /* od_inst_dict is OrderedDict().__dict__. */ + PyObject *od_inst_dict; + /* od_weakreflist holds weakrefs to the odict. */ + PyObject *od_weakreflist; +}; + + +/* ---------------------------------------------- + * odict keys (a simple doubly-linked list) + */ + +struct _odictnode { + PyObject *key; + _ODictNode *next; + _ODictNode *prev; +}; + +#define _odictnode_KEY(node) \ + (node->key) +/* borrowed reference */ +#define _odictnode_VALUE(node, od) \ + PyODict_GetItem((PyObject *)od, _odictnode_KEY(node)) +/* If needed we could also have _odictnode_HASH. */ +#define _odictnode_PREV(node) (node->prev) +#define _odictnode_NEXT(node) (node->next) + +#define _odict_FIRST(od) (((PyODictObject *)od)->od_first) +#define _odict_LAST(od) (((PyODictObject *)od)->od_last) +#define _odict_EMPTY(od) (_odict_FIRST(od) == NULL) +#define _odict_FOREACH(od, node) \ + for (node = _odict_FIRST(od); node != NULL; node = _odictnode_NEXT(node)) + + +static Py_ssize_t _odict_get_index(PyODictObject *, PyObject *); /* forward */ + +static void +_odict_free_fast_nodes(PyODictObject *od) { + if (od->od_fast_nodes) { + PyMem_FREE(od->od_fast_nodes); + } +} + +static int +_odict_resize(PyODictObject *od) { + Py_ssize_t size, prev_size, i; + _ODictNode **fast_nodes, *node; + + /* Initialize a new "fast nodes" table. */ + size = ((PyDictObject *)od)->ma_keys->dk_size; + fast_nodes = PyMem_NEW(_ODictNode *, size); + if (fast_nodes == NULL) { + PyErr_NoMemory(); + return -1; + } + for (i = 0; i < size; i++) + fast_nodes[i] = NULL; + + /* Copy the current nodes into the table. */ + prev_size = od->od_size; + od->od_size = size; + _odict_FOREACH(od, node) { + assert(node != NULL); + i = _odict_get_index(od, _odictnode_KEY(node)); + if (i < 0) { + od->od_size = prev_size; + PyMem_FREE(fast_nodes); + return -1; + } + fast_nodes[i] = node; + } + if (size != ((PyDictObject *)od)->ma_keys->dk_size) { + /* If _odict_get_index triggered a resize then we are already done. */ + PyMem_FREE(fast_nodes); + return 0; + } + + /* Replace the old fast nodes table. */ + _odict_free_fast_nodes(od); + od->od_fast_nodes = fast_nodes; + return 0; +} + +/* Return the index into the hash table, regardless of a valid node. */ +static Py_ssize_t +_odict_get_index(PyODictObject *od, PyObject *key) +{ + Py_hash_t hash; + PyObject **value_addr = NULL; + PyDictKeyEntry *ep; + PyDictKeysObject *keys = ((PyDictObject *)od)->ma_keys; + + assert(key != NULL); + do { + /* Ensure od_fast_nodes and dk_entries are in sync. */ + if (keys->dk_size != od->od_size) { + int resize_res = _odict_resize(od); + if (resize_res < 0) + return -1; + } + + /* now get the index */ + hash = PyObject_Hash(key); + if (hash == -1) + return -1; + /* May have resized during the PyObject_Hash() call. */ + keys = ((PyDictObject *)od)->ma_keys; + } while (keys->dk_size != od->od_size); + + ep = (keys->dk_lookup)((PyDictObject *)od, key, hash, &value_addr); + if (ep == NULL) + return -1; + /* We use pointer arithmetic to get the entry's index into the table. */ + return ep - keys->dk_entries; +} + +static int +_odict_initialize(PyODictObject *od) +{ + _odict_FIRST(od) = NULL; + _odict_LAST(od) = NULL; + return _odict_resize((PyODictObject *)od); +} + +/* Returns NULL if there was some error or the key was not found. */ +static _ODictNode * +_odict_find_node(PyODictObject *od, PyObject *key) +{ + Py_ssize_t index; + + if (_odict_EMPTY(od)) + return NULL; + index = _odict_get_index(od, key); + if (index < 0) + return NULL; + return od->od_fast_nodes[index]; +} + +static void +_odict_add_head(PyODictObject *od, _ODictNode *node) +{ + if (_odict_FIRST(od) == NULL) { + _odictnode_PREV(node) = NULL; + _odictnode_NEXT(node) = NULL; + _odict_FIRST(od) = node; + _odict_LAST(od) = node; + } + else { + _odictnode_PREV(node) = NULL; + _odictnode_NEXT(node) = _odict_FIRST(od); + _odict_FIRST(od) = node; + _odictnode_PREV(_odict_FIRST(od)) = node; + } +} + +static void +_odict_add_tail(PyODictObject *od, _ODictNode *node) +{ + if (_odict_LAST(od) == NULL) { + _odictnode_PREV(node) = NULL; + _odictnode_NEXT(node) = NULL; + _odict_FIRST(od) = node; + _odict_LAST(od) = node; + } + else { + _odictnode_PREV(node) = _odict_LAST(od); + _odictnode_NEXT(node) = NULL; + _odictnode_NEXT(_odict_LAST(od)) = node; + _odict_LAST(od) = node; + } +} + +/* adds the node to the end of the list */ +static int +_odict_add_new_node(PyODictObject *od, PyObject *key) +{ + Py_ssize_t i; + _ODictNode *node; + + Py_INCREF(key); + i = _odict_get_index(od, key); + if (i < 0) { + if (!PyErr_Occurred()) + PyErr_SetObject(PyExc_KeyError, key); + Py_DECREF(key); + return -1; + } + else if (od->od_fast_nodes[i] != NULL) { + /* We already have a node for the key so there's no need to add one. */ + Py_DECREF(key); + return 0; + } + + /* must not be added yet */ + node = (_ODictNode *)PyMem_MALLOC(sizeof(_ODictNode)); + if (node == NULL) { + Py_DECREF(key); + PyErr_NoMemory(); + return -1; + } + + _odictnode_KEY(node) = key; + _odict_add_tail(od, node); + od->od_fast_nodes[i] = node; + return 0; +} + +/* Putting the decref after the free causes problems. */ +#define _odictnode_DEALLOC(node) \ + do { \ + Py_DECREF(_odictnode_KEY(node)); \ + PyMem_FREE((void *)node); \ + } while (0) + +/* Repeated calls on the same node are no-ops. */ +static void +_odict_remove_node(PyODictObject *od, _ODictNode *node) +{ + if (_odict_FIRST(od) == node) + _odict_FIRST(od) = _odictnode_NEXT(node); + else if (_odictnode_PREV(node) != NULL) + _odictnode_NEXT(_odictnode_PREV(node)) = _odictnode_NEXT(node); + + if (_odict_LAST(od) == node) + _odict_LAST(od) = _odictnode_PREV(node); + else if (_odictnode_NEXT(node) != NULL) + _odictnode_PREV(_odictnode_NEXT(node)) = _odictnode_PREV(node); + + _odictnode_PREV(node) = NULL; + _odictnode_NEXT(node) = NULL; +} + +static _ODictNode * +_odict_pop_node(PyODictObject *od, _ODictNode *node, PyObject *key) +{ + if (node == NULL) { + node = _odict_find_node(od, key); + if (node == NULL) + return NULL; + } + _odict_remove_node(od, node); + return node; +} + +/* If someone calls PyDict_DelItem() directly on an OrderedDict, we'll + get all sorts of problems here. In PyODict_DelItem we make sure to + call _odict_clear_node first. + + This matters in the case of colliding keys. Suppose we add 3 keys: + [A, B, C], where the hash of C collides with A and the next possible + index in the hash table is occupied by B. If we remove B then for C + the dict's looknode func will give us the old index of B instead of + the index we got before deleting B. However, the node for C in + od_fast_nodes is still at the old dict index of C. Thus to be sure + things don't get out of sync, we clear the node in od_fast_nodes + *before* calling PyDict_DelItem. + + The same must be done for any other OrderedDict operations where + we modify od_fast_nodes. +*/ +static int +_odict_clear_node(PyODictObject *od, _ODictNode *node, PyObject *key) +{ + Py_ssize_t i; + + assert(key != NULL); + if (_odict_EMPTY(od)) { + /* Let later code decide if this is a KeyError. */ + return 0; + } + + i = _odict_get_index(od, key); + if (i < 0) + return PyErr_Occurred() ? -1 : 0; + + if (node == NULL) + node = od->od_fast_nodes[i]; + assert(node == od->od_fast_nodes[i]); + if (node == NULL) { + /* Let later code decide if this is a KeyError. */ + return 0; + } + + // Now clear the node. + od->od_fast_nodes[i] = NULL; + _odict_remove_node(od, node); + _odictnode_DEALLOC(node); + return 0; +} + +static void +_odict_clear_nodes(PyODictObject *od) +{ + _ODictNode *node, *next; + + if (!_odict_EMPTY(od)) { + node = _odict_FIRST(od); + while (node != NULL) { + next = _odictnode_NEXT(node); + _odictnode_DEALLOC(node); + node = next; + } + _odict_FIRST(od) = NULL; + _odict_LAST(od) = NULL; + } + + _odict_free_fast_nodes(od); + od->od_fast_nodes = NULL; +} + +/* There isn't any memory management of nodes past this point. */ +#undef _odictnode_DEALLOC + +static int +_odict_keys_equal(PyODictObject *a, PyODictObject *b) +{ + _ODictNode *node_a, *node_b; + + node_a = _odict_FIRST(a); + node_b = _odict_FIRST(b); + while (1) { + if (node_a == NULL && node_b == NULL) + /* success: hit the end of each at the same time */ + return 1; + else if (node_a == NULL || node_b == NULL) + /* unequal length */ + return 0; + else { + int res = PyObject_RichCompareBool( + (PyObject *)_odictnode_KEY(node_a), + (PyObject *)_odictnode_KEY(node_b), + Py_EQ); + if (res < 0) + return res; + else if (res == 0) + return 0; + + /* otherwise it must match, so move on to the next one */ + node_a = _odictnode_NEXT(node_a); + node_b = _odictnode_NEXT(node_b); + } + } +} + + +/* ---------------------------------------------- + * OrderedDict mapping methods + */ + +/* mp_ass_subscript: __setitem__() and __delitem__() */ + +static int +odict_mp_ass_sub(PyODictObject *od, PyObject *v, PyObject *w) +{ + if (w == NULL) + return PyODict_DelItem((PyObject *)od, v); + else + return PyODict_SetItem((PyObject *)od, v, w); +} + +/* tp_as_mapping */ + +static PyMappingMethods odict_as_mapping = { + 0, /*mp_length*/ + 0, /*mp_subscript*/ + (objobjargproc)odict_mp_ass_sub, /*mp_ass_subscript*/ +}; + + +/* ---------------------------------------------- + * OrderedDict methods + */ + +/* __delitem__() */ + +PyDoc_STRVAR(odict_delitem__doc__, "od.__delitem__(y) <==> del od[y]"); + +/* __eq__() */ + +PyDoc_STRVAR(odict_eq__doc__, +"od.__eq__(y) <==> od==y. Comparison to another OD is order-sensitive \n\ + while comparison to a regular mapping is order-insensitive.\n\ + "); + +/* forward */ +static PyObject * odict_richcompare(PyObject *v, PyObject *w, int op); + +static PyObject * +odict_eq(PyObject *a, PyObject *b) +{ + return odict_richcompare(a, b, Py_EQ); +} + +/* __init__() */ + +PyDoc_STRVAR(odict_init__doc__, +"Initialize an ordered dictionary. The signature is the same as\n\ + regular dictionaries, but keyword arguments are not recommended because\n\ + their insertion order is arbitrary.\n\ +\n\ + "); + +/* forward */ +static int odict_init(PyObject *self, PyObject *args, PyObject *kwds); + +/* __iter__() */ + +PyDoc_STRVAR(odict_iter__doc__, "od.__iter__() <==> iter(od)"); + +static PyObject * odict_iter(PyODictObject *self); /* forward */ + +/* __ne__() */ + +/* Mapping.__ne__() does not have a docstring. */ +PyDoc_STRVAR(odict_ne__doc__, ""); + +static PyObject * +odict_ne(PyObject *a, PyObject *b) +{ + return odict_richcompare(a, b, Py_NE); +} + +/* __repr__() */ + +PyDoc_STRVAR(odict_repr__doc__, "od.__repr__() <==> repr(od)"); + +static PyObject * odict_repr(PyODictObject *self); /* forward */ + +/* __setitem__() */ + +PyDoc_STRVAR(odict_setitem__doc__, "od.__setitem__(i, y) <==> od[i]=y"); + +/* fromkeys() */ + +PyDoc_STRVAR(odict_fromkeys__doc__, +"OD.fromkeys(S[, v]) -> New ordered dictionary with keys from S.\n\ + If not specified, the value defaults to None.\n\ +\n\ + "); + +static PyObject * +odict_fromkeys(PyObject *cls, PyObject *args) +{ + PyObject *seq; + PyObject *value = Py_None; + if (!PyArg_UnpackTuple(args, "fromkeys", 1, 2, &seq, &value)) /* borrowed */ + return NULL; + return _PyDict_FromKeys(cls, seq, value); +} + +/* __sizeof__() */ + +/* OrderedDict.__sizeof__() does not have a docstring. */ +PyDoc_STRVAR(odict_sizeof__doc__, ""); + +static PyObject * +odict_sizeof(PyODictObject *od) +{ + PyObject *pylong; + Py_ssize_t res; + + pylong = _PyDict_SizeOf((PyDictObject *)od); + if (pylong == NULL) + return NULL; + res = PyLong_AsSsize_t(pylong); + Py_DECREF(pylong); + if (res == -1 && PyErr_Occurred()) + return NULL; + + res += sizeof(PyODictObject) - sizeof(PyDictObject); + + /* instance dict */ + pylong = _PyDict_SizeOf((PyDictObject *)od->od_inst_dict); + if (pylong == NULL) + return NULL; + res += PyLong_AsSsize_t(pylong); + Py_DECREF(pylong); + if (res == -1 && PyErr_Occurred()) + return NULL; + + res += sizeof(_ODictNode) * od->od_size; /* od_fast_nodes */ + if (!_odict_EMPTY(od)) { + res += sizeof(_ODictNode) * PyODict_SIZE(od); /* linked-list */ + } + return PyLong_FromSsize_t(res); +} + +/* __reduce__() */ + +PyDoc_STRVAR(odict_reduce__doc__, "Return state information for pickling"); + +static PyObject * +odict_reduce(register PyODictObject *od) +{ + _Py_IDENTIFIER(__dict__); + _Py_IDENTIFIER(__class__); + PyObject *vars = NULL, *ns = NULL, *result = NULL, *cls = NULL; + PyObject *items_iter = NULL, *items = NULL, *args = NULL; + + /* capture any instance state */ + vars = _PyObject_GetAttrId((PyObject *)od, &PyId___dict__); + if (vars != NULL) { + PyObject *empty, *od_vars, *iterator, *key; + + /* od.__dict__ isn't necessarily a dict... */ + ns = PyObject_CallMethod((PyObject *)vars, "copy", NULL); + if (ns == NULL) + goto Done; + empty = PyODict_New(); + if (empty == NULL) + goto Done; + od_vars = _PyObject_GetAttrId((PyObject *)empty, &PyId___dict__); + Py_DECREF(empty); + if (od_vars == NULL) + goto Done; + iterator = PyObject_GetIter(od_vars); + Py_DECREF(od_vars); + if (iterator == NULL) + goto Done; + + while ( (key = PyIter_Next(iterator)) ) { + if (PyMapping_HasKey(ns, key) && PyMapping_DelItem(ns, key) != 0) { + Py_DECREF(iterator); + Py_DECREF(key); + goto Done; + } + Py_DECREF(key); + } + Py_DECREF(iterator); + if (PyErr_Occurred()) + goto Done; + + if (!PyObject_Length(ns)) { + /* nothing novel to pickle in od.__dict__ */ + Py_DECREF(ns); + ns = NULL; + } + } + + /* build the result */ + cls = _PyObject_GetAttrId((PyObject *)od, &PyId___class__); + if (cls == NULL) + goto Done; + + args = PyTuple_New(0); + if (args == NULL) + goto Done; + + items = PyObject_CallMethod((PyObject *)od, "items", NULL); + if (items == NULL) + goto Done; + + items_iter = PyObject_GetIter(items); + if (items_iter == NULL) + goto Done; + + result = PyTuple_Pack(5, cls, args, ns ? ns : Py_None, Py_None, items_iter); + +Done: + Py_XDECREF(vars); + Py_XDECREF(ns); + Py_XDECREF(cls); + Py_XDECREF(args); + Py_XDECREF(items); + Py_XDECREF(items_iter); + + return result; +} + +/* setdefault() */ + +PyDoc_STRVAR(odict_setdefault__doc__, + "od.setdefault(k[,d]) -> od.get(k,d), also set od[k]=d if k not in od"); + +/* Skips __missing__() calls. */ +static PyObject * +odict_setdefault(register PyODictObject *od, PyObject *args) +{ + _ODictNode *node; + PyObject *key, *result = NULL; + PyObject *failobj = Py_None; + + /* both borrowed */ + if (!PyArg_UnpackTuple(args, "setdefault", 1, 2, &key, &failobj)) + return NULL; + Py_INCREF(key); + Py_INCREF(failobj); + + if (PyODict_CheckExact(od)) { + node = _odict_find_node(od, key); + if (node == NULL) { + if (PyErr_Occurred()) { + goto done; + } + else if (PyODict_SetItem((PyObject *)od, key, failobj) >= 0) { + result = failobj; + Py_INCREF(failobj); + } + } + else { + result = PyODict_GetItem(od, key); /* borrowed reference */ + Py_XINCREF(result); + } + } + else { + int exists = PySequence_Contains((PyObject *)od, key); + if (exists < 0) { + goto done; + } + else if (exists) { + result = PyObject_GetItem((PyObject *)od, key); + } + else if (PyObject_SetItem((PyObject *)od, key, failobj) >= 0) { + result = failobj; + Py_INCREF(failobj); + } + } + +done: + Py_DECREF(failobj); + Py_DECREF(key); + return result; +} + +/* pop() */ + +PyDoc_STRVAR(odict_pop__doc__, +"od.pop(k[,d]) -> v, remove specified key and return the corresponding\n\ + value. If key is not found, d is returned if given, otherwise KeyError\n\ + is raised.\n\ +\n\ + "); + +/* forward */ +static PyObject * _odict_popkey(PyObject *, PyObject *, PyObject *); + +/* Skips __missing__() calls. */ +static PyObject * +odict_pop(PyObject *od, PyObject *args) +{ + PyObject *key, *failobj = NULL; + + if (!PyArg_UnpackTuple(args, "pop", 1, 2, &key, &failobj)) { /* borrowed */ + return NULL; + } + + return _odict_popkey(od, key, failobj); +} + +static PyObject * +_odict_popkey(PyObject *od, PyObject *key, PyObject *failobj) +{ + _ODictNode *node; + PyObject *value = NULL; + + Py_INCREF(key); + Py_XINCREF(failobj); + + /* Pop the node first to avoid a possible dict resize (due to + eval loop reentrancy) and complications due to hash collision + resolution. */ + node = _odict_find_node((PyODictObject *)od, key); + if (node == NULL) { + if (PyErr_Occurred()) + goto done; + } + else { + int res = _odict_clear_node((PyODictObject *)od, node, key); + if (res < 0) { + goto done; + } + } + + /* Now delete the value from the dict. */ + if (PyODict_CheckExact(od)) { + if (node != NULL) { + /* We could do PyDict_GetItem() and PyDict_DelItem() directly... */ + value = _PyDict_Pop((PyDictObject *)od, key, failobj); + } + } + else { + int exists = PySequence_Contains(od, key); + if (exists < 0) + goto done; + if (exists) { + value = PyObject_GetItem(od, key); + if (value != NULL) { + if (PyObject_DelItem(od, key) == -1) { + Py_DECREF(value); + value = NULL; + } + } + } + } + + /* Apply the fallback value, if necessary. */ + if (value == NULL && !PyErr_Occurred()) { + if (failobj) { + value = failobj; + Py_INCREF(failobj); + } + else { + PyErr_SetObject(PyExc_KeyError, key); + } + } + +done: + Py_DECREF(key); + Py_XDECREF(failobj); + return value; +} + +/* popitem() */ + +PyDoc_STRVAR(odict_popitem__doc__, +"od.popitem() -> (k, v), return and remove a (key, value) pair.\n\ + Pairs are returned in LIFO order if last is true or FIFO order if false.\n\ +\n\ + "); + +static PyObject * +odict_popitem(PyObject *od, PyObject *args) +{ + PyObject *key, *value, *item = NULL, *last = NULL; + _ODictNode *node; + + if (_odict_EMPTY((PyODictObject *)od)) { + PyErr_SetString(PyExc_KeyError, "dictionary is empty"); + return NULL; + } + + /* pull the item */ + + if (!PyArg_UnpackTuple(args, "popitem", 0, 1, &last)) /* borrowed */ + return NULL; + Py_XINCREF(last); + + if (last == NULL || last == Py_True) + node = _odict_LAST((PyODictObject *)od); + else + node = _odict_FIRST((PyODictObject *)od); + Py_XDECREF(last); + + key = _odictnode_KEY(node); + value = _odict_popkey(od, key, NULL); + if (value == NULL) + return NULL; + item = PyTuple_Pack(2, key, value); + Py_DECREF(value); + return item; +} + +/* keys() */ + +/* MutableMapping.keys() does not have a docstring. */ +PyDoc_STRVAR(odict_keys__doc__, ""); + +static PyObject * odictkeys_new(PyObject *od); /* forward */ + +/* values() */ + +/* MutableMapping.values() does not have a docstring. */ +PyDoc_STRVAR(odict_values__doc__, ""); + +static PyObject * odictvalues_new(PyObject *od); /* forward */ + +/* items() */ + +/* MutableMapping.items() does not have a docstring. */ +PyDoc_STRVAR(odict_items__doc__, ""); + +static PyObject * odictitems_new(PyObject *od); /* forward */ + +/* update() */ + +/* MutableMapping.update() does not have a docstring. */ +PyDoc_STRVAR(odict_update__doc__, ""); + +/* forward */ +static PyObject * mutablemapping_update(PyObject *, PyObject *, PyObject *); + +#define odict_update mutablemapping_update + +/* clear() */ + +PyDoc_STRVAR(odict_clear__doc__, + "od.clear() -> None. Remove all items from od."); + +static PyObject * +odict_clear(register PyODictObject *od) +{ + PyDict_Clear((PyObject *)od); + _odict_clear_nodes(od); + _odict_FIRST(od) = NULL; + _odict_LAST(od) = NULL; + if (_odict_resize(od) < 0) + return NULL; + Py_RETURN_NONE; +} + +/* copy() */ + +PyDoc_STRVAR(odict_copy__doc__, "od.copy() -> a shallow copy of od"); + +static PyObject * +odict_copy(register PyODictObject *od) +{ + _ODictNode *node; + PyObject *od_copy; + + if (PyODict_CheckExact(od)) + od_copy = PyODict_New(); + else + od_copy = PyObject_CallFunctionObjArgs((PyObject *)Py_TYPE(od), NULL); + if (od_copy == NULL) + return NULL; + + if (PyODict_CheckExact(od)) { + _odict_FOREACH(od, node) { + int res = PyODict_SetItem((PyObject *)od_copy, + _odictnode_KEY(node), + _odictnode_VALUE(node, od)); + if (res != 0) + goto fail; + } + } + else { + _odict_FOREACH(od, node) { + int res; + PyObject *value = PyObject_GetItem((PyObject *)od, + _odictnode_KEY(node)); + if (value == NULL) + goto fail; + res = PyObject_SetItem((PyObject *)od_copy, + _odictnode_KEY(node), value); + Py_DECREF(value); + if (res != 0) + goto fail; + } + } + return od_copy; + +fail: + Py_DECREF(od_copy); + return NULL; +} + +/* __reversed__() */ + +PyDoc_STRVAR(odict_reversed__doc__, "od.__reversed__() <==> reversed(od)"); + +#define _odict_ITER_REVERSED 1 +#define _odict_ITER_KEYS 2 +#define _odict_ITER_VALUES 4 + +/* forward */ +static PyObject * odictiter_new(PyODictObject *, int); + +static PyObject * +odict_reversed(PyODictObject *od) +{ + if (_odict_EMPTY(od)) { + Py_RETURN_NONE; + } + return odictiter_new(od, _odict_ITER_KEYS|_odict_ITER_REVERSED); +} + +/* move_to_end() */ + +PyDoc_STRVAR(odict_move_to_end__doc__, +"Move an existing element to the end (or beginning if last==False).\n\ +\n\ + Raises KeyError if the element does not exist.\n\ + When last=True, acts like a fast version of self[key]=self.pop(key).\n\ +\n\ + "); + +static PyObject * +odict_move_to_end(PyODictObject *od, PyObject *args) +{ + PyObject *key, *last = NULL; + Py_ssize_t pos = -1; + + /* both borrowed */ + if (!PyArg_UnpackTuple(args, "move_to_end", 1, 2, &key, &last)) + return NULL; + Py_INCREF(key); + if (_odict_EMPTY(od)) { + PyErr_SetObject(PyExc_KeyError, key); + Py_DECREF(key); + return NULL; + } + if (last != NULL) { + Py_INCREF(last); + pos = PyObject_IsTrue(last) ? -1 : 0; + Py_DECREF(last); + } + if (pos == 0) { + /* Only move if not already the first one. */ + PyObject *first_key = _odictnode_KEY(_odict_FIRST(od)); + if (PyObject_RichCompareBool(key, first_key, Py_NE)) { + _ODictNode *node = _odict_pop_node(od, NULL, key); + if (node != NULL) { + _odict_add_head(od, node); + } + else { + if (!PyErr_Occurred()) + PyErr_SetObject(PyExc_KeyError, key); + Py_DECREF(key); + return NULL; + } + } + } + else if (pos == -1) { + /* Only move if not already the last one. */ + PyObject *last_key = _odictnode_KEY(_odict_LAST(od)); + if (PyObject_RichCompareBool(key, last_key, Py_NE)) { + _ODictNode *node = _odict_pop_node(od, NULL, key); + if (node != NULL) { + _odict_add_tail(od, node); + } + else { + if (!PyErr_Occurred()) + PyErr_SetObject(PyExc_KeyError, key); + Py_DECREF(key); + return NULL; + } + } + } + Py_DECREF(key); + Py_RETURN_NONE; +} + + +/* tp_methods */ + +static PyMethodDef odict_methods[] = { + + /* explicitly defined so we can align docstrings with + * collections.OrderedDict */ + {"__delitem__", (PyCFunction)odict_mp_ass_sub, METH_NOARGS, + odict_delitem__doc__}, + {"__eq__", (PyCFunction)odict_eq, METH_NOARGS, + odict_eq__doc__}, + {"__init__", (PyCFunction)odict_init, METH_NOARGS, + odict_init__doc__}, + {"__iter__", (PyCFunction)odict_iter, METH_NOARGS, + odict_iter__doc__}, + {"__ne__", (PyCFunction)odict_ne, METH_NOARGS, + odict_ne__doc__}, + {"__repr__", (PyCFunction)odict_repr, METH_NOARGS, + odict_repr__doc__}, + {"__setitem__", (PyCFunction)odict_mp_ass_sub, METH_NOARGS, + odict_setitem__doc__}, + {"fromkeys", (PyCFunction)odict_fromkeys, METH_VARARGS | METH_CLASS, + odict_fromkeys__doc__}, + + /* overridden dict methods */ + {"__sizeof__", (PyCFunction)odict_sizeof, METH_NOARGS, + odict_sizeof__doc__}, + {"__reduce__", (PyCFunction)odict_reduce, METH_NOARGS, + odict_reduce__doc__}, + {"setdefault", (PyCFunction)odict_setdefault, METH_VARARGS, + odict_setdefault__doc__}, + {"pop", (PyCFunction)odict_pop, METH_VARARGS, + odict_pop__doc__}, + {"popitem", (PyCFunction)odict_popitem, METH_VARARGS, + odict_popitem__doc__}, + {"keys", (PyCFunction)odictkeys_new, METH_NOARGS, + odict_keys__doc__}, + {"values", (PyCFunction)odictvalues_new, METH_NOARGS, + odict_values__doc__}, + {"items", (PyCFunction)odictitems_new, METH_NOARGS, + odict_items__doc__}, + {"update", (PyCFunction)odict_update, METH_VARARGS | METH_KEYWORDS, + odict_update__doc__}, + {"clear", (PyCFunction)odict_clear, METH_NOARGS, + odict_clear__doc__}, + {"copy", (PyCFunction)odict_copy, METH_NOARGS, + odict_copy__doc__}, + + /* new methods */ + {"__reversed__", (PyCFunction)odict_reversed, METH_NOARGS, + odict_reversed__doc__}, + {"move_to_end", (PyCFunction)odict_move_to_end, METH_VARARGS, + odict_move_to_end__doc__}, + + {NULL, NULL} /* sentinel */ +}; + + +/* ---------------------------------------------- + * OrderedDict members + */ + +/* tp_members */ + +static PyMemberDef odict_members[] = { + {"__dict__", T_OBJECT, offsetof(PyODictObject, od_inst_dict), READONLY}, + {0} +}; + + +/* ---------------------------------------------- + * OrderedDict type slot methods + */ + +/* tp_dealloc */ + +static void +odict_dealloc(PyODictObject *self) +{ + PyObject_GC_UnTrack(self); + Py_TRASHCAN_SAFE_BEGIN(self); + Py_XDECREF(self->od_inst_dict); + if (self->od_weakreflist != NULL) + PyObject_ClearWeakRefs((PyObject *)self); + + _odict_clear_nodes(self); + Py_TRASHCAN_SAFE_END(self); + + /* must be last */ + PyDict_Type.tp_dealloc((PyObject *)self); +}; + +/* tp_repr */ + +static PyObject * +odict_repr(PyODictObject *self) +{ + int i; + const char *formatstr; + _Py_IDENTIFIER(__class__); + _Py_IDENTIFIER(__name__); + Py_ssize_t count = -1; + PyObject *pieces = NULL, *result = NULL, *cls = NULL; + PyObject *classname = NULL, *format = NULL, *args = NULL; + _ODictNode *node; + + i = Py_ReprEnter((PyObject *)self); + if (i != 0) { + return i > 0 ? PyUnicode_FromString("...") : NULL; + } + + if (PyODict_SIZE(self) == 0) { + /* "OrderedDict()" */ + goto Finish; + } + + if (PyODict_CheckExact(self)) { + pieces = PyList_New(PyODict_SIZE(self)); + if (pieces == NULL) + goto Done; + + _odict_FOREACH(self, node) { + PyObject *pair = PyTuple_Pack(2, _odictnode_KEY(node), + _odictnode_VALUE(node, self)); + if (pair == NULL) + goto Done; + + PyList_SET_ITEM(pieces, ++count, pair); /* steals reference */ + } + } + else { + PyObject *items = PyObject_CallMethod((PyObject *)self, "items", NULL); + if (items == NULL) + goto Done; + pieces = PySequence_List(items); + Py_DECREF(items); + if(pieces == NULL) + goto Done; + } + +Finish: + cls = _PyObject_GetAttrId((PyObject *)self, &PyId___class__); + if (cls == NULL) + goto Done; + classname = _PyObject_GetAttrId(cls, &PyId___name__); + if (classname == NULL) + goto Done; + + if (pieces == NULL) { + formatstr = "%s()"; + args = PyTuple_Pack(1, classname); + } + else { + formatstr = "%s(%r)"; + args = PyTuple_Pack(2, classname, pieces); + } + if (args == NULL) + goto Done; + + format = PyUnicode_InternFromString(formatstr); + if (format == NULL) + goto Done; + + result = PyUnicode_Format(format, args); +Done: + Py_XDECREF(pieces); + Py_XDECREF(cls); + Py_XDECREF(classname); + Py_XDECREF(format); + Py_XDECREF(args); + Py_ReprLeave((PyObject *)self); + return result; +}; + +/* tp_doc */ + +PyDoc_STRVAR(odict_doc, + "Dictionary that remembers insertion order"); + +/* tp_traverse */ + +static int +odict_traverse(PyODictObject *od, visitproc visit, void *arg) +{ + Py_VISIT(od->od_inst_dict); + Py_VISIT(od->od_weakreflist); + return PyDict_Type.tp_traverse((PyObject *)od, visit, arg); +} + +/* tp_clear */ + +static int +odict_tp_clear(PyODictObject *od) +{ + PyObject *res; + Py_CLEAR(od->od_inst_dict); + Py_CLEAR(od->od_weakreflist); + res = odict_clear(od); + if (res == NULL) + return -1; + Py_DECREF(res); + return 0; +} + +/* tp_richcompare */ + +static PyObject * +odict_richcompare(PyObject *v, PyObject *w, int op) +{ + if (!PyODict_Check(v) || !PyDict_Check(w)) { + Py_RETURN_NOTIMPLEMENTED; + } + + if (op == Py_EQ || op == Py_NE) { + PyObject *res, *cmp; + int eq; + + cmp = PyDict_Type.tp_richcompare(v, w, op); + if (cmp == NULL) + return NULL; + if (!PyODict_Check(w)) + return cmp; + if (op == Py_EQ && cmp == Py_False) + return cmp; + if (op == Py_NE && cmp == Py_True) + return cmp; + Py_DECREF(cmp); + + /* Try comparing odict keys. */ + eq = _odict_keys_equal((PyODictObject *)v, (PyODictObject *)w); + if (eq < 0) + return NULL; + + res = (eq == (op == Py_EQ)) ? Py_True : Py_False; + Py_INCREF(res); + return res; + } else { + Py_RETURN_NOTIMPLEMENTED; + } +}; + +/* tp_iter */ + +static PyObject * +odict_iter(PyODictObject *od) +{ + return odictiter_new(od, _odict_ITER_KEYS); +}; + +/* tp_init */ + +static int +odict_init(PyObject *self, PyObject *args, PyObject *kwds) +{ + PyObject *res; + Py_ssize_t len = PyObject_Length(args); + + if (len == -1) + return -1; + if (len > 1) { + char *msg = "expected at most 1 arguments, got %d"; + PyErr_Format(PyExc_TypeError, msg, len); + return -1; + } + + /* __init__() triggering update() is just the way things are! */ + res = odict_update(self, args, kwds); + if (res == NULL) { + return -1; + } else { + Py_DECREF(res); + return 0; + } +}; + +/* tp_new */ + +static PyObject * +odict_new(PyTypeObject *type, PyObject *args, PyObject *kwds) +{ + PyObject *od = PyDict_Type.tp_new(type, args, kwds); + if (od != NULL) { + ((PyODictObject *)od)->od_inst_dict = PyDict_New(); + ((PyODictObject *)od)->od_weakreflist = NULL; + if (_odict_initialize((PyODictObject *)od) < 0) + return NULL; + } + return od; +} + +/* PyODict_Type */ + +PyTypeObject PyODict_Type = { + PyVarObject_HEAD_INIT(&PyType_Type, 0) + "collections.OrderedDict", /* tp_name */ + sizeof(PyODictObject), /* tp_basicsize */ + 0, /* tp_itemsize */ + (destructor)odict_dealloc, /* tp_dealloc */ + 0, /* tp_print */ + 0, /* tp_getattr */ + 0, /* tp_setattr */ + 0, /* tp_reserved */ + (reprfunc)odict_repr, /* tp_repr */ + 0, /* tp_as_number */ + 0, /* tp_as_sequence */ + &odict_as_mapping, /* tp_as_mapping */ + 0, /* tp_hash */ + 0, /* tp_call */ + 0, /* tp_str */ + 0, /* tp_getattro */ + 0, /* tp_setattro */ + 0, /* tp_as_buffer */ + Py_TPFLAGS_DEFAULT | Py_TPFLAGS_BASETYPE | Py_TPFLAGS_HAVE_GC,/* tp_flags */ + odict_doc, /* tp_doc */ + (traverseproc)odict_traverse, /* tp_traverse */ + (inquiry)odict_tp_clear, /* tp_clear */ + (richcmpfunc)odict_richcompare, /* tp_richcompare */ + offsetof(PyODictObject, od_weakreflist), /* tp_weaklistoffset */ + (getiterfunc)odict_iter, /* tp_iter */ + 0, /* tp_iternext */ + odict_methods, /* tp_methods */ + odict_members, /* tp_members */ + 0, /* tp_getset */ + &PyDict_Type, /* tp_base */ + 0, /* tp_dict */ + 0, /* tp_descr_get */ + 0, /* tp_descr_set */ + offsetof(PyODictObject, od_inst_dict), /* tp_dictoffset */ + (initproc)odict_init, /* tp_init */ + PyType_GenericAlloc, /* tp_alloc */ + (newfunc)odict_new, /* tp_new */ + 0, /* tp_free */ +}; + + +/* ---------------------------------------------- + * the public OrderedDict API + */ + +PyObject * +PyODict_New(void) { + return odict_new(&PyODict_Type, NULL, NULL); +}; + +int +PyODict_SetItem(PyObject *od, PyObject *key, PyObject *value) { + int res = PyDict_SetItem(od, key, value); + if (res == 0) { + res = _odict_add_new_node((PyODictObject *)od, key); + } + return res; +}; + +int +PyODict_DelItem(PyObject *od, PyObject *key) { + int res = _odict_clear_node((PyODictObject *)od, NULL, key); + if (res < 0) + return -1; + return PyDict_DelItem(od, key); +}; + + +/* ------------------------------------------- + * The OrderedDict views (keys/values/items) + */ + +typedef struct { + PyObject_HEAD + int kind; + PyODictObject *di_odict; + PyObject *di_current; + PyObject *di_result; /* reusable result tuple for iteritems */ +} odictiterobject; + +static void +odictiter_dealloc(odictiterobject *di) +{ + _PyObject_GC_UNTRACK(di); + Py_DECREF(di->di_odict); + Py_XDECREF(di->di_current); + if (di->kind & (_odict_ITER_KEYS | _odict_ITER_VALUES)) { + Py_DECREF(di->di_result); + } + PyObject_GC_Del(di); +} + +static int +odictiter_traverse(odictiterobject *di, visitproc visit, void *arg) +{ + Py_VISIT(di->di_odict); + Py_VISIT(di->di_current); /* A key could be any type, not just str. */ + Py_VISIT(di->di_result); + return 0; +} + +static PyObject * +odictiter_nextkey(odictiterobject *di) +{ + PyObject *key; + _ODictNode *node; + int reversed = di->kind & _odict_ITER_REVERSED; + + /* Get the key. */ + if (di->di_current == NULL) + return NULL; + node = _odict_find_node(di->di_odict, di->di_current); + if (node == NULL) { + /* Must have been deleted. */ + Py_DECREF(di->di_current); + di->di_current = NULL; + return NULL; + } + key = di->di_current; + + /* Advance to the next key. */ + node = reversed ? _odictnode_PREV(node) : _odictnode_NEXT(node); + if (node == NULL) { + /* Reached the end. */ + di->di_current = NULL; + } + else { + di->di_current = _odictnode_KEY(node); + Py_INCREF(di->di_current); + } + + return key; +} + +static PyObject * +odictiter_iternext(odictiterobject *di) +{ + PyObject *value; + PyObject *key = odictiter_nextkey(di); /* new reference */ + + if (key == NULL) + return NULL; + + /* Handle the keys case. */ + if (! (di->kind & _odict_ITER_VALUES)) { + return key; + } + + /* Handle the items case. */ + if (di->kind & _odict_ITER_KEYS) { + PyObject *result = di->di_result; + + value = PyODict_GetItem((PyObject *)di->di_odict, key); /* borrowed */ + + if (result->ob_refcnt == 1) { + /* not in use so we can reuse it + * (the common case during iteration) */ + Py_INCREF(result); + Py_DECREF(PyTuple_GET_ITEM(result, 0)); /* borrowed */ + Py_DECREF(PyTuple_GET_ITEM(result, 1)); /* borrowed */ + } + else { + result = PyTuple_New(2); + if (result == NULL) + return NULL; + } + + Py_INCREF(value); + PyTuple_SET_ITEM(result, 0, key); /* steals reference */ + PyTuple_SET_ITEM(result, 1, value); /* steals reference */ + + return result; + } + /* Handle the values case. */ + else { + value = PyODict_GetItem((PyObject *)di->di_odict, key); + Py_XINCREF(value); + Py_DECREF(key); + return value; + } +} + +/* No need for tp_clear because odictiterobject is not mutable. */ + +PyDoc_STRVAR(reduce_doc, "Return state information for pickling"); + +static PyObject * +odictiter_reduce(odictiterobject *di) +{ + PyObject *list; + + list = PyList_New(0); + if (!list) + return NULL; + + /* iterate the temporary into a list */ + for(;;) { + PyObject *element = odictiter_iternext(di); + if (element) { + if (PyList_Append(list, element)) { + Py_DECREF(element); + Py_DECREF(list); + return NULL; + } + Py_DECREF(element); + } + else { + /* done iterating? */ + break; + } + } + if (PyErr_Occurred()) { + Py_DECREF(list); + return NULL; + } + return Py_BuildValue("N(N)", _PyObject_GetBuiltin("iter"), list); +} + +static PyMethodDef odictiter_methods[] = { + {"__reduce__", (PyCFunction)odictiter_reduce, METH_NOARGS, reduce_doc}, + {NULL, NULL} /* sentinel */ +}; + +PyTypeObject PyODictIter_Type = { + PyVarObject_HEAD_INIT(&PyType_Type, 0) + "odict_iterator", /* tp_name */ + sizeof(odictiterobject), /* tp_basicsize */ + 0, /* tp_itemsize */ + /* methods */ + (destructor)odictiter_dealloc, /* tp_dealloc */ + 0, /* tp_print */ + 0, /* tp_getattr */ + 0, /* tp_setattr */ + 0, /* tp_reserved */ + 0, /* tp_repr */ + 0, /* tp_as_number */ + 0, /* tp_as_sequence */ + 0, /* tp_as_mapping */ + 0, /* tp_hash */ + 0, /* tp_call */ + 0, /* tp_str */ + PyObject_GenericGetAttr, /* tp_getattro */ + 0, /* tp_setattro */ + 0, /* tp_as_buffer */ + Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC, /* tp_flags */ + 0, /* tp_doc */ + (traverseproc)odictiter_traverse, /* tp_traverse */ + 0, /* tp_clear */ + 0, /* tp_richcompare */ + 0, /* tp_weaklistoffset */ + PyObject_SelfIter, /* tp_iter */ + (iternextfunc)odictiter_iternext, /* tp_iternext */ + odictiter_methods, /* tp_methods */ + 0, +}; + +static PyObject * +odictiter_new(PyODictObject *od, int kind) +{ + odictiterobject *di; + _ODictNode *node; + int reversed = kind & _odict_ITER_REVERSED; + + di = PyObject_GC_New(odictiterobject, &PyODictIter_Type); + if (di == NULL) + return NULL; + + if (kind & (_odict_ITER_KEYS | _odict_ITER_VALUES)){ + di->di_result = PyTuple_Pack(2, Py_None, Py_None); + if (di->di_result == NULL) { + Py_DECREF(di); + return NULL; + } + } + else + di->di_result = NULL; + + di->kind = kind; + node = reversed ? _odict_LAST(od) : _odict_FIRST(od); + di->di_current = node ? _odictnode_KEY(node) : NULL; + Py_XINCREF(di->di_current); + di->di_odict = od; + Py_INCREF(od); + + _PyObject_GC_TRACK(di); + return (PyObject *)di; +} + +/* keys() */ + +static PyObject * +odictkeys_iter(_PyDictViewObject *dv) +{ + if (dv->dv_dict == NULL) { + Py_RETURN_NONE; + } + return odictiter_new((PyODictObject *)dv->dv_dict, + _odict_ITER_KEYS); +} + +static PyObject * +odictkeys_reversed(_PyDictViewObject *dv) +{ + if (dv->dv_dict == NULL) { + Py_RETURN_NONE; + } + return odictiter_new((PyODictObject *)dv->dv_dict, + _odict_ITER_KEYS|_odict_ITER_REVERSED); +} + +static PyMethodDef odictkeys_methods[] = { + {"__reversed__", (PyCFunction)odictkeys_reversed, METH_NOARGS, NULL}, + {NULL, NULL} /* sentinel */ +}; + +PyTypeObject PyODictKeys_Type = { + PyVarObject_HEAD_INIT(&PyType_Type, 0) + "odict_keys", /* tp_name */ + 0, /* tp_basicsize */ + 0, /* tp_itemsize */ + 0, /* tp_dealloc */ + 0, /* tp_print */ + 0, /* tp_getattr */ + 0, /* tp_setattr */ + 0, /* tp_reserved */ + 0, /* tp_repr */ + 0, /* tp_as_number */ + 0, /* tp_as_sequence */ + 0, /* tp_as_mapping */ + 0, /* tp_hash */ + 0, /* tp_call */ + 0, /* tp_str */ + 0, /* tp_getattro */ + 0, /* tp_setattro */ + 0, /* tp_as_buffer */ + 0, /* tp_flags */ + 0, /* tp_doc */ + 0, /* tp_traverse */ + 0, /* tp_clear */ + 0, /* tp_richcompare */ + 0, /* tp_weaklistoffset */ + (getiterfunc)odictkeys_iter, /* tp_iter */ + 0, /* tp_iternext */ + odictkeys_methods, /* tp_methods */ + 0, /* tp_members */ + 0, /* tp_getset */ + &PyDictKeys_Type, /* tp_base */ +}; + +static PyObject * +odictkeys_new(PyObject *od) +{ + return _PyDictView_New(od, &PyODictKeys_Type); +} + +/* items() */ + +static PyObject * +odictitems_iter(_PyDictViewObject *dv) +{ + if (dv->dv_dict == NULL) { + Py_RETURN_NONE; + } + return odictiter_new((PyODictObject *)dv->dv_dict, + _odict_ITER_KEYS|_odict_ITER_VALUES); +} + +static PyObject * +odictitems_reversed(_PyDictViewObject *dv) +{ + if (dv->dv_dict == NULL) { + Py_RETURN_NONE; + } + return odictiter_new((PyODictObject *)dv->dv_dict, + _odict_ITER_KEYS|_odict_ITER_VALUES|_odict_ITER_REVERSED); +} + +static PyMethodDef odictitems_methods[] = { + {"__reversed__", (PyCFunction)odictitems_reversed, METH_NOARGS, NULL}, + {NULL, NULL} /* sentinel */ +}; + +PyTypeObject PyODictItems_Type = { + PyVarObject_HEAD_INIT(&PyType_Type, 0) + "odict_items", /* tp_name */ + 0, /* tp_basicsize */ + 0, /* tp_itemsize */ + 0, /* tp_dealloc */ + 0, /* tp_print */ + 0, /* tp_getattr */ + 0, /* tp_setattr */ + 0, /* tp_reserved */ + 0, /* tp_repr */ + 0, /* tp_as_number */ + 0, /* tp_as_sequence */ + 0, /* tp_as_mapping */ + 0, /* tp_hash */ + 0, /* tp_call */ + 0, /* tp_str */ + 0, /* tp_getattro */ + 0, /* tp_setattro */ + 0, /* tp_as_buffer */ + 0, /* tp_flags */ + 0, /* tp_doc */ + 0, /* tp_traverse */ + 0, /* tp_clear */ + 0, /* tp_richcompare */ + 0, /* tp_weaklistoffset */ + (getiterfunc)odictitems_iter, /* tp_iter */ + 0, /* tp_iternext */ + odictitems_methods, /* tp_methods */ + 0, /* tp_members */ + 0, /* tp_getset */ + &PyDictItems_Type, /* tp_base */ +}; + +static PyObject * +odictitems_new(PyObject *od) +{ + return _PyDictView_New(od, &PyODictItems_Type); +} + +/* values() */ + +static PyObject * +odictvalues_iter(_PyDictViewObject *dv) +{ + if (dv->dv_dict == NULL) { + Py_RETURN_NONE; + } + return odictiter_new((PyODictObject *)dv->dv_dict, + _odict_ITER_VALUES); +} + +static PyObject * +odictvalues_reversed(_PyDictViewObject *dv) +{ + if (dv->dv_dict == NULL) { + Py_RETURN_NONE; + } + return odictiter_new((PyODictObject *)dv->dv_dict, + _odict_ITER_VALUES|_odict_ITER_REVERSED); +} + +static PyMethodDef odictvalues_methods[] = { + {"__reversed__", (PyCFunction)odictvalues_reversed, METH_NOARGS, NULL}, + {NULL, NULL} /* sentinel */ +}; + +PyTypeObject PyODictValues_Type = { + PyVarObject_HEAD_INIT(&PyType_Type, 0) + "odict_values", /* tp_name */ + 0, /* tp_basicsize */ + 0, /* tp_itemsize */ + 0, /* tp_dealloc */ + 0, /* tp_print */ + 0, /* tp_getattr */ + 0, /* tp_setattr */ + 0, /* tp_reserved */ + 0, /* tp_repr */ + 0, /* tp_as_number */ + 0, /* tp_as_sequence */ + 0, /* tp_as_mapping */ + 0, /* tp_hash */ + 0, /* tp_call */ + 0, /* tp_str */ + 0, /* tp_getattro */ + 0, /* tp_setattro */ + 0, /* tp_as_buffer */ + 0, /* tp_flags */ + 0, /* tp_doc */ + 0, /* tp_traverse */ + 0, /* tp_clear */ + 0, /* tp_richcompare */ + 0, /* tp_weaklistoffset */ + (getiterfunc)odictvalues_iter, /* tp_iter */ + 0, /* tp_iternext */ + odictvalues_methods, /* tp_methods */ + 0, /* tp_members */ + 0, /* tp_getset */ + &PyDictValues_Type, /* tp_base */ +}; + +static PyObject * +odictvalues_new(PyObject *od) +{ + return _PyDictView_New(od, &PyODictValues_Type); +} + + +/* ---------------------------------------------- + MutableMappping implementations + +Mapping: + +============ =========== +method uses +============ =========== +__contains__ __getitem__ +__eq__ items +__getitem__ + +__iter__ + +__len__ + +__ne__ __eq__ +get __getitem__ +items ItemsView +keys KeysView +values ValuesView +============ =========== + +ItemsView uses __len__, __iter__, and __getitem__. +KeysView uses __len__, __iter__, and __contains__. +ValuesView uses __len__, __iter__, and __getitem__. + +MutableMapping: + +============ =========== +method uses +============ =========== +__delitem__ + +__setitem__ + +clear popitem +pop __getitem__ + __delitem__ +popitem __iter__ + _getitem__ + __delitem__ +setdefault __getitem__ + __setitem__ +update __setitem__ +============ =========== +*/ + +static int +mutablemapping_add_pairs(PyObject *self, PyObject *pairs) +{ + PyObject *pair, *iterator, *unexpected; + int res = 0; + + iterator = PyObject_GetIter(pairs); + if (iterator == NULL) + return -1; + PyErr_Clear(); + + while ((pair = PyIter_Next(iterator)) != NULL) { + /* could be more efficient (see UNPACK_SEQUENCE in ceval.c) */ + PyObject * key, *value = NULL; + PyObject *pair_iterator = PyObject_GetIter(pair); + + key = PyIter_Next(pair_iterator); + if (key == NULL) { + if (!PyErr_Occurred()) + PyErr_SetString(PyExc_ValueError, + "need more than 0 values to unpack"); + goto Done; + } + + value = PyIter_Next(pair_iterator); + if (value == NULL) { + if (!PyErr_Occurred()) + PyErr_SetString(PyExc_ValueError, + "need more than 1 value to unpack"); + goto Done; + } + + unexpected = PyIter_Next(pair_iterator); + if (unexpected != NULL) { + Py_DECREF(unexpected); + PyErr_SetString(PyExc_ValueError, + "too many values to unpack (expected 2)"); + goto Done; + } + else if (PyErr_Occurred()) + goto Done; + + res = PyObject_SetItem(self, key, value); + +Done: + Py_DECREF(pair); + Py_DECREF(pair_iterator); + Py_XDECREF(key); + Py_XDECREF(value); + if (PyErr_Occurred()) + break; + } + Py_DECREF(iterator); + + if (res < 0 || PyErr_Occurred() != NULL) + return -1; + else + return 0; +} + +static PyObject * +mutablemapping_update(PyObject *self, PyObject *args, PyObject *kwargs) +{ + int res = 0; + Py_ssize_t len = (args != NULL) ? PyObject_Size(args) : 0; + + /* first handle args, if any */ + if (len < 0) + return NULL; + else if (len > 1) { + char *msg = "update() takes at most 1 positional argument (%d given)"; + PyErr_Format(PyExc_TypeError, msg, len); + return NULL; + } + else if (len == 1) { + PyObject *other = PyTuple_GET_ITEM(args, 0); /* borrowed reference */ + if (other == NULL) + return NULL; + Py_INCREF(other); + if (PyObject_HasAttrString(other, "items")) { + PyObject *items = PyMapping_Items(other); + Py_DECREF(other); + if (items == NULL) + return NULL; + res = mutablemapping_add_pairs(self, items); + Py_DECREF(items); + if (res == -1) + return NULL; + } + else if (PyObject_HasAttrString(other, "keys")) { + PyObject *keys, *iterator, *key; + keys = PyObject_CallMethod(other, "keys", NULL); + Py_DECREF(other); + if (keys == NULL) + return NULL; + iterator = PyObject_GetIter(keys); + Py_DECREF(keys); + if (iterator == NULL) + return NULL; + while (res == 0 && (key = PyIter_Next(iterator))) { + PyObject *value = PyObject_GetItem(other, key); + if (value != NULL) { + res = PyObject_SetItem(self, key, value); + Py_DECREF(value); + } + else { + res = -1; + } + Py_DECREF(key); + } + Py_DECREF(iterator); + if (res != 0 || PyErr_Occurred()) + return NULL; + } + else { + res = mutablemapping_add_pairs(self, other); + Py_DECREF(other); + if (res != 0) + return NULL; + } + } + + /* now handle kwargs */ + len = (kwargs != NULL) ? PyObject_Size(kwargs) : 0; + if (len < 0) + return NULL; + else if (len > 0) { + PyObject *items; + if (!PyMapping_Check(kwargs)) { + PyErr_SetString(PyExc_TypeError, "expected mapping for kwargs"); + return NULL; + } + items = PyMapping_Items(kwargs); + if (items == NULL) + return NULL; + res = mutablemapping_add_pairs(self, items); + Py_DECREF(items); + if (res == -1) + return NULL; + } + + Py_RETURN_NONE; +} -- cgit v0.12