Repository: nushell/nushell (language: rust)

Issue:
Fuzzy completion panics on `lines <Tab>`
### Describe the bug

It appears that some recent changes have introduced panics/OOB memory access attempt in the completion logic (the actual panic itself occurs in `reedline`, but I'm unsure of the cause). The ***bug*** (causing the panic) may be in nu, or reedline. It seems to only occur with fuzzy completion enabled. The bug is not present on `v0.101.0`.

### How to reproduce

With latest commit of `main` checked-out, run:

```nu
RUST_BACKTRACE=full cargo run -- -n -e '$env.config.completions.algorithm = "fuzzy"'
```

Then type (note the space character):

```nu
lines <Tab>
```

...using `Tab` to trigger completion.

The panic also occurs on `lines<Tab> `.

Note that this panic also occurs with some other commands/command-lines as well (e.g. `print<Tab> `).

### Expected behavior

shouldn't panic, reedline shouldn't reload (losing entered command-line), etc.

### Configuration

`$env.config.completions.algorithm = "fuzzy"`

---

| key                | value                                                             |
| ------------------ | ----------------------------------------------------------------- |
| version            | 0.101.1                                                           |
| major              | 0                                                                 |
| minor              | 101                                                               |
| patch              | 1                                                                 |
| branch             | main                                                              |
| commit_hash        | 3f5ebd75b6e1506f06509bc29a4807be1bc25049                          |
| build_os           | macos-aarch64                                                     |
| build_target       | aarch64-apple-darwin                                              |
| rust_version       | rustc 1.83.0 (90b35a623 2024-11-26) (built from a source tarball) |
| cargo_version      | cargo 1.83.0 (5ffbef321 2024-10-29)                               |
| build_time         | 2025-01-18 10:33:47 -08:00                                        |
| build_rust_channel | debug                                                             |
| allocator          | mimalloc                                                          |
| features           | default, sqlite, trash                                            |
| installed_plugins  |                                                                   |
Fuzzy completion panics on `lines <Tab>`
### Describe the bug

It appears that some recent changes have introduced panics/OOB memory access attempt in the completion logic (the actual panic itself occurs in `reedline`, but I'm unsure of the cause). The ***bug*** (causing the panic) may be in nu, or reedline. It seems to only occur with fuzzy completion enabled. The bug is not present on `v0.101.0`.

### How to reproduce

With latest commit of `main` checked-out, run:

```nu
RUST_BACKTRACE=full cargo run -- -n -e '$env.config.completions.algorithm = "fuzzy"'
```

Then type (note the space character):

```nu
lines <Tab>
```

...using `Tab` to trigger completion.

The panic also occurs on `lines<Tab> `.

Note that this panic also occurs with some other commands/command-lines as well (e.g. `print<Tab> `).

### Expected behavior

shouldn't panic, reedline shouldn't reload (losing entered command-line), etc.

### Configuration

`$env.config.completions.algorithm = "fuzzy"`

---

| key                | value                                                             |
| ------------------ | ----------------------------------------------------------------- |
| version            | 0.101.1                                                           |
| major              | 0                                                                 |
| minor              | 101                                                               |
| patch              | 1                                                                 |
| branch             | main                                                              |
| commit_hash        | 3f5ebd75b6e1506f06509bc29a4807be1bc25049                          |
| build_os           | macos-aarch64                                                     |
| build_target       | aarch64-apple-darwin                                              |
| rust_version       | rustc 1.83.0 (90b35a623 2024-11-26) (built from a source tarball) |
| cargo_version      | cargo 1.83.0 (5ffbef321 2024-10-29)                               |
| build_time         | 2025-01-18 10:33:47 -08:00                                        |
| build_rust_channel | debug                                                             |
| allocator          | mimalloc                                                          |
| features           | default, sqlite, trash                                            |
| installed_plugins  |                                                                   |


Discussion / hints:
Panic occurs here: https://github.com/nushell/reedline/blob/abb5c08d79b6e42826c32dbd4f4bef178efff1fb/src/menu/columnar_menu.rs#L304-L305

<details><summary>Backtrace</summary>
<p>

```
Error:                                                                                                                                                                     01/23/2025 07:42:56 PM
  × Main thread panicked.he given values to stdout.
  ├─▶ at /private/tmp/nix-build-rustc-1.83.0.drv-0/rustc-1.83.0-src/library/core/src/str/mod.rs:644:21                                                                                                  
  ╰─▶ byte index 6 is out of bounds of `print`                                                                                                                                                          
         0: 0x102c51bcc - _rust_begin_unwind                                                                                                                                                            
         1: 0x102cfb180 - core::panicking::panic_fmt::h43c21d3ca19f8fab                                                                                                                                 
         2: 0x102c8c9b8 - core::str::slice_error_fail_rt::h57a5dde695d17ada                                                                                                                             
         3: 0x102cfaf2c - core::str::slice_error_fail::hfa13f66bec142c98                                                                                                                                
         4: 0x101806908 - core::str::<impl str>::split_at::hc5911bf5ba36a33e                                                                                                                            
                      at /private/tmp/nix-build-rustc-1.83.0.drv-0/rustc-1.83.0-src/library/core/src/str/mod.rs:644                                                                                     
         5: 0x1017fb088 - reedline::menu::columnar_menu::ColumnarMenu::create_string::h30836facbc242035                                                                                                 
                      at */.cargo/registry/src/index.crates.io-6f17d22bba15001f/reedline-0.38.0/src/menu/columnar_menu.rs:305                                                          
         6: 0x1017ff774 - <reedline::menu::columnar_menu::ColumnarMenu as reedline::menu::Menu>::menu_string::{{closure}}::h23228335f5dbcdfe
                      at */.cargo/registry/src/index.crates.io-6f17d22bba15001f/reedline-0.38.0/src/menu/columnar_menu.rs:659
         7: 0x1017f2484 - core::ops::function::impls::<impl core::ops::function::FnOnce<A> for &mut F>::call_once::h548e336bc13e34cb
                      at /private/tmp/nix-build-rustc-1.83.0.drv-0/rustc-1.83.0-src/library/core/src/ops/function.rs:305
         8: 0x101861a98 - core::option::Option<T>::map::hc952370e9f3391b4
                      at /private/tmp/nix-build-rustc-1.83.0.drv-0/rustc-1.83.0-src/library/core/src/option.rs:1113
                       - <core::iter::adapters::map::Map<I,F> as core::iter::traits::iterator::Iterator>::next::hfd00f0f85ad8742f
                      at /private/tmp/nix-build-rustc-1.83.0.drv-0/rustc-1.83.0-src/library/core/src/iter/adapters/map.rs:107
         9: 0x10182343c - <alloc::string::String as core::iter::traits::collect::FromIterator<alloc::string::String>>::from_iter::h61ff3f041140a257
                      at /private/tmp/nix-build-rustc-1.83.0.drv-0/rustc-1.83.0-src/library/alloc/src/string.rs:2264
        10: 0x101863470 - core::iter::traits::iterator::Iterator::collect::h754be89423169910
                      at /private/tmp/nix-build-rustc-1.83.0.drv-0/rustc-1.83.0-src/library/core/src/iter/traits/iterator.rs:2001
        11: 0x1017ff634 - <reedline::menu::columnar_menu::ColumnarMenu as reedline::menu::Menu>::menu_string::h861cac0eb15c6ea9
                      at */.cargo/registry/src/index.crates.io-6f17d22bba15001f/reedline-0.38.0/src/menu/columnar_menu.rs:648
        12: 0x101860818 - <reedline::menu::ReedlineMenu as reedline::menu::Menu>::menu_string::h7b2c00a6add9dd04
                      at */.cargo/registry/src/index.crates.io-6f17d22bba15001f/reedline-0.38.0/src/menu/mod.rs:457
        13: 0x10189de40 - reedline::painting::painter::Painter::print_menu::h35a357fe5c3fef3d
                      at */.cargo/registry/src/index.crates.io-6f17d22bba15001f/reedline-0.38.0/src/painting/painter.rs:318
        14: 0x10189e55c - reedline::painting::painter::Painter::print_small_buffer::hf46490e592e13a9f
                      at */.cargo/registry/src/index.crates.io-6f17d22bba15001f/reedline-0.38.0/src/painting/painter.rs:370
        15: 0x10189d498 - reedline::painting::painter::Painter::repaint_buffer::h68cd89e5c74c8bc8
                      at */.cargo/registry/src/index.crates.io-6f17d22bba15001f/reedline-0.38.0/src/painting/painter.rs:245
        16: 0x10185091c - reedline::engine::Reedline::buffer_paint::h27576dceec2c98c1
                      at */.cargo/registry/src/index.crates.io-6f17d22bba15001f/reedline-0.38.0/src/engine.rs:1814
        17: 0x10184e4e8 - reedline::engine::Reedline::repaint::h0d0de190d2767715
                      at */.cargo/registry/src/index.crates.io-6f17d22bba15001f/reedline-0.38.0/src/engine.rs:1516
        18: 0x101849c40 - reedline::engine::Reedline::read_line_helper::h6d8b60b78b158f8c
                      at */.cargo/registry/src/index.crates.io-6f17d22bba15001f/reedline-0.38.0/src/engine.rs:805
        19: 0x101849240 - reedline::engine::Reedline::read_line::h01b81463db9f1c7a
                      at */.cargo/registry/src/index.crates.io-6f17d22bba15001f/reedline-0.38.0/src/engine.rs:650
        20: 0x1016ce36c - nu_cli::repl::loop_iteration::h715c38979dee572c
                      at */code/nushell/crates/nu-cli/src/repl.rs:483
        21: 0x101693608 - nu_cli::repl::evaluate_repl::{{closure}}::hfce0390a6f8cfd62
                      at */code/nushell/crates/nu-cli/src/repl.rs:185
        22: 0x10170c544 - <core::panic::unwind_safe::AssertUnwindSafe<F> as core::ops::function::FnOnce<()>>::call_once::h167121954b04c777
                      at /private/tmp/nix-build-rustc-1.83.0.drv-0/rustc-1.83.0-src/library/core/src/panic/unwind_safe.rs:272
        23: 0x10170239c - std::panicking::try::do_call::hb8537541786309fd
                      at /private/tmp/nix-build-rustc-1.83.0.drv-0/rustc-1.83.0-src/library/std/src/panicking.rs:557
        24: 0x101720c58 - ___rust_try
        25: 0x101720ba4 - std::panicking::try::he76130db89fafe60
                      at /private/tmp/nix-build-rustc-1.83.0.drv-0/rustc-1.83.0-src/library/std/src/panicking.rs:520
                       - std::panic::catch_unwind::h894c2d5483e416db
```

</p>
</details> 
I think it's introduced by #14846
@ysthakur when you have time, would you please look into this? It may have something to do with the recent nucleo changes.
Looks like the cause is that if you give the pattern `"lines "` to Nucleo (with a space at the end), Nucleo will try to split that into words and match only `"lines"`, which means that `lines` will be one of the suggestions. There are a couple different ways to fix it, but I think the safest would be to make the needle a single [`Atom`](https://docs.rs/nucleo-matcher/0.3.1/nucleo_matcher/pattern/struct.Atom.html) rather than letting Nucleo split it into multiple words.
> Looks like the cause is that if you give the pattern `"lines "` to Nucleo (with a space at the end), Nucleo will try to split that into words and match only `"lines"`, which means that `lines` will be one of the suggestions. There are a couple different ways to fix it, but I think the safest would be to make the needle a single [`Atom`](https://docs.rs/nucleo-matcher/0.3.1/nucleo_matcher/pattern/struct.Atom.html) rather than letting Nucleo split it into multiple words.

I didn't do a lot of research, but the reedline code  seems not correct for fuzzy matcher? It highlights the wrong parts in nu 101 with skim.

A different story, we probably need to fix both of them.
Panic occurs here: https://github.com/nushell/reedline/blob/abb5c08d79b6e42826c32dbd4f4bef178efff1fb/src/menu/columnar_menu.rs#L304-L305

<details><summary>Backtrace</summary>
<p>

```
Error:                                                                                                                                                                     01/23/2025 07:42:56 PM
  × Main thread panicked.he given values to stdout.
  ├─▶ at /private/tmp/nix-build-rustc-1.83.0.drv-0/rustc-1.83.0-src/library/core/src/str/mod.rs:644:21                                                                                                  
  ╰─▶ byte index 6 is out of bounds of `print`                                                                                                                                                          
         0: 0x102c51bcc - _rust_begin_unwind                                                                                                                                                            
         1: 0x102cfb180 - core::panicking::panic_fmt::h43c21d3ca19f8fab                                                                                                                                 
         2: 0x102c8c9b8 - core::str::slice_error_fail_rt::h57a5dde695d17ada                                                                                                                             
         3: 0x102cfaf2c - core::str::slice_error_fail::hfa13f66bec142c98                                                                                                                                
         4: 0x101806908 - core::str::<impl str>::split_at::hc5911bf5ba36a33e                                                                                                                            
                      at /private/tmp/nix-build-rustc-1.83.0.drv-0/rustc-1.83.0-src/library/core/src/str/mod.rs:644                                                                                     
         5: 0x1017fb088 - reedline::menu::columnar_menu::ColumnarMenu::create_string::h30836facbc242035                                                                                                 
                      at */.cargo/registry/src/index.crates.io-6f17d22bba15001f/reedline-0.38.0/src/menu/columnar_menu.rs:305                                                          
         6: 0x1017ff774 - <reedline::menu::columnar_menu::ColumnarMenu as reedline::menu::Menu>::menu_string::{{closure}}::h23228335f5dbcdfe
                      at */.cargo/registry/src/index.crates.io-6f17d22bba15001f/reedline-0.38.0/src/menu/columnar_menu.rs:659
         7: 0x1017f2484 - core::ops::function::impls::<impl core::ops::function::FnOnce<A> for &mut F>::call_once::h548e336bc13e34cb
                      at /private/tmp/nix-build-rustc-1.83.0.drv-0/rustc-1.83.0-src/library/core/src/ops/function.rs:305
         8: 0x101861a98 - core::option::Option<T>::map::hc952370e9f3391b4
                      at /private/tmp/nix-build-rustc-1.83.0.drv-0/rustc-1.83.0-src/library/core/src/option.rs:1113
                       - <core::iter::adapters::map::Map<I,F> as core::iter::traits::iterator::Iterator>::next::hfd00f0f85ad8742f
                      at /private/tmp/nix-build-rustc-1.83.0.drv-0/rustc-1.83.0-src/library/core/src/iter/adapters/map.rs:107
         9: 0x10182343c - <alloc::string::String as core::iter::traits::collect::FromIterator<alloc::string::String>>::from_iter::h61ff3f041140a257
                      at /private/tmp/nix-build-rustc-1.83.0.drv-0/rustc-1.83.0-src/library/alloc/src/string.rs:2264
        10: 0x101863470 - core::iter::traits::iterator::Iterator::collect::h754be89423169910
                      at /private/tmp/nix-build-rustc-1.83.0.drv-0/rustc-1.83.0-src/library/core/src/iter/traits/iterator.rs:2001
        11: 0x1017ff634 - <reedline::menu::columnar_menu::ColumnarMenu as reedline::menu::Menu>::menu_string::h861cac0eb15c6ea9
                      at */.cargo/registry/src/index.crates.io-6f17d22bba15001f/reedline-0.38.0/src/menu/columnar_menu.rs:648
        12: 0x101860818 - <reedline::menu::ReedlineMenu as reedline::menu::Menu>::menu_string::h7b2c00a6add9dd04
                      at */.cargo/registry/src/index.crates.io-6f17d22bba15001f/reedline-0.38.0/src/menu/mod.rs:457
        13: 0x10189de40 - reedline::painting::painter::Painter::print_menu::h35a357fe5c3fef3d
                      at */.cargo/registry/src/index.crates.io-6f17d22bba15001f/reedline-0.38.0/src/painting/painter.rs:318
        14: 0x10189e55c - reedline::painting::painter::Painter::print_small_buffer::hf46490e592e13a9f
                      at */.cargo/registry/src/index.crates.io-6f17d22bba15001f/reedline-0.38.0/src/painting/painter.rs:370
        15: 0x10189d498 - reedline::painting::painter::Painter::repaint_buffer::h68cd89e5c74c8bc8
                      at */.cargo/registry/src/index.crates.io-6f17d22bba15001f/reedline-0.38.0/src/painting/painter.rs:245
        16: 0x10185091c - reedline::engine::Reedline::buffer_paint::h27576dceec2c98c1
                      at */.cargo/registry/src/index.crates.io-6f17d22bba15001f/reedline-0.38.0/src/engine.rs:1814
        17: 0x10184e4e8 - reedline::engine::Reedline::repaint::h0d0de190d2767715
                      at */.cargo/registry/src/index.crates.io-6f17d22bba15001f/reedline-0.38.0/src/engine.rs:1516
        18: 0x101849c40 - reedline::engine::Reedline::read_line_helper::h6d8b60b78b158f8c
                      at */.cargo/registry/src/index.crates.io-6f17d22bba15001f/reedline-0.38.0/src/engine.rs:805
        19: 0x101849240 - reedline::engine::Reedline::read_line::h01b81463db9f1c7a
                      at */.cargo/registry/src/index.crates.io-6f17d22bba15001f/reedline-0.38.0/src/engine.rs:650
        20: 0x1016ce36c - nu_cli::repl::loop_iteration::h715c38979dee572c
                      at */code/nushell/crates/nu-cli/src/repl.rs:483
        21: 0x101693608 - nu_cli::repl::evaluate_repl::{{closure}}::hfce0390a6f8cfd62
                      at */code/nushell/crates/nu-cli/src/repl.rs:185
        22: 0x10170c544 - <core::panic::unwind_safe::AssertUnwindSafe<F> as core::ops::function::FnOnce<()>>::call_once::h167121954b04c777
                      at /private/tmp/nix-build-rustc-1.83.0.drv-0/rustc-1.83.0-src/library/core/src/panic/unwind_safe.rs:272
        23: 0x10170239c - std::panicking::try::do_call::hb8537541786309fd
                      at /private/tmp/nix-build-rustc-1.83.0.drv-0/rustc-1.83.0-src/library/std/src/panicking.rs:557
        24: 0x101720c58 - ___rust_try
        25: 0x101720ba4 - std::panicking::try::he76130db89fafe60
                      at /private/tmp/nix-build-rustc-1.83.0.drv-0/rustc-1.83.0-src/library/std/src/panicking.rs:520
                       - std::panic::catch_unwind::h894c2d5483e416db
```

</p>
</details> 
I think it's introduced by #14846
@ysthakur when you have time, would you please look into this? It may have something to do with the recent nucleo changes.
Looks like the cause is that if you give the pattern `"lines "` to Nucleo (with a space at the end), Nucleo will try to split that into words and match only `"lines"`, which means that `lines` will be one of the suggestions. There are a couple different ways to fix it, but I think the safest would be to make the needle a single [`Atom`](https://docs.rs/nucleo-matcher/0.3.1/nucleo_matcher/pattern/struct.Atom.html) rather than letting Nucleo split it into multiple words.
> Looks like the cause is that if you give the pattern `"lines "` to Nucleo (with a space at the end), Nucleo will try to split that into words and match only `"lines"`, which means that `lines` will be one of the suggestions. There are a couple different ways to fix it, but I think the safest would be to make the needle a single [`Atom`](https://docs.rs/nucleo-matcher/0.3.1/nucleo_matcher/pattern/struct.Atom.html) rather than letting Nucleo split it into multiple words.

I didn't do a lot of research, but the reedline code  seems not correct for fuzzy matcher? It highlights the wrong parts in nu 101 with skim.

A different story, we probably need to fix both of them.

Fix patch:
diff --git a/crates/nu-cli/src/completions/completion_options.rs b/crates/nu-cli/src/completions/completion_options.rs
index 58fea194ec766..cbe119e2c1742 100644
--- a/crates/nu-cli/src/completions/completion_options.rs
+++ b/crates/nu-cli/src/completions/completion_options.rs
@@ -2,7 +2,7 @@ use nu_parser::trim_quotes_str;
 use nu_protocol::{CompletionAlgorithm, CompletionSort};
 use nu_utils::IgnoreCaseExt;
 use nucleo_matcher::{
-    pattern::{AtomKind, CaseMatching, Normalization, Pattern},
+    pattern::{Atom, AtomKind, CaseMatching, Normalization},
     Config, Matcher, Utf32Str,
 };
 use std::{borrow::Cow, fmt::Display};
@@ -38,9 +38,9 @@ enum State<T> {
     },
     Fuzzy {
         matcher: Matcher,
-        pat: Pattern,
+        atom: Atom,
         /// Holds (haystack, item, score)
-        items: Vec<(String, T, u32)>,
+        items: Vec<(String, T, u16)>,
     },
 }
 
@@ -65,7 +65,7 @@ impl<T> NuMatcher<T> {
                 }
             }
             MatchAlgorithm::Fuzzy => {
-                let pat = Pattern::new(
+                let atom = Atom::new(
                     needle,
                     if options.case_sensitive {
                         CaseMatching::Respect
@@ -74,13 +74,14 @@ impl<T> NuMatcher<T> {
                     },
                     Normalization::Smart,
                     AtomKind::Fuzzy,
+                    false,
                 );
                 NuMatcher {
                     options,
                     needle: needle.to_owned(),
                     state: State::Fuzzy {
                         matcher: Matcher::new(Config::DEFAULT),
-                        pat,
+                        atom,
                         items: Vec::new(),
                     },
                 }
@@ -115,13 +116,13 @@ impl<T> NuMatcher<T> {
             }
             State::Fuzzy {
                 matcher,
-                pat,
+                atom,
                 items,
             } => {
                 let mut haystack_buf = Vec::new();
                 let haystack_utf32 = Utf32Str::new(trim_quotes_str(haystack), &mut haystack_buf);
                 let mut indices = Vec::new();
-                let Some(score) = pat.indices(haystack_utf32, matcher, &mut indices) else {
+                let Some(score) = atom.indices(haystack_utf32, matcher, &mut indices) else {
                     return false;
                 };
                 if let Some(item) = item {
@@ -292,4 +293,22 @@ mod test {
         // Sort by score, then in alphabetical order
         assert_eq!(vec!["fob", "foo bar", "foo/bar"], matcher.results());
     }
+
+    #[test]
+    fn match_algorithm_fuzzy_sort_strip() {
+        let options = CompletionOptions {
+            match_algorithm: MatchAlgorithm::Fuzzy,
+            ..Default::default()
+        };
+        let mut matcher = NuMatcher::new("'love spaces' ", options);
+        for item in [
+            "'i love spaces'",
+            "'i love spaces' so much",
+            "'lovespaces' ",
+        ] {
+            matcher.add(item, item);
+        }
+        // Make sure the spaces are respected
+        assert_eq!(vec!["'i love spaces' so much"], matcher.results());
+    }
 }


Test patch:
diff --git a/crates/nu-cli/tests/completions/mod.rs b/crates/nu-cli/tests/completions/mod.rs
index fc2cc160b3727..c8a3ea6d84074 100644
--- a/crates/nu-cli/tests/completions/mod.rs
+++ b/crates/nu-cli/tests/completions/mod.rs
@@ -1038,8 +1038,8 @@ fn subcommand_completions() {
     match_suggestions(
         &vec![
             "food bar".to_string(),
-            "foo-test-command aagap bcr".to_string(),
             "foo-test-command bar".to_string(),
+            "foo-test-command aagap bcr".to_string(),
         ],
         &suggestions,
     );