Merge pull request #7953 from charris/backport-7937

Backport 7937, BUG: Guard against buggy comparisons in generic quicksort.

2 files changed, 19 insertions, 4 deletions

diff --git a/numpy/core/src/npysort/quicksort.c.src b/numpy/core/src/npysort/quicksort.c.src
index 91b5e67f5..eda3f870c 100644
--- a/numpy/core/src/npysort/quicksort.c.src
+++ b/numpy/core/src/npysort/quicksort.c.src
@@ -392,13 +392,17 @@ npy_quicksort(void *start, npy_intp num, void *varr)
             pi = pl;
             pj = pr - elsize;
             GENERIC_SWAP(pm, pj, elsize);
+            /*
+             * Generic comparisons may be buggy, so don't rely on the sentinals
+             * to keep the pointers from going out of bounds.
+             */
             for (;;) {
                 do {
                     pi += elsize;
-                } while (cmp(pi, vp, arr) < 0);
+                } while (cmp(pi, vp, arr) < 0 && pi < pj);
                 do {
                     pj -= elsize;
-                } while (cmp(vp, pj, arr) < 0);
+                } while (cmp(vp, pj, arr) < 0 && pi < pj);
                 if (pi >= pj) {
                     break;
                 }
@@ -477,10 +481,10 @@ npy_aquicksort(void *vv, npy_intp* tosort, npy_intp num, void *varr)
             for (;;) {
                 do {
                     ++pi;
-                } while (cmp(v + (*pi)*elsize, vp, arr) < 0);
+                } while (cmp(v + (*pi)*elsize, vp, arr) < 0 && pi < pj);
                 do {
                     --pj;
-                } while (cmp(vp, v + (*pj)*elsize, arr) < 0);
+                } while (cmp(vp, v + (*pj)*elsize, arr) < 0 && pi < pj);
                 if (pi >= pj) {
                     break;
                 }
diff --git a/numpy/core/tests/test_multiarray.py b/numpy/core/tests/test_multiarray.py
index 7d984aa9b..7d14186d8 100644
--- a/numpy/core/tests/test_multiarray.py
+++ b/numpy/core/tests/test_multiarray.py
@@ -1296,6 +1296,17 @@ class TestMethods(TestCase):
         msg = 'test empty array sort with axis=None'
         assert_equal(np.sort(a, axis=None), a.ravel(), msg)
 
+        # test generic class with bogus ordering,
+        # should not segfault.
+        class Boom(object):
+            def __lt__(self, other):
+                return True
+
+        a = np.array([Boom()]*100, dtype=object)
+        for kind in ['q', 'm', 'h']:
+            msg = "bogus comparison object sort, kind=%s" % kind
+            c.sort(kind=kind)
+
     def test_copy(self):
         def assert_fortran(arr):
             assert_(arr.flags.fortran)