Merge pull request #7937 from charris/fix-quicksort-for-bogus-comparison

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 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 221942274..977378cfa 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)