How to map slices from vec, and then sort that vec based on that map

1

Ideally I'd like to do this all efficiently, without needing to clone things.

Here's a concrete example of what I'm trying to do.

First I have a list of of file paths:

test/
test/a
test/b
test/b/1
test/b/2
test/b/3

Modeled like this:

let mut items = vec![vec!["test"], vec!["test", "a"], vec!["test", "b"], vec!["test", "b", "1"], vec!["test", "b", "2"], vec!["test", "b", "3"]];

I would like to sort this list of paths by the number of items contained in the parent folder of each path item. So first I need to calculate the number of items in each "folder", I store those results in a map like this:

for each in items.iter() {
    let parent = &each[0..each.len() - 1];
    *map.entry(parent).or_insert(0) += 1;
}

And the resulting map looks like:

{
    []: 1, 
    ["test"]: 2, 
    ["test", "b"]: 3
}

Next I want to use this map to sort the collection of items. I'm trying to do that like this:

items.sort_unstable_by(|a, b| {
    let a_parent = &a[0..a.len() - 1];
    let b_parent = &b[0..b.len() - 1];
    map.get(a_parent).unwrap_or(&0).cmp(&map.get(b_parent).unwrap_or(&0))
});

But when I try that I'm running into borrowing problems saying "cannot borrow items as mutable because it is also borrowed as immutable". I think I generally understand why rust is complaining. But I also generally think that in this case the code is OK, I want to know how to get rust to also think that it's OK.

Here's full (non-working) code:

use std::collections::HashMap;

fn main() {
    let mut items = vec![vec!["test"], vec!["test", "a"], vec!["test", "b"], vec!["test", "b", "1"], vec!["test", "b", "2"], vec!["test", "b", "3"]];
    let mut map: HashMap<&[&str], usize> = HashMap::new();
    
    for each in items.iter() {
        let parent = &each[0..each.len() - 1];
        *map.entry(parent).or_insert(0) += 1;
    }

    items.sort_unstable_by(|a, b| {
        let a_parent = &a[0..a.len() - 1];
        let b_parent = &b[0..b.len() - 1];
        map.get(a_parent).unwrap_or(&0).cmp(&map.get(b_parent).unwrap_or(&0))
    });
    
    println!("{:?}", items);
    println!("{:?}", map);
}

(Playground)

Errors:

   Compiling playground v0.0.1 (file:///playground)
warning: unused import: `std::cmp::Ordering`
 --> src/main.rs:2:9
  |
2 |     use std::cmp::Ordering;
  |         ^^^^^^^^^^^^^^^^^^
  |
  = note: #[warn(unused_imports)] on by default

error[E0502]: cannot borrow `items` as mutable because it is also borrowed as immutable
  --> src/main.rs:13:9
   |
8  |         for each in items.iter() {
   |                     ----- immutable borrow occurs here
...
13 |         items.sort_unstable_by(|a, b| {
   |         ^^^^^ mutable borrow occurs here
...
21 |     }
   |     - immutable borrow ends here

error: aborting due to previous error

For more information about this error, try `rustc --explain E0502`.
error: Could not compile `playground`.

To learn more, run the command again with --verbose.
2

The bad news:

  • The type system is not expressive enough to express why this is valid.
  • Even NLL won't save you!

The good news:

  • You're correct; what you want to do is safe.
  • Rust does kinda support what you're trying to do, but you'll have to twist things a bit.

Consider one small adjustment:

// was
let mut items = vec![vec!["test"], vec!["test", "a"], vec!["test", "b"], ...];
// now
let mut items = vec![&["test"][..], &["test", "a"][..], &["test", "b"][..], ...];

or even better (to show that we aren't relying on 'static lifetimes):

fn foo(mut items: Vec<&[&str]>) {
    ...
}

This change is enough to make it compile. What happens is basically that:

  • Let's name some lifetimes. Consider the type of items to be Vec<&'a [&'b str]>. (Vec<Vec<&'b str>> in the original)
  • When you call items.iter(), items is implicitly borrowed; call this lifetime 'iter.
  • In the original code:
    • items has type Vec<&'b str>
    • each has type &'iter Vec<&'b str>
    • each[...] is an l-value of type Vec<&'b str>.
    • &each[...] has type &'iter Vec<&'b str>.
  • In the modified code:
    • items has type &'a [&'b str]
    • each has type &'iter &'a [&'b str]
    • each[...] first copies the &[T] to produce a temporary &'a [&'b str],
      which is then indexed to produce an l-value of type [&'b str]
    • &each[...] has type &'a [&'b str].

In the latter case, thanks to the Copy, the 'iter lifetime disappears from parent in much the same way that the 'a disappears from a &'a i32 when you dereference it to produce an i32.

1 Like
3

Thanks for your reply. I haven't digested it enough to ask any good questions, but will read it all again tomorrow. Thanks!