Repository: jorgecarleitao/arrow2
Pull request #1021 (2022-05-28 15:50:32)

Fixed lexsort limit equal or greater than row_count
If `limit` is equal to or greater than `row_count` in function `lexsort_to_indices_impl`, it will panic because of the index is greater than the length of the slice.

```
---- compute::sort::lex_sort::test_lex_sort_mixed_types stdout ----
thread 'compute::sort::lex_sort::test_lex_sort_mixed_types' panicked at 'partition_at_index index 4 greater than length of slice 4', /rustc/30b3f35c420694a4f24e5a4df00f06073f4f3a37/library/core/src/slice/sort.rs:893:9
stack backtrace:
   0:        0x10eca59e1 - std::backtrace_rs::backtrace::libunwind::trace::h72854132b122d638
                               at /rustc/30b3f35c420694a4f24e5a4df00f06073f4f3a37/library/std/src/../../backtrace/src/backtrace/libunwind.rs:93:5
   1:        0x10eca59e1 - std::backtrace_rs::backtrace::trace_unsynchronized::ha93153aa050311ab
                               at /rustc/30b3f35c420694a4f24e5a4df00f06073f4f3a37/library/std/src/../../backtrace/src/backtrace/mod.rs:66:5
   2:        0x10eca59e1 - std::sys_common::backtrace::_print_fmt::h5b1eb3d7be0b24ab
                               at /rustc/30b3f35c420694a4f24e5a4df00f06073f4f3a37/library/std/src/sys_common/backtrace.rs:66:5
   3:        0x10eca59e1 - <std::sys_common::backtrace::_print::DisplayBacktrace as core::fmt::Display>::fmt::h0af9e61123fe45db
                               at /rustc/30b3f35c420694a4f24e5a4df00f06073f4f3a37/library/std/src/sys_common/backtrace.rs:45:22
   4:        0x10ecc9b4b - core::fmt::write::h2584048b445b9b8c
                               at /rustc/30b3f35c420694a4f24e5a4df00f06073f4f3a37/library/core/src/fmt/mod.rs:1190:17
   5:        0x10eca0d9e - std::io::Write::write_fmt::he76dfd3db344bd00
                               at /rustc/30b3f35c420694a4f24e5a4df00f06073f4f3a37/library/std/src/io/mod.rs:1657:15
   6:        0x10eca7ca0 - std::sys_common::backtrace::_print::h8da79e38123fe8dc
                               at /rustc/30b3f35c420694a4f24e5a4df00f06073f4f3a37/library/std/src/sys_common/backtrace.rs:48:5
   7:        0x10eca7ca0 - std::sys_common::backtrace::print::h8c81a78009132972
                               at /rustc/30b3f35c420694a4f24e5a4df00f06073f4f3a37/library/std/src/sys_common/backtrace.rs:35:9
   8:        0x10eca7ca0 - std::panicking::default_hook::{{closure}}::hbd3431964909b1f1
                               at /rustc/30b3f35c420694a4f24e5a4df00f06073f4f3a37/library/std/src/panicking.rs:295:22
   9:        0x10eca79ea - std::panicking::default_hook::h121f3ab9a5b3b08e
                               at /rustc/30b3f35c420694a4f24e5a4df00f06073f4f3a37/library/std/src/panicking.rs:311:9
  10:        0x10eca83fe - std::panicking::rust_panic_with_hook::hb48cf4f9933cc169
                               at /rustc/30b3f35c420694a4f24e5a4df00f06073f4f3a37/library/std/src/panicking.rs:698:17
  11:        0x10eca8123 - std::panicking::begin_panic_handler::{{closure}}::h424426f012771223
                               at /rustc/30b3f35c420694a4f24e5a4df00f06073f4f3a37/library/std/src/panicking.rs:588:13
  12:        0x10eca5e77 - std::sys_common::backtrace::__rust_end_short_backtrace::ha4959f8921e37983
                               at /rustc/30b3f35c420694a4f24e5a4df00f06073f4f3a37/library/std/src/sys_common/backtrace.rs:138:18
  13:        0x10eca7dea - rust_begin_unwind
                               at /rustc/30b3f35c420694a4f24e5a4df00f06073f4f3a37/library/std/src/panicking.rs:584:5
  14:        0x10ed78723 - core::panicking::panic_fmt::h592cc8ebeaa4ecb9
                               at /rustc/30b3f35c420694a4f24e5a4df00f06073f4f3a37/library/core/src/panicking.rs:143:14
  15:        0x10d0e43b8 - core::slice::sort::partition_at_index::hb58c3f3334b867c6
                               at /rustc/30b3f35c420694a4f24e5a4df00f06073f4f3a37/library/core/src/slice/sort.rs:893:9
  16:        0x10c732920 - core::slice::<impl [T]>::select_nth_unstable_by::hade57f88b01952bb
                               at /rustc/30b3f35c420694a4f24e5a4df00f06073f4f3a37/library/core/src/slice/mod.rs:2656:9
  17:        0x10d0f1361 - arrow2::compute::sort::lex_sort::lexsort_to_indices_impl::h3986aef87b3ab5a0
                               at /Users/baishen/open/db/arrow/arrow2/src/compute/sort/lex_sort.rs:209:30
  18:        0x10d0f0d06 - arrow2::compute::sort::lex_sort::lexsort_to_indices::h6b3f553f0e340b39
                               at /Users/baishen/open/db/arrow/arrow2/src/compute/sort/lex_sort.rs:139:5
  19:        0x10d0f0b33 - arrow2::compute::sort::lex_sort::lexsort::h0733bc87c3c9e059
                               at /Users/baishen/open/db/arrow/arrow2/src/compute/sort/lex_sort.rs:64:19
  20:        0x10c3304bc - it::compute::sort::lex_sort::test_lex_sort_arrays::he3c3000dc95fb553
                               at /Users/baishen/open/db/arrow/arrow2/tests/it/compute/sort/lex_sort.rs:15:18
  21:        0x10c331903 - it::compute::sort::lex_sort::test_lex_sort_mixed_types::hbce0514756ff056a
                               at /Users/baishen/open/db/arrow/arrow2/tests/it/compute/sort/lex_sort.rs:47:5
  22:        0x10c64e5c1 - it::compute::sort::lex_sort::test_lex_sort_mixed_types::{{closure}}::ha40f0f463a05e8ba
                               at /Users/baishen/open/db/arrow/arrow2/tests/it/compute/sort/lex_sort.rs:24:1
  23:        0x10c9e65e1 - core::ops::function::FnOnce::call_once::hbbac487e9bfc5fbd
                               at /rustc/30b3f35c420694a4f24e5a4df00f06073f4f3a37/library/core/src/ops/function.rs:227:5
  24:        0x10d17e956 - core::ops::function::FnOnce::call_once::ha1ad185932737e6b
                               at /rustc/30b3f35c420694a4f24e5a4df00f06073f4f3a37/library/core/src/ops/function.rs:227:5
  25:        0x10d17e956 - test::__rust_begin_short_backtrace::h193a33ff0c687c70
                               at /rustc/30b3f35c420694a4f24e5a4df00f06073f4f3a37/library/test/src/lib.rs:575:5
  26:        0x10d17d850 - <alloc::boxed::Box<F,A> as core::ops::function::FnOnce<Args>>::call_once::heba70c93b2010364
                               at /rustc/30b3f35c420694a4f24e5a4df00f06073f4f3a37/library/alloc/src/boxed.rs:1854:9
  27:        0x10d17d850 - <core::panic::unwind_safe::AssertUnwindSafe<F> as core::ops::function::FnOnce<()>>::call_once::h87743e845dae1447
                               at /rustc/30b3f35c420694a4f24e5a4df00f06073f4f3a37/library/core/src/panic/unwind_safe.rs:271:9
  28:        0x10d17d850 - std::panicking::try::do_call::h59fb2879dd3d1c12
                               at /rustc/30b3f35c420694a4f24e5a4df00f06073f4f3a37/library/std/src/panicking.rs:492:40
  29:        0x10d17d850 - std::panicking::try::h61be9b3b15e615c6
                               at /rustc/30b3f35c420694a4f24e5a4df00f06073f4f3a37/library/std/src/panicking.rs:456:19
  30:        0x10d17d850 - std::panic::catch_unwind::hdf64eef90e5c45f1
                               at /rustc/30b3f35c420694a4f24e5a4df00f06073f4f3a37/library/std/src/panic.rs:137:14
  31:        0x10d17d850 - test::run_test_in_process::hc3ad1b70446ed286
                               at /rustc/30b3f35c420694a4f24e5a4df00f06073f4f3a37/library/test/src/lib.rs:598:18
  32:        0x10d17d850 - test::run_test::run_test_inner::{{closure}}::h27cf9538b9368c8f
                               at /rustc/30b3f35c420694a4f24e5a4df00f06073f4f3a37/library/test/src/lib.rs:492:39
  33:        0x10d1875da - test::run_test::run_test_inner::{{closure}}::h79f8ba7fa0d63b52
                               at /rustc/30b3f35c420694a4f24e5a4df00f06073f4f3a37/library/test/src/lib.rs:519:37
  34:        0x10d1875da - std::sys_common::backtrace::__rust_begin_short_backtrace::hd272823b95c33a1f
                               at /rustc/30b3f35c420694a4f24e5a4df00f06073f4f3a37/library/std/src/sys_common/backtrace.rs:122:18
  35:        0x10d153fdc - std::thread::Builder::spawn_unchecked_::{{closure}}::{{closure}}::he2f3d38f9e9d297b
                               at /rustc/30b3f35c420694a4f24e5a4df00f06073f4f3a37/library/std/src/thread/mod.rs:498:17
  36:        0x10d153fdc - <core::panic::unwind_safe::AssertUnwindSafe<F> as core::ops::function::FnOnce<()>>::call_once::hea6ef47267a429f0
                               at /rustc/30b3f35c420694a4f24e5a4df00f06073f4f3a37/library/core/src/panic/unwind_safe.rs:271:9
  37:        0x10d153fdc - std::panicking::try::do_call::h87a07cddc102e2af
                               at /rustc/30b3f35c420694a4f24e5a4df00f06073f4f3a37/library/std/src/panicking.rs:492:40
  38:        0x10d153fdc - std::panicking::try::hc09496e75be6ad7a
                               at /rustc/30b3f35c420694a4f24e5a4df00f06073f4f3a37/library/std/src/panicking.rs:456:19
  39:        0x10d153fdc - std::panic::catch_unwind::h7377f4cb22eed4a7
                               at /rustc/30b3f35c420694a4f24e5a4df00f06073f4f3a37/library/std/src/panic.rs:137:14
  40:        0x10d153fdc - std::thread::Builder::spawn_unchecked_::{{closure}}::h3c91847c248f543e
                               at /rustc/30b3f35c420694a4f24e5a4df00f06073f4f3a37/library/std/src/thread/mod.rs:497:30
  41:        0x10d153fdc - core::ops::function::FnOnce::call_once{{vtable.shim}}::h991416b5ad9ed3f7
                               at /rustc/30b3f35c420694a4f24e5a4df00f06073f4f3a37/library/core/src/ops/function.rs:227:5
  42:        0x10ecb0987 - <alloc::boxed::Box<F,A> as core::ops::function::FnOnce<Args>>::call_once::h03e49bb35a5f5755
                               at /rustc/30b3f35c420694a4f24e5a4df00f06073f4f3a37/library/alloc/src/boxed.rs:1854:9
  43:        0x10ecb0987 - <alloc::boxed::Box<F,A> as core::ops::function::FnOnce<Args>>::call_once::h2af1b5a036552068
                               at /rustc/30b3f35c420694a4f24e5a4df00f06073f4f3a37/library/alloc/src/boxed.rs:1854:9
  44:        0x10ecb0987 - std::sys::unix::thread::Thread::new::thread_start::h612b4a1852d138f9
                               at /rustc/30b3f35c420694a4f24e5a4df00f06073f4f3a37/library/std/src/sys/unix/thread.rs:108:17
  45:     0x7ff8076664e1 - __pthread_start
```

codecov[bot]: # [Codecov](https://codecov.io/gh/jorgecarleitao/arrow2/pull/1021?src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Jorge+Leitao) Report
> Merging [#1021](https://codecov.io/gh/jorgecarleitao/arrow2/pull/1021?src=pr&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Jorge+Leitao) (0da3e78) into [main](https://codecov.io/gh/jorgecarleitao/arrow2/commit/e976c1e8874082838460314dc304369cd4b29ee9?el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Jorge+Leitao) (e976c1e) will **increase** coverage by `0.00%`.
> The diff coverage is `100.00%`.

```diff
@@           Coverage Diff           @@
##             main    #1021   +/-   ##
=======================================
  Coverage   71.63%   71.64%           
=======================================
  Files         359      359           
  Lines       19904    19907    +3     
=======================================
+ Hits        14259    14262    +3     
  Misses       5645     5645           
```


| [Impacted Files](https://codecov.io/gh/jorgecarleitao/arrow2/pull/1021?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Jorge+Leitao) | Coverage Δ | |
|---|---|---|
| [src/compute/sort/lex\_sort.rs](https://codecov.io/gh/jorgecarleitao/arrow2/pull/1021/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Jorge+Leitao#diff-c3JjL2NvbXB1dGUvc29ydC9sZXhfc29ydC5ycw==) | `69.41% <100.00%> (+1.11%)` | :arrow_up: |
| [src/compute/arithmetics/time.rs](https://codecov.io/gh/jorgecarleitao/arrow2/pull/1021/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Jorge+Leitao#diff-c3JjL2NvbXB1dGUvYXJpdGhtZXRpY3MvdGltZS5ycw==) | `25.68% <0.00%> (-0.92%)` | :arrow_down: |
| [src/bitmap/utils/slice\_iterator.rs](https://codecov.io/gh/jorgecarleitao/arrow2/pull/1021/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Jorge+Leitao#diff-c3JjL2JpdG1hcC91dGlscy9zbGljZV9pdGVyYXRvci5ycw==) | `87.93% <0.00%> (+1.72%)` | :arrow_up: |

------

[Continue to review full report at Codecov](https://codecov.io/gh/jorgecarleitao/arrow2/pull/1021?src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Jorge+Leitao).
> **Legend** - [Click here to learn more](https://docs.codecov.io/docs/codecov-delta?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Jorge+Leitao)
> `Δ = absolute <relative> (impact)`, `ø = not affected`, `? = missing data`
> Powered by [Codecov](https://codecov.io/gh/jorgecarleitao/arrow2/pull/1021?src=pr&el=footer&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Jorge+Leitao). Last update [e976c1e...0da3e78](https://codecov.io/gh/jorgecarleitao/arrow2/pull/1021?src=pr&el=lastupdated&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Jorge+Leitao). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Jorge+Leitao).


Patch:
diff --git a/src/compute/sort/lex_sort.rs b/src/compute/sort/lex_sort.rs
index 114093f49a..c598cfd3ab 100644
--- a/src/compute/sort/lex_sort.rs
+++ b/src/compute/sort/lex_sort.rs
@@ -198,7 +198,12 @@ pub fn lexsort_to_indices_impl<I: Index>(
 
     if let Some(limit) = limit {
         let limit = limit.min(row_count);
-        let (before, _, _) = values.select_nth_unstable_by(limit, lex_comparator);
+        let before = if limit < row_count {
+            let (before, _, _) = values.select_nth_unstable_by(limit, lex_comparator);
+            before
+        } else {
+            &mut values[..]
+        };
         before.sort_unstable_by(lex_comparator);
         values.truncate(limit);
         values.shrink_to_fit();


Test patch:
diff --git a/tests/it/compute/sort/lex_sort.rs b/tests/it/compute/sort/lex_sort.rs
index bf0b146a8f..a24f116dc8 100644
--- a/tests/it/compute/sort/lex_sort.rs
+++ b/tests/it/compute/sort/lex_sort.rs
@@ -5,6 +5,13 @@ fn test_lex_sort_arrays(input: Vec<SortColumn>, expected: Vec<Box<dyn Array>>) {
     let sorted = lexsort::<i32>(&input, None).unwrap();
     assert_eq!(sorted, expected);
 
+    let sorted = lexsort::<i32>(&input, Some(4)).unwrap();
+    let expected = expected
+        .into_iter()
+        .map(|x| x.slice(0, 4))
+        .collect::<Vec<_>>();
+    assert_eq!(sorted, expected);
+
     let sorted = lexsort::<i32>(&input, Some(2)).unwrap();
     let expected = expected
         .into_iter()