BUG: Guard against buggy comparisons in generic quicksort.

Generic types may have buggy comparison operators in which case the
sentinal values in quicksort cannot be counted on to keep the pointers
from running off the ends of the array. The solution here is to
explicitly check that the pointers are in bounds when sorting generic
types.

Closes #7934.

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 0ea9d21c7..2b6e2ed1c 100644
--- a/numpy/core/src/npysort/quicksort.c.src
+++ b/numpy/core/src/npysort/quicksort.c.src
@@ -464,13 +464,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;
                 }
@@ -559,10 +563,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 9446f0ac2..892db2dd9 100644
--- a/numpy/core/tests/test_multiarray.py
+++ b/numpy/core/tests/test_multiarray.py
@@ -1349,6 +1349,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_sort_degraded(self):
         # test degraded dataset would take minutes to run with normal qsort
         d = np.arange(1000000)