DEV Community

pintuch
pintuch

Posted on

Rust - nth element

I am new to Rust and have skimmed through most of the chapters of the Rust Book. However, to get some programming practice, I decided to work through few of the 99 scheme problems. The subject of this post is the third problem on that list.

// nth returns an optional value to the nth element
// of the list. The value of n indicates the position
// (= index + 1).

fn nth<T>(xs: &[T], n: usize) -> Option<T> {
    if (n < 1) || n > xs.len() {
        None
    } else {
        Some(xs[n-1])
    }
}
Enter fullscreen mode Exit fullscreen mode

The code above was my first attempt at the problem. Well, how hard could indexing into a slice be? I had already checked the following worked.

let xs = &["he", "el", "lo"];
println!("{}", xs[0]); // he is printed out
Enter fullscreen mode Exit fullscreen mode

But, to my surprise, the Rust compiler was unhappy.

error[E0508]: cannot move out of type `[T]`, a non-copy slice
  --> src/main.rs:18:14
   |
18 |         Some(xs[n-1])
   |              ^^^^^^^
   |              |
   |              cannot move out of here
   |              move occurs because `xs[_]` has type `T`, which does not implement the `Copy` trait

error: aborting due to previous error

For more information about this error, try `rustc --explain E0508`.

Enter fullscreen mode Exit fullscreen mode

The way I interpret the error is that in the absence of a borrow, the indexed value either gets copied or moved out of the slice. The former isn't an option since the generic type T doesn't implement the Copy trait by default. And, I guess, for the latter to work, you'd need to give up the ownership of the value in that position, almost creating a hole in the slice which would be awkward. One could also argue maybe giving up the ownership of the entire slice is a decent compromise that works around the problem of leaving holes. But, then that means you can't de-allocate the rest of the slice anymore as long as the indexed value is in scope. I'm not sure if this was the reason behind the current behavior.

So, to fix, i could try taking a reference or constrain my slice to types that implement the Copy trait. Sure enough, the following code compiles:

// Option<&T> works
fn nth<T>(xs: &[T], n: usize) -> Option<&T> {
    if n < 1 || n > xs.len() {
        None
    }
    else{
        Some(&xs[n-1])
    }
}
Enter fullscreen mode Exit fullscreen mode

And so does this too:

// <T: Copy> works
fn nth<T: Copy>(xs: &[T], n: usize) -> Option<T> {
    if n < 1 || n > xs.len() {
        None
    }
    else{
        Some(xs[n-1])
    }
}
Enter fullscreen mode Exit fullscreen mode

So, what explains this?

let xs = &["he", "el", "lo"]; // xs: &[&str]
println!("{}", xs[0]);
Enter fullscreen mode Exit fullscreen mode

&str is a shared/immutable reference to the static data. Copying the reference should be cheap enough and since it doesn't own the literal slice itself, it should be safe. It's expected that it follows Copy semantics.

But what about String types? Would we run into trouble since String is a pointer to owned heap-allocated data and copying the pointer would simply create two owners to the same piece of data (causing double-free)? Since that can't happen, printing an indexed value from a slice of String values should fail to compile, right?

let xs = &["he", "el", "lo"];
let ys = &[String::from("he"), String::from("el"), String::from("lo")];

println!("{}", xs[0]);
println!("{}", ys[0]);
Enter fullscreen mode Exit fullscreen mode

The code above compiles. However, this doesn't:

let xs = &["he", "el", "lo"];
let x: &str = xs[0];

let ys = &[String::from("he"), String::from("el"), String::from("lo")];
let y: String = ys[0];

println!("{}", xs[0]);
println!("{}", ys[0]);

Enter fullscreen mode Exit fullscreen mode
error[E0508]: cannot move out of type `[std::string::String; 3]`, a non-copy array
  --> src/main.rs:50:21
   |
50 |     let y: String = ys[0];
   |                     ^^^^^
   |                     |
   |                     cannot move out of here
   |                     move occurs because `ys[_]` has type `std::string::String`, which does not implement the `Copy` trait
   |                     help: consider borrowing here: `&ys[0]`

error: aborting due to previous error; 2 warnings emitted

For more information about this error, try `rustc --explain E0508`.
Enter fullscreen mode Exit fullscreen mode

It turns out println! macro has a special behavior. It borrows the value being formatted implicitly, which is why we never see those 'move out of type' errors.

References:

Discussion (0)