Merged revisions 55817-55961 via svnmerge from

svn+ssh://pythondev@svn.python.org/python/branches/p3yk

................
  r55837 | guido.van.rossum | 2007-06-08 16:04:42 -0700 (Fri, 08 Jun 2007) | 2 lines

  PEP 3119 -- the abc module.
................
  r55838 | guido.van.rossum | 2007-06-08 17:38:55 -0700 (Fri, 08 Jun 2007) | 2 lines

  Implement part of PEP 3119 -- One Trick Ponies.
................
  r55847 | guido.van.rossum | 2007-06-09 08:28:06 -0700 (Sat, 09 Jun 2007) | 2 lines

  Different way to do one trick ponies, allowing registration (per PEP strawman).
................
  r55849 | guido.van.rossum | 2007-06-09 18:06:38 -0700 (Sat, 09 Jun 2007) | 3 lines

  Make sure that the magic looking for __hash__ (etc.) doesn't apply to
  real subclasses of Hashable.
................
  r55852 | guido.van.rossum | 2007-06-10 08:29:51 -0700 (Sun, 10 Jun 2007) | 2 lines

  Add some more examples, e.g. generators and dict views.
................
  r55853 | guido.van.rossum | 2007-06-10 08:31:59 -0700 (Sun, 10 Jun 2007) | 2 lines

  keys() and items() *are* containers -- just values() isn't.
................
  r55864 | georg.brandl | 2007-06-10 15:29:40 -0700 (Sun, 10 Jun 2007) | 2 lines

  PEP 3127: new octal literals, binary literals.
................
  r55865 | georg.brandl | 2007-06-10 15:31:37 -0700 (Sun, 10 Jun 2007) | 2 lines

  Some octal literal fixes in Tools.
................
  r55866 | georg.brandl | 2007-06-10 15:37:43 -0700 (Sun, 10 Jun 2007) | 2 lines

  Tokenizer changes for PEP 3127.
................
  r55867 | georg.brandl | 2007-06-10 15:37:55 -0700 (Sun, 10 Jun 2007) | 2 lines

  Some docs for PEP 3127.
................
  r55868 | georg.brandl | 2007-06-10 15:44:39 -0700 (Sun, 10 Jun 2007) | 2 lines

  Missed a place in intobject.c. Is that used anymore anyway?
................
  r55871 | neal.norwitz | 2007-06-10 18:31:49 -0700 (Sun, 10 Jun 2007) | 182 lines

  Merged revisions 55729-55868 via svnmerge from
  svn+ssh://pythondev@svn.python.org/python/trunk

  ........
    r55731 | neal.norwitz | 2007-06-01 00:29:12 -0700 (Fri, 01 Jun 2007) | 7 lines

    SF 1668596/1720897: distutils now copies data files
    even if package_dir is empty.

    This needs to be backported.  I'm too tired tonight.  It would be great
    if someone backports this if the buildbots are ok with it.  Otherwise,
    I will try to get to it tomorrow.
  ........
    r55732 | georg.brandl | 2007-06-01 04:33:33 -0700 (Fri, 01 Jun 2007) | 2 lines

    Bug #1722484: remove docstrings again when running with -OO.
  ........
    r55735 | georg.brandl | 2007-06-01 12:20:27 -0700 (Fri, 01 Jun 2007) | 2 lines

    Fix wrong issue number.
  ........
    r55739 | brett.cannon | 2007-06-01 20:02:29 -0700 (Fri, 01 Jun 2007) | 3 lines

    Have configure raise an error when building on AtheOS.  Code specific to AtheOS
    will be removed in Python 2.7.
  ........
    r55746 | neal.norwitz | 2007-06-02 11:33:53 -0700 (Sat, 02 Jun 2007) | 1 line

    Update expected birthday of 2.6
  ........
    r55751 | neal.norwitz | 2007-06-03 13:32:50 -0700 (Sun, 03 Jun 2007) | 10 lines

    Backout the original 'fix' to 1721309 which had no effect.
    Different versions of Berkeley DB handle this differently.
    The comments and bug report should have the details.  Memory is allocated
    in 4.4 (and presumably earlier), but not in 4.5.  Thus
    4.5 has the free error, but not earlier versions.

    Mostly update comments, plus make the free conditional.

    This fix was already applied to the 2.5 branch.
  ........
    r55752 | brett.cannon | 2007-06-03 16:13:41 -0700 (Sun, 03 Jun 2007) | 6 lines

    Make _strptime.TimeRE().pattern() use ``\s+`` for matching whitespace instead
    of ``\s*``.  This prevents patterns from "stealing" bits from other patterns in
    order to make a match work.

    Closes bug #1730389.  Will be backported.
  ........
    r55766 | hyeshik.chang | 2007-06-05 11:16:52 -0700 (Tue, 05 Jun 2007) | 4 lines

    Fix build on FreeBSD.  Bluetooth HCI API in FreeBSD is quite different
    from Linux's.  Just fix the build for now but the code doesn't
    support the complete capability of HCI on FreeBSD yet.
  ........
    r55770 | hyeshik.chang | 2007-06-05 11:58:51 -0700 (Tue, 05 Jun 2007) | 4 lines

    Bug #1728403: Fix a bug that CJKCodecs StreamReader hangs when it
    reads a file that ends with incomplete sequence and sizehint argument
    for .read() is specified.
  ........
    r55775 | hyeshik.chang | 2007-06-05 12:28:15 -0700 (Tue, 05 Jun 2007) | 2 lines

    Fix for Windows: close a temporary file before trying to delete it.
  ........
    r55783 | guido.van.rossum | 2007-06-05 14:24:47 -0700 (Tue, 05 Jun 2007) | 2 lines

    Patch by Tim Delany (missing DECREF). SF #1731330.
  ........
    r55785 | collin.winter | 2007-06-05 17:17:35 -0700 (Tue, 05 Jun 2007) | 3 lines

    Patch #1731049: make threading.py use a proper "raise" when checking internal state, rather than assert statements (which get stripped out by -O).
  ........
    r55786 | facundo.batista | 2007-06-06 08:13:37 -0700 (Wed, 06 Jun 2007) | 4 lines


    FTP.ntransfercmd method now uses create_connection when passive,
    using the timeout received in connection time.
  ........
    r55792 | facundo.batista | 2007-06-06 10:15:23 -0700 (Wed, 06 Jun 2007) | 7 lines


    Added an optional timeout parameter to function urllib2.urlopen,
    with tests in test_urllib2net.py (must have network resource
    enabled to execute them). Also modified test_urllib2.py because
    testing mock classes must take it into acount. Docs are also
    updated.
  ........
    r55793 | thomas.heller | 2007-06-06 13:19:19 -0700 (Wed, 06 Jun 2007) | 1 line

    Build _ctypes and _ctypes_test in the ReleaseAMD64 configuration.
  ........
    r55802 | georg.brandl | 2007-06-07 06:23:24 -0700 (Thu, 07 Jun 2007) | 3 lines

    Disallow function calls like foo(None=1).
    Backport from py3k rev. 55708 by Guido.
  ........
    r55804 | georg.brandl | 2007-06-07 06:30:24 -0700 (Thu, 07 Jun 2007) | 2 lines

    Make reindent.py executable.
  ........
    r55805 | georg.brandl | 2007-06-07 06:34:10 -0700 (Thu, 07 Jun 2007) | 2 lines

    Patch #1667860: Fix UnboundLocalError in urllib2.
  ........
    r55821 | kristjan.jonsson | 2007-06-07 16:53:49 -0700 (Thu, 07 Jun 2007) | 1 line

    Fixing changes to getbuildinfo.c that broke linux builds
  ........
    r55828 | thomas.heller | 2007-06-08 09:10:27 -0700 (Fri, 08 Jun 2007) | 1 line

    Make this test work with older Python releases where struct has no 't' format character.
  ........
    r55829 | martin.v.loewis | 2007-06-08 10:29:20 -0700 (Fri, 08 Jun 2007) | 3 lines

    Bug #1733488: Fix compilation of bufferobject.c on AIX.
    Will backport to 2.5.
  ........
    r55831 | thomas.heller | 2007-06-08 11:20:09 -0700 (Fri, 08 Jun 2007) | 2 lines

    [ 1715718 ] x64 clean compile patch for _ctypes, by Kristj?n Valur
    with small modifications.
  ........
    r55832 | thomas.heller | 2007-06-08 12:01:06 -0700 (Fri, 08 Jun 2007) | 1 line

    Fix gcc warnings intruduced by passing Py_ssize_t to PyErr_Format calls.
  ........
    r55833 | thomas.heller | 2007-06-08 12:08:31 -0700 (Fri, 08 Jun 2007) | 2 lines

    Fix wrong documentation, and correct the punktuation.
    Closes [1700455].
  ........
    r55834 | thomas.heller | 2007-06-08 12:14:23 -0700 (Fri, 08 Jun 2007) | 1 line

    Fix warnings by using proper function prototype.
  ........
    r55839 | neal.norwitz | 2007-06-08 20:36:34 -0700 (Fri, 08 Jun 2007) | 7 lines

    Prevent expandtabs() on string and unicode objects from causing a segfault when
    a large width is passed on 32-bit platforms.  Found by Google.

    It would be good for people to review this especially carefully and verify
    I don't have an off by one error and there is no other way to cause overflow.
  ........
    r55841 | neal.norwitz | 2007-06-08 21:48:22 -0700 (Fri, 08 Jun 2007) | 1 line

    Use macro version of GET_SIZE to avoid Coverity warning (#150) about a possible error.
  ........
    r55842 | martin.v.loewis | 2007-06-09 00:42:52 -0700 (Sat, 09 Jun 2007) | 3 lines

    Patch #1733960: Allow T_LONGLONG to accept ints.
    Will backport to 2.5.
  ........
    r55843 | martin.v.loewis | 2007-06-09 00:58:05 -0700 (Sat, 09 Jun 2007) | 2 lines

    Fix Windows build.
  ........
    r55845 | martin.v.loewis | 2007-06-09 03:10:26 -0700 (Sat, 09 Jun 2007) | 2 lines

    Provide LLONG_MAX for S390.
  ........
    r55854 | thomas.heller | 2007-06-10 08:59:17 -0700 (Sun, 10 Jun 2007) | 4 lines


    First version of build scripts for Windows/AMD64 (no external
    components are built yet, and 'kill_python' is disabled).
  ........
    r55855 | thomas.heller | 2007-06-10 10:55:51 -0700 (Sun, 10 Jun 2007) | 3 lines

    For now, disable the _bsddb, _sqlite3, _ssl, _testcapi, _tkinter
    modules in the ReleaseAMD64 configuration because they do not compile.
  ........
    r55856 | thomas.heller | 2007-06-10 11:27:54 -0700 (Sun, 10 Jun 2007) | 1 line

    Need to set the environment variables, otherwise devenv.com is not found.
  ........
    r55860 | thomas.heller | 2007-06-10 14:01:17 -0700 (Sun, 10 Jun 2007) | 1 line

    Revert commit 55855.
  ........
................
  r55880 | neal.norwitz | 2007-06-10 22:07:36 -0700 (Sun, 10 Jun 2007) | 5 lines

  Fix the refleak counter on test_collections.  The ABC metaclass creates
  a registry which must be cleared on each run.  Otherwise, there *seem*
  to be refleaks when there really aren't any.  (The class is held within
  the registry even though it's no longer needed.)
................
  r55884 | neal.norwitz | 2007-06-10 22:46:33 -0700 (Sun, 10 Jun 2007) | 1 line

  These tests have been removed, so they are no longer needed here
................
  r55886 | georg.brandl | 2007-06-11 00:26:37 -0700 (Mon, 11 Jun 2007) | 3 lines

  Optimize access to True and False in the compiler (if True)
  and the peepholer (LOAD_NAME True).
................
  r55905 | georg.brandl | 2007-06-11 10:02:26 -0700 (Mon, 11 Jun 2007) | 5 lines

  Remove __oct__ and __hex__ and use __index__ for converting
  non-ints before formatting in a base.

  Add a bin() builtin.
................
  r55906 | georg.brandl | 2007-06-11 10:04:44 -0700 (Mon, 11 Jun 2007) | 2 lines

  int(x, 0) does not "guess".
................
  r55907 | georg.brandl | 2007-06-11 10:05:47 -0700 (Mon, 11 Jun 2007) | 2 lines

  Add a comment to explain that nb_oct and nb_hex are nonfunctional.
................
  r55908 | guido.van.rossum | 2007-06-11 10:49:18 -0700 (Mon, 11 Jun 2007) | 2 lines

  Get rid of unused imports and comment.
................
  r55910 | guido.van.rossum | 2007-06-11 13:05:17 -0700 (Mon, 11 Jun 2007) | 2 lines

  _Abstract.__new__ now requires either no arguments or __init__ overridden.
................
  r55911 | guido.van.rossum | 2007-06-11 13:07:49 -0700 (Mon, 11 Jun 2007) | 7 lines

  Move the collections ABCs to a separate file, _abcoll.py, in order to avoid
  needing to import _collections.so during the bootstrap (this will become
  apparent in the next submit of os.py).

  Add (plain and mutable) ABCs for Set, Mapping, Sequence.
................
  r55912 | guido.van.rossum | 2007-06-11 13:09:31 -0700 (Mon, 11 Jun 2007) | 2 lines

  Rewrite the _Environ class to use the new collections ABCs.
................
  r55913 | guido.van.rossum | 2007-06-11 13:59:45 -0700 (Mon, 11 Jun 2007) | 72 lines

  Merged revisions 55869-55912 via svnmerge from
  svn+ssh://pythondev@svn.python.org/python/trunk

  ........
    r55869 | neal.norwitz | 2007-06-10 17:42:11 -0700 (Sun, 10 Jun 2007) | 1 line

    Add Atul Varma for patch # 1667860
  ........
    r55870 | neal.norwitz | 2007-06-10 18:22:03 -0700 (Sun, 10 Jun 2007) | 1 line

    Ignore valgrind problems on Ubuntu from ld
  ........
    r55872 | neal.norwitz | 2007-06-10 18:48:46 -0700 (Sun, 10 Jun 2007) | 2 lines

    Ignore config.status.lineno which seems new (new autoconf?)
  ........
    r55873 | neal.norwitz | 2007-06-10 19:14:39 -0700 (Sun, 10 Jun 2007) | 1 line

    Prevent these tests from running on Win64 since they don\'t apply there either
  ........
    r55874 | neal.norwitz | 2007-06-10 19:16:10 -0700 (Sun, 10 Jun 2007) | 5 lines

    Fix a bug when there was a newline in the string expandtabs was called on.
    This also catches another condition that can overflow.

    Will backport.
  ........
    r55879 | neal.norwitz | 2007-06-10 21:52:37 -0700 (Sun, 10 Jun 2007) | 1 line

    Prevent hang if the port cannot be opened.
  ........
    r55881 | neal.norwitz | 2007-06-10 22:28:45 -0700 (Sun, 10 Jun 2007) | 4 lines

    Add all of the distuils modules that don't seem to have explicit tests. :-(
    Move an import in mworkscompiler so that this module can be imported on
    any platform.  Hopefully this works on all platforms.
  ........
    r55882 | neal.norwitz | 2007-06-10 22:35:10 -0700 (Sun, 10 Jun 2007) | 4 lines

    SF #1734732, lower case the module names per PEP 8.

    Will backport.
  ........
    r55885 | neal.norwitz | 2007-06-10 23:16:48 -0700 (Sun, 10 Jun 2007) | 4 lines

    Not sure why this only fails sometimes on Unix machines. Better
    to disable it and only import msvccompiler on Windows since that's
    the only place it can work anyways.
  ........
    r55887 | neal.norwitz | 2007-06-11 00:29:43 -0700 (Mon, 11 Jun 2007) | 4 lines

    Bug #1734723: Fix repr.Repr() so it doesn't ignore the maxtuple attribute.

    Will backport
  ........
    r55889 | neal.norwitz | 2007-06-11 00:36:24 -0700 (Mon, 11 Jun 2007) | 1 line

    Reflow long line
  ........
    r55896 | thomas.heller | 2007-06-11 08:58:33 -0700 (Mon, 11 Jun 2007) | 3 lines

    Use "O&" in calls to PyArg_Parse when we need a 'void*' instead of "k"
    or "K" codes.
  ........
    r55901 | facundo.batista | 2007-06-11 09:27:08 -0700 (Mon, 11 Jun 2007) | 5 lines


    Added versionchanged flag to all the methods which received
    a new optional timeout parameter, and a versionadded flag to
    the socket.create_connection function.
  ........
................
  r55914 | guido.van.rossum | 2007-06-11 14:19:50 -0700 (Mon, 11 Jun 2007) | 3 lines

  New super() implementation, for PEP 3135 (though the PEP is not yet updated
  to this design, and small tweaks may still be made later).
................
  r55923 | guido.van.rossum | 2007-06-11 21:15:24 -0700 (Mon, 11 Jun 2007) | 4 lines

  I'm guessing this module broke when Neal ripped out the types module --
  it used 'list' both as a local variable and as the built-in list type.
  Renamed the local variable since that was easier.
................
  r55924 | guido.van.rossum | 2007-06-11 21:20:05 -0700 (Mon, 11 Jun 2007) | 5 lines

  Change all occurrences of super(<thisclass>, <firstarg>) to super().
  Seems to have worked, all the tests still pass.
  Exception: test_descr and test_descrtut, which have tons of these
  and are there to test the various usages.
................
  r55939 | collin.winter | 2007-06-12 13:57:33 -0700 (Tue, 12 Jun 2007) | 1 line

  Patch #1735485: remove StandardError from the exception hierarchy.
................
  r55954 | neal.norwitz | 2007-06-12 21:56:32 -0700 (Tue, 12 Jun 2007) | 51 lines

  Merged revisions 55913-55950 via svnmerge from
  svn+ssh://pythondev@svn.python.org/python/trunk

  ........
    r55926 | marc-andre.lemburg | 2007-06-12 02:09:58 -0700 (Tue, 12 Jun 2007) | 3 lines

    Apply patch #1734945 to support TurboLinux as distribution.
  ........
    r55927 | marc-andre.lemburg | 2007-06-12 02:26:49 -0700 (Tue, 12 Jun 2007) | 3 lines

    Add patch #1726668: Windows Vista support.
  ........
    r55929 | thomas.heller | 2007-06-12 08:36:22 -0700 (Tue, 12 Jun 2007) | 1 line

    Checkout, but do not yet try to build, exernal sources.
  ........
    r55930 | thomas.heller | 2007-06-12 09:08:27 -0700 (Tue, 12 Jun 2007) | 6 lines

    Add bufferoverflowU.lib to the libraries needed by _ssl (is this the
    right thing to do?).

    Set the /XP64 /RETAIL build enviroment in the makefile when building
    ReleaseAMD64.
  ........
    r55931 | thomas.heller | 2007-06-12 09:23:19 -0700 (Tue, 12 Jun 2007) | 5 lines

    Revert this change, since it breaks the win32 build:

    Add bufferoverflowU.lib to the libraries needed by _ssl (is this the
    right thing to do?).
  ........
    r55934 | thomas.heller | 2007-06-12 10:28:31 -0700 (Tue, 12 Jun 2007) | 3 lines

    Specify the bufferoverflowU.lib to the makefile on the command line
    (for ReleaseAMD64 builds).
  ........
    r55937 | thomas.heller | 2007-06-12 12:02:59 -0700 (Tue, 12 Jun 2007) | 3 lines

    Add bufferoverflowU.lib to PCBuild\_bsddb.vcproj.
    Build sqlite3.dll and bsddb.
  ........
    r55938 | thomas.heller | 2007-06-12 12:56:12 -0700 (Tue, 12 Jun 2007) | 2 lines

    Don't rebuild Berkeley DB if not needed (this was committed by accident).
  ........
    r55948 | martin.v.loewis | 2007-06-12 20:42:19 -0700 (Tue, 12 Jun 2007) | 3 lines

    Provide PY_LLONG_MAX on all systems having long long.
    Will backport to 2.5.
  ........
................
  r55959 | guido.van.rossum | 2007-06-13 09:22:41 -0700 (Wed, 13 Jun 2007) | 2 lines

  Fix a compilation warning.
................

1 files changed, 535 insertions, 0 deletions

diff --git a/Lib/_abcoll.py b/Lib/_abcoll.py
new file mode 100644
index 0000000..cd1c9ce
--- /dev/null
+++ b/Lib/_abcoll.py
@@ -0,0 +1,535 @@
+# Copyright 2007 Google, Inc. All Rights Reserved.
+# Licensed to PSF under a Contributor Agreement.
+
+"""Abstract Base Classes (ABCs) for collections, according to PEP 3119.
+
+DON'T USE THIS MODULE DIRECTLY!  The classes here should be imported
+via collections; they are defined here only to alleviate ceratin
+bootstrapping issues.  Unit tests are in test_collections.
+"""
+
+from abc import ABCMeta, abstractmethod
+
+__all__ = ["Hashable", "Iterable", "Iterator",
+           "Sized", "Container", "Callable",
+           "Set", "MutableSet",
+           "Mapping", "MutableMapping",
+           "MappingView", "KeysView", "ItemsView", "ValuesView",
+           "Sequence", "MutableSequence",
+           ]
+
+### ONE-TRICK PONIES ###
+
+class Hashable(metaclass=ABCMeta):
+
+    @abstractmethod
+    def __hash__(self):
+        return 0
+
+    @classmethod
+    def __subclasshook__(cls, C):
+        if cls is Hashable:
+            for B in C.__mro__:
+                if "__hash__" in B.__dict__:
+                    if B.__dict__["__hash__"]:
+                        return True
+                    break
+        return NotImplemented
+
+
+class Iterable(metaclass=ABCMeta):
+
+    @abstractmethod
+    def __iter__(self):
+        while False:
+            yield None
+
+    @classmethod
+    def __subclasshook__(cls, C):
+        if cls is Iterable:
+            if any("__iter__" in B.__dict__ for B in C.__mro__):
+                return True
+        return NotImplemented
+
+Iterable.register(bytes)
+
+
+class Iterator(metaclass=ABCMeta):
+
+    @abstractmethod
+    def __next__(self):
+        raise StopIteration
+
+    def __iter__(self):
+        return self
+
+    @classmethod
+    def __subclasshook__(cls, C):
+        if cls is Iterator:
+            if any("__next__" in B.__dict__ for B in C.__mro__):
+                return True
+        return NotImplemented
+
+
+class Sized(metaclass=ABCMeta):
+
+    @abstractmethod
+    def __len__(self):
+        return 0
+
+    @classmethod
+    def __subclasshook__(cls, C):
+        if cls is Sized:
+            if any("__len__" in B.__dict__ for B in C.__mro__):
+                return True
+        return NotImplemented
+
+
+class Container(metaclass=ABCMeta):
+
+    @abstractmethod
+    def __contains__(self, x):
+        return False
+
+    @classmethod
+    def __subclasshook__(cls, C):
+        if cls is Container:
+            if any("__contains__" in B.__dict__ for B in C.__mro__):
+                return True
+        return NotImplemented
+
+
+class Callable(metaclass=ABCMeta):
+
+    @abstractmethod
+    def __contains__(self, x):
+        return False
+
+    @classmethod
+    def __subclasshook__(cls, C):
+        if cls is Callable:
+            if any("__call__" in B.__dict__ for B in C.__mro__):
+                return True
+        return NotImplemented
+
+
+### SETS ###
+
+
+class Set(metaclass=ABCMeta):
+
+    """A set is a finite, iterable container.
+
+    This class provides concrete generic implementations of all
+    methods except for __contains__, __iter__ and __len__.
+
+    To override the comparisons (presumably for speed, as the
+    semantics are fixed), all you have to do is redefine __le__ and
+    then the other operations will automatically follow suit.
+    """
+
+    @abstractmethod
+    def __contains__(self, value):
+        return False
+
+    @abstractmethod
+    def __iter__(self):
+        while False:
+            yield None
+
+    @abstractmethod
+    def __len__(self):
+        return 0
+
+    def __le__(self, other):
+        if not isinstance(other, Set):
+            return NotImplemented
+        if len(self) > len(other):
+            return False
+        for elem in self:
+            if elem not in other:
+                return False
+        return True
+
+    def __lt__(self, other):
+        if not isinstance(other, Set):
+            return NotImplemented
+        return len(self) < len(other) and self.__le__(other)
+
+    def __eq__(self, other):
+        if not isinstance(other, Set):
+            return NotImplemented
+        return len(self) == len(other) and self.__le__(other)
+
+    @classmethod
+    def _from_iterable(cls, it):
+        return frozenset(it)
+
+    def __and__(self, other):
+        if not isinstance(other, Iterable):
+            return NotImplemented
+        return self._from_iterable(value for value in other if value in self)
+
+    def __or__(self, other):
+        if not isinstance(other, Iterable):
+            return NotImplemented
+        return self._from_iterable(itertools.chain(self, other))
+
+    def __sub__(self, other):
+        if not isinstance(other, Set):
+            if not isinstance(other, Iterable):
+                return NotImplemented
+            other = self._from_iterable(other)
+        return self._from_iterable(value for value in self
+                                   if value not in other)
+
+    def __xor__(self, other):
+        if not isinstance(other, Set):
+            if not isinstance(other, Iterable):
+                return NotImplemented
+            other = self._from_iterable(other)
+        return (self - other) | (other - self)
+
+    def _hash(self):
+        """Compute the hash value of a set.
+
+        Note that we don't define __hash__: not all sets are hashable.
+        But if you define a hashable set type, its __hash__ should
+        call this function.
+
+        This must be compatible __eq__.
+
+        All sets ought to compare equal if they contain the same
+        elements, regardless of how they are implemented, and
+        regardless of the order of the elements; so there's not much
+        freedom for __eq__ or __hash__.  We match the algorithm used
+        by the built-in frozenset type.
+        """
+        MAX = sys.maxint
+        MASK = 2 * MAX + 1
+        n = len(self)
+        h = 1927868237 * (n + 1)
+        h &= MASK
+        for x in self:
+            hx = hash(x)
+            h ^= (hx ^ (hx << 16) ^ 89869747)  * 3644798167
+            h &= MASK
+        h = h * 69069 + 907133923
+        h &= MASK
+        if h > MAX:
+            h -= MASK + 1
+        if h == -1:
+            h = 590923713
+        return h
+
+Set.register(frozenset)
+
+
+class MutableSet(Set):
+
+    @abstractmethod
+    def add(self, value):
+        """Return True if it was added, False if already there."""
+        raise NotImplementedError
+
+    @abstractmethod
+    def discard(self, value):
+        """Return True if it was deleted, False if not there."""
+        raise NotImplementedError
+
+    def pop(self):
+        """Return the popped value.  Raise KeyError if empty."""
+        it = iter(self)
+        try:
+            value = it.__next__()
+        except StopIteration:
+            raise KeyError
+        self.discard(value)
+        return value
+
+    def toggle(self, value):
+        """Return True if it was added, False if deleted."""
+        # XXX This implementation is not thread-safe
+        if value in self:
+            self.discard(value)
+            return False
+        else:
+            self.add(value)
+            return True
+
+    def clear(self):
+        """This is slow (creates N new iterators!) but effective."""
+        try:
+            while True:
+                self.pop()
+        except KeyError:
+            pass
+
+    def __ior__(self, it: Iterable):
+        for value in it:
+            self.add(value)
+        return self
+
+    def __iand__(self, c: Container):
+        for value in self:
+            if value not in c:
+                self.discard(value)
+        return self
+
+    def __ixor__(self, it: Iterable):
+        # This calls toggle(), so if that is overridded, we call the override
+        for value in it:
+            self.toggle(it)
+        return self
+
+    def __isub__(self, it: Iterable):
+        for value in it:
+            self.discard(value)
+        return self
+
+MutableSet.register(set)
+
+
+### MAPPINGS ###
+
+
+class Mapping(metaclass=ABCMeta):
+
+    @abstractmethod
+    def __getitem__(self, key):
+        raise KeyError
+
+    def get(self, key, default=None):
+        try:
+            return self[key]
+        except KeyError:
+            return default
+
+    def __contains__(self, key):
+        try:
+            self[key]
+        except KeyError:
+            return False
+        else:
+            return True
+
+    @abstractmethod
+    def __len__(self):
+        return 0
+
+    @abstractmethod
+    def __iter__(self):
+        while False:
+            yield None
+
+    def keys(self):
+        return KeysView(self)
+
+    def items(self):
+        return ItemsView(self)
+
+    def values(self):
+        return ValuesView(self)
+
+
+class MappingView(metaclass=ABCMeta):
+
+    def __init__(self, mapping):
+        self._mapping = mapping
+
+    def __len__(self):
+        return len(self._mapping)
+
+
+class KeysView(MappingView, Set):
+
+    def __contains__(self, key):
+        return key in self._mapping
+
+    def __iter__(self):
+        for key in self._mapping:
+            yield key
+
+KeysView.register(type({}.keys()))
+
+
+class ItemsView(MappingView, Set):
+
+    def __contains__(self, item):
+        key, value = item
+        try:
+            v = self._mapping[key]
+        except KeyError:
+            return False
+        else:
+            return v == value
+
+    def __iter__(self):
+        for key in self._mapping:
+            yield (key, self._mapping[key])
+
+ItemsView.register(type({}.items()))
+
+
+class ValuesView(MappingView):
+
+    def __contains__(self, value):
+        for key in self._mapping:
+            if value == self._mapping[key]:
+                return True
+        return False
+
+    def __iter__(self):
+        for key in self._mapping:
+            yield self._mapping[key]
+
+ValuesView.register(type({}.values()))
+
+
+class MutableMapping(Mapping):
+
+    @abstractmethod
+    def __setitem__(self, key, value):
+        raise KeyError
+
+    @abstractmethod
+    def __delitem__(self, key):
+        raise KeyError
+
+    __marker = object()
+
+    def pop(self, key, default=__marker):
+        try:
+            value = self[key]
+        except KeyError:
+            if default is self.__marker:
+                raise
+            return default
+        else:
+            del self[key]
+            return value
+
+    def popitem(self):
+        try:
+            key = next(iter(self))
+        except StopIteration:
+            raise KeyError
+        value = self[key]
+        del self[key]
+        return key, value
+
+    def clear(self):
+        try:
+            while True:
+                self.popitem()
+        except KeyError:
+            pass
+
+    def update(self, other=(), **kwds):
+        if isinstance(other, Mapping):
+            for key in other:
+                self[key] = other[key]
+        elif hasattr(other, "keys"):
+            for key in other.keys():
+                self[key] = other[key]
+        else:
+            for key, value in other:
+                self[key] = value
+        for key, value in kwds.items():
+            self[key] = value
+
+MutableMapping.register(dict)
+
+
+### SEQUENCES ###
+
+
+class Sequence(metaclass=ABCMeta):
+
+    """All the operations on a read-only sequence.
+
+    Concrete subclasses must override __new__ or __init__,
+    __getitem__, and __len__.
+    """
+
+    @abstractmethod
+    def __getitem__(self, index):
+        raise IndexError
+
+    @abstractmethod
+    def __len__(self):
+        return 0
+
+    def __iter__(self):
+        i = 0
+        while True:
+            try:
+                v = self[i]
+            except IndexError:
+                break
+            yield v
+            i += 1
+
+    def __contains__(self, value):
+        for v in self:
+            if v == value:
+                return True
+        return False
+
+    def __reversed__(self):
+        for i in reversed(range(len(self))):
+            yield self[i]
+
+    def index(self, value):
+        for i, v in enumerate(self):
+            if v == value:
+                return i
+        raise ValueError
+
+    def count(self, value):
+        return sum(1 for v in self if v == value)
+
+Sequence.register(tuple)
+Sequence.register(basestring)
+Sequence.register(buffer)
+
+
+class MutableSequence(Sequence):
+
+    @abstractmethod
+    def __setitem__(self, index, value):
+        raise IndexError
+
+    @abstractmethod
+    def __delitem__(self, index):
+        raise IndexError
+
+    @abstractmethod
+    def insert(self, index, value):
+        raise IndexError
+
+    def append(self, value):
+        self.insert(len(self), value)
+
+    def reverse(self):
+        n = len(self)
+        for i in range(n//2):
+            self[i], self[n-i-1] = self[n-i-1], self[i]
+
+    def extend(self, values):
+        for v in values:
+            self.append(v)
+
+    def pop(self, index=-1):
+        v = self[index]
+        del self[index]
+        return v
+
+    def remove(self, value):
+        del self[self.index(value)]
+
+    def __iadd__(self, values):
+        self.extend(values)
+
+MutableSequence.register(list)
+MutableSequence.register(bytes)