Merge pull request #1940 from dcherednik/importlib

Library import 14

1 files changed, 157 insertions, 20 deletions

diff --git a/contrib/tools/python3/src/Modules/_bisectmodule.c b/contrib/tools/python3/src/Modules/_bisectmodule.c
index 0caa92b2dc6..0773bbd1919 100644
--- a/contrib/tools/python3/src/Modules/_bisectmodule.c
+++ b/contrib/tools/python3/src/Modules/_bisectmodule.c
@@ -25,6 +25,26 @@ get_bisect_state(PyObject *module)
     return (bisect_state *)state;
 }
 
+static ssizeargfunc
+get_sq_item(PyObject *s)
+{
+    // The parts of PySequence_GetItem that we only need to do once
+    PyTypeObject *tp = Py_TYPE(s);
+    PySequenceMethods *m = tp->tp_as_sequence;
+    if (m && m->sq_item) {
+        return m->sq_item;
+    }
+    const char *msg;
+    if (tp->tp_as_mapping && tp->tp_as_mapping->mp_subscript) {
+        msg = "%.200s is not a sequence";
+    }
+    else {
+        msg = "'%.200s' object does not support indexing";
+    }
+    PyErr_Format(PyExc_TypeError, msg, tp->tp_name);
+    return NULL;
+}
+
 static inline Py_ssize_t
 internal_bisect_right(PyObject *list, PyObject *item, Py_ssize_t lo, Py_ssize_t hi,
                       PyObject* key)
@@ -42,32 +62,86 @@ internal_bisect_right(PyObject *list, PyObject *item, Py_ssize_t lo, Py_ssize_t
         if (hi < 0)
             return -1;
     }
+    ssizeargfunc sq_item = get_sq_item(list);
+    if (sq_item == NULL) {
+        return -1;
+    }
+    if (Py_EnterRecursiveCall("in _bisect.bisect_right")) {
+        return -1;
+    }
+    PyTypeObject *tp = Py_TYPE(item);
+    richcmpfunc compare = tp->tp_richcompare;
     while (lo < hi) {
         /* The (size_t)cast ensures that the addition and subsequent division
            are performed as unsigned operations, avoiding difficulties from
            signed overflow.  (See issue 13496.) */
         mid = ((size_t)lo + hi) / 2;
-        litem = PySequence_GetItem(list, mid);
-        if (litem == NULL)
-            return -1;
+        assert(mid >= 0);
+        // PySequence_GetItem, but we already checked the types.
+        litem = sq_item(list, mid);
+        assert((PyErr_Occurred() == NULL) ^ (litem == NULL));
+        if (litem == NULL) {
+            goto error;
+        }
         if (key != Py_None) {
             PyObject *newitem = PyObject_CallOneArg(key, litem);
             if (newitem == NULL) {
-                Py_DECREF(litem);
-                return -1;
+                goto error;
             }
             Py_SETREF(litem, newitem);
         }
-        res = PyObject_RichCompareBool(item, litem, Py_LT);
+        /* if item < key(list[mid]):
+         *     hi = mid
+         * else:
+         *     lo = mid + 1
+         */
+        if (compare != NULL && Py_IS_TYPE(litem, tp)) {
+            // A fast path for comparing objects of the same type
+            PyObject *res_obj = compare(item, litem, Py_LT);
+            if (res_obj == Py_True) {
+                Py_DECREF(res_obj);
+                Py_DECREF(litem);
+                hi = mid;
+                continue;
+            }
+            if (res_obj == Py_False) {
+                Py_DECREF(res_obj);
+                Py_DECREF(litem);
+                lo = mid + 1;
+                continue;
+            }
+            if (res_obj == NULL) {
+                goto error;
+            }
+            if (res_obj == Py_NotImplemented) {
+                Py_DECREF(res_obj);
+                compare = NULL;
+                res = PyObject_RichCompareBool(item, litem, Py_LT);
+            }
+            else {
+                res = PyObject_IsTrue(res_obj);
+                Py_DECREF(res_obj);
+            }
+        }
+        else {
+            // A default path for comparing arbitrary objects
+            res = PyObject_RichCompareBool(item, litem, Py_LT);
+        }
+        if (res < 0) {
+            goto error;
+        }
         Py_DECREF(litem);
-        if (res < 0)
-            return -1;
         if (res)
             hi = mid;
         else
             lo = mid + 1;
     }
+    Py_LeaveRecursiveCall();
     return lo;
+error:
+    Py_LeaveRecursiveCall();
+    Py_XDECREF(litem);
+    return -1;
 }
 
 /*[clinic input]
@@ -88,12 +162,14 @@ insert just after the rightmost x already there.
 
 Optional args lo (default 0) and hi (default len(a)) bound the
 slice of a to be searched.
+
+A custom key function can be supplied to customize the sort order.
 [clinic start generated code]*/
 
 static Py_ssize_t
 _bisect_bisect_right_impl(PyObject *module, PyObject *a, PyObject *x,
                           Py_ssize_t lo, Py_ssize_t hi, PyObject *key)
-/*[clinic end generated code: output=3a4bc09cc7c8a73d input=40fcc5afa06ae593]*/
+/*[clinic end generated code: output=3a4bc09cc7c8a73d input=43071869772dd53a]*/
 {
     return internal_bisect_right(a, x, lo, hi, key);
 }
@@ -114,12 +190,14 @@ If x is already in a, insert it to the right of the rightmost x.
 
 Optional args lo (default 0) and hi (default len(a)) bound the
 slice of a to be searched.
+
+A custom key function can be supplied to customize the sort order.
 [clinic start generated code]*/
 
 static PyObject *
 _bisect_insort_right_impl(PyObject *module, PyObject *a, PyObject *x,
                           Py_ssize_t lo, Py_ssize_t hi, PyObject *key)
-/*[clinic end generated code: output=ac3bf26d07aedda2 input=44e1708e26b7b802]*/
+/*[clinic end generated code: output=ac3bf26d07aedda2 input=f60777d2b6ddb239]*/
 {
     PyObject *result, *key_x;
     Py_ssize_t index;
@@ -168,32 +246,86 @@ internal_bisect_left(PyObject *list, PyObject *item, Py_ssize_t lo, Py_ssize_t h
         if (hi < 0)
             return -1;
     }
+    ssizeargfunc sq_item = get_sq_item(list);
+    if (sq_item == NULL) {
+        return -1;
+    }
+    if (Py_EnterRecursiveCall("in _bisect.bisect_left")) {
+        return -1;
+    }
+    PyTypeObject *tp = Py_TYPE(item);
+    richcmpfunc compare = tp->tp_richcompare;
     while (lo < hi) {
         /* The (size_t)cast ensures that the addition and subsequent division
            are performed as unsigned operations, avoiding difficulties from
            signed overflow.  (See issue 13496.) */
         mid = ((size_t)lo + hi) / 2;
-        litem = PySequence_GetItem(list, mid);
-        if (litem == NULL)
-            return -1;
+        assert(mid >= 0);
+        // PySequence_GetItem, but we already checked the types.
+        litem = sq_item(list, mid);
+        assert((PyErr_Occurred() == NULL) ^ (litem == NULL));
+        if (litem == NULL) {
+            goto error;
+        }
         if (key != Py_None) {
             PyObject *newitem = PyObject_CallOneArg(key, litem);
             if (newitem == NULL) {
-                Py_DECREF(litem);
-                return -1;
+                goto error;
             }
             Py_SETREF(litem, newitem);
         }
-        res = PyObject_RichCompareBool(litem, item, Py_LT);
+        /* if key(list[mid]) < item:
+         *     lo = mid + 1
+         * else:
+         *     hi = mid
+         */
+        if (compare != NULL && Py_IS_TYPE(litem, tp)) {
+            // A fast path for comparing objects of the same type
+            PyObject *res_obj = compare(litem, item, Py_LT);
+            if (res_obj == Py_True) {
+                Py_DECREF(res_obj);
+                Py_DECREF(litem);
+                lo = mid + 1;
+                continue;
+            }
+            if (res_obj == Py_False) {
+                Py_DECREF(res_obj);
+                Py_DECREF(litem);
+                hi = mid;
+                continue;
+            }
+            if (res_obj == NULL) {
+                goto error;
+            }
+            if (res_obj == Py_NotImplemented) {
+                Py_DECREF(res_obj);
+                compare = NULL;
+                res = PyObject_RichCompareBool(litem, item, Py_LT);
+            }
+            else {
+                res = PyObject_IsTrue(res_obj);
+                Py_DECREF(res_obj);
+            }
+        }
+        else {
+            // A default path for comparing arbitrary objects
+            res = PyObject_RichCompareBool(litem, item, Py_LT);
+        }
+        if (res < 0) {
+            goto error;
+        }
         Py_DECREF(litem);
-        if (res < 0)
-            return -1;
         if (res)
             lo = mid + 1;
         else
             hi = mid;
     }
+    Py_LeaveRecursiveCall();
     return lo;
+error:
+    Py_LeaveRecursiveCall();
+    Py_XDECREF(litem);
+    return -1;
 }
 
 
@@ -215,12 +347,14 @@ insert just before the leftmost x already there.
 
 Optional args lo (default 0) and hi (default len(a)) bound the
 slice of a to be searched.
+
+A custom key function can be supplied to customize the sort order.
 [clinic start generated code]*/
 
 static Py_ssize_t
 _bisect_bisect_left_impl(PyObject *module, PyObject *a, PyObject *x,
                          Py_ssize_t lo, Py_ssize_t hi, PyObject *key)
-/*[clinic end generated code: output=70749d6e5cae9284 input=90dd35b50ceb05e3]*/
+/*[clinic end generated code: output=70749d6e5cae9284 input=f29c4fe7f9b797c7]*/
 {
     return internal_bisect_left(a, x, lo, hi, key);
 }
@@ -242,12 +376,14 @@ If x is already in a, insert it to the left of the leftmost x.
 
 Optional args lo (default 0) and hi (default len(a)) bound the
 slice of a to be searched.
+
+A custom key function can be supplied to customize the sort order.
 [clinic start generated code]*/
 
 static PyObject *
 _bisect_insort_left_impl(PyObject *module, PyObject *a, PyObject *x,
                          Py_ssize_t lo, Py_ssize_t hi, PyObject *key)
-/*[clinic end generated code: output=b1d33e5e7ffff11e input=3ab65d8784f585b1]*/
+/*[clinic end generated code: output=b1d33e5e7ffff11e input=0a700a82edbd472c]*/
 {
     PyObject *result, *key_x;
     Py_ssize_t index;
@@ -321,6 +457,7 @@ bisect_modexec(PyObject *m)
 
 static PyModuleDef_Slot bisect_slots[] = {
     {Py_mod_exec, bisect_modexec},
+    {Py_mod_multiple_interpreters, Py_MOD_PER_INTERPRETER_GIL_SUPPORTED},
     {0, NULL}
 };