Merge pull request #11273 from seberg/sort-valgrind-fix

BUG: Remove invalid read in searchsorted if needle is empty

2 files changed, 26 insertions, 2 deletions

diff --git a/numpy/core/src/npysort/binsearch.c.src b/numpy/core/src/npysort/binsearch.c.src
index a1a07039a..c04e197b7 100644
--- a/numpy/core/src/npysort/binsearch.c.src
+++ b/numpy/core/src/npysort/binsearch.c.src
@@ -43,7 +43,12 @@ binsearch_@side@_@suff@(const char *arr, const char *key, char *ret,
 {
     npy_intp min_idx = 0;
     npy_intp max_idx = arr_len;
-    @type@ last_key_val = *(const @type@ *)key;
+    @type@ last_key_val;
+
+    if (key_len == 0) {
+        return;
+    }
+    last_key_val = *(const @type@ *)key;
 
     for (; key_len > 0; key_len--, key += key_str, ret += ret_str) {
         const @type@ key_val = *(const @type@ *)key;
@@ -86,7 +91,12 @@ argbinsearch_@side@_@suff@(const char *arr, const char *key,
 {
     npy_intp min_idx = 0;
     npy_intp max_idx = arr_len;
-    @type@ last_key_val = *(const @type@ *)key;
+    @type@ last_key_val;
+
+    if (key_len == 0) {
+        return 0;
+    }
+    last_key_val = *(const @type@ *)key;
 
     for (; key_len > 0; key_len--, key += key_str, ret += ret_str) {
         const @type@ key_val = *(const @type@ *)key;
diff --git a/numpy/core/tests/test_multiarray.py b/numpy/core/tests/test_multiarray.py
index 05dd2efd1..b13e48fdc 100644
--- a/numpy/core/tests/test_multiarray.py
+++ b/numpy/core/tests/test_multiarray.py
@@ -1997,6 +1997,13 @@ class TestMethods(object):
             assert_equal(b, out)
             b = a.searchsorted(a, 'r')
             assert_equal(b, out + 1)
+            # Test empty array, use a fresh array to get warnings in
+            # valgrind if access happens.
+            e = np.ndarray(shape=0, buffer=b'', dtype=dt)
+            b = e.searchsorted(a, 'l')
+            assert_array_equal(b, np.zeros(len(a), dtype=np.intp))
+            b = a.searchsorted(e, 'l')
+            assert_array_equal(b, np.zeros(0, dtype=np.intp))
 
     def test_searchsorted_unicode(self):
         # Test searchsorted on unicode strings.
@@ -2094,6 +2101,13 @@ class TestMethods(object):
             assert_equal(b, out)
             b = a.searchsorted(a, 'r', s)
             assert_equal(b, out + 1)
+            # Test empty array, use a fresh array to get warnings in
+            # valgrind if access happens.
+            e = np.ndarray(shape=0, buffer=b'', dtype=dt)
+            b = e.searchsorted(a, 'l', s[:0])
+            assert_array_equal(b, np.zeros(len(a), dtype=np.intp))
+            b = a.searchsorted(e, 'l', s)
+            assert_array_equal(b, np.zeros(0, dtype=np.intp))
 
         # Test non-contiguous sorter array
         a = np.array([3, 4, 1, 2, 0])