8000 Merge pull request #7953 from charris/backport-7937 · numpy/numpy@2c8a3ba · GitHub
[go: up one dir, main page]

Skip to content

Commit 2c8a3ba

Browse files
authored
Merge pull request #7953 from charris/backport-7937
Backport 7937, BUG: Guard against buggy comparisons in generic quicksort.
2 parents 0ed551f + df32cf3 commit 2c8a3ba

File tree

2 files changed

+19
-4
lines changed

2 files changed

+19
-4
lines changed

numpy/core/src/npysort/quicksort.c.src

Lines changed: 8 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -392,13 +392,17 @@ npy_quicksort(void *start, npy_intp num, void *varr)
392392
pi = pl;
393393
pj = pr - elsize;
394394
GENERIC_SWAP(pm, pj, elsize);
395+
/*
396+
* Generic comparisons may be buggy, so don't rely on the sentinals
397+
* to keep the pointers from going out of bounds.
398+
*/
395399
for (;;) {
396400
do {
397401
pi += elsize;
398-
} while (cmp(pi, vp, arr) < 0);
402+
} while (cmp(pi, vp, arr) < 0 && pi < pj);
399403
do {
400404
pj -= elsize;
401-
} while (cmp(vp, pj, arr) < 0);
405+
} while (cmp(vp, pj, arr) < 0 && pi < pj);
402406
if (pi >= pj) {
403407
break;
404408
}
@@ -477,10 +481,10 @@ npy_aquicksort(void *vv, npy_intp* tosort, npy_intp num, void *varr)
477481
for (;;) {
478482
do {
479483
++pi;
480-
} while (cmp(v + (*pi)*elsize, vp, arr) < 0);
484+
} while (cmp(v + (*pi)*elsize, vp, arr) < 0 && pi < pj);
481485
do {
482486
--pj;
483-
} while (cmp(vp, v + (*pj)*elsize, arr) < 0);
487+
} while (cmp(vp, v + (*pj)*elsize, arr) < 0 && pi < pj);
484488
if (pi >= pj) {
485489
break;
486490
}

numpy/core/tests/test_multiarray.py

Lines changed: 11 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1296,6 +1296,17 @@ def test_sort(self):
12961296
msg = 'test empty array sort with axis=None'
12971297
assert_equal(np.sort(a, axis=None), a.ravel(), msg)
12981298

1299+
# test generic class with bogus ordering,
1300+
# should not segfault.
1301+
class Boom(object):
1302+
def __lt__(self, other):
1303+
return True
1304+
1305+
a = np.array([Boom()]*100, dtype=object)
1306+
for kind in ['q', 'm', 'h']:
1307+
msg = "bogus comparison object sort, kind=%s" % kind
1308+
c.sort(kind=kind)
1309+
12991310
def test_copy(self):
13001311
def assert_fortran(arr):
13011312
assert_(arr.flags.fortran)

0 commit comments

Comments
 (0)
0