rust reports cannot move out of dereference while templatizing a code

Question

The following code in Rust compiles fine:

pub fn insertion_sort(data : &mut [int]){
  let n  = data.len();
  for j in range(1, n){
    let key = data[j];
    // we insert data[j] into the sorted sequence 
    //data[0...j-1]
    let mut i = j -1;
    while data[i] > key{
        data[i + 1]  = data[i];
        if i == 0{
            break;
        }
        i -= 1;
    }
    data[i] = key;
  }
}

But the moment, I introduce generics as follows:

pub fn insertion_sort<T : Ord>(data : &mut [T]){
  let n  = data.len();
  for j in range(1, n){
    let key = data[j];
    // we insert data[j] into the sorted sequence 
    //data[0...j-1]
    let mut i = j -1;
    while data[i] > key{
        data[i + 1]  = data[i];
        if i == 0{
            break;
        }
        i -= 1;
    }
    data[i] = key;
  }
}

the compiler reports following problems:

error: cannot move out of dereference of &mut-pointer insertion.rs:6 let key = data[j];

error: cannot move out of dereference of &mut-pointer insertion.rs:11 data[i + 1] = data[i];

Do we need to take some special care while moving from a non-generic code for built-in types to generic code? The error messages sound quite cryptic.

[EDIT]

Based on Vladimir's advice below, I have attempted to come up with a version which can work for T : Ord using swap functions of a slice

pub fn insertion_sort<T : Ord>(data : &mut [T]){
  let n  = data.len();
  for j in range(1, n){
    // we insert data[j] into the sorted sequence 
    //data[0...j-1]
    let mut i = j -1;
    while data[i] > data[i+1]{
        data.swap(i + 1, i);
        if i == 0{
            break;
        }
        i -= 1;
    }
  }
}

Vladimir Matveev Vladimir Matveev · Accepted Answer · 2014-10-20T08:46:11

Yes, you need to take special care, because in the original piece of code you used int, which is implicitly copyable (implements Copy trait), and in the second piece you used generic parameter only with Ord bound. By default values in Rust are moved, not copied, and this does bring several limitations on what you can do with values. You can observe this if you write <T: Ord+Copy> instead of just <T: Ord> - your code will start compiling again. This is not a proper generic solution, however, because a lot of types are not Copy.

First of all, you should read the official Rust guide which explains, among everything else, ownership and borrowing, core Rust concepts which are absolutely required to be understood in order to use Rust efficiently. The error you see is a consequence of these concepts. Basically, if you have a reference into some data structure, you can't move anything out of this structure. Slice is a reference into a contiguous chunk of data; because you didn't specify Copy bound on T, Rust can't copy values from the slice, and it also can't move these values because moving from behind a reference is prohibited. So it emits an error.

Such behavior sounds restrictive, and sometimes it is. A lot of things which are done very naturally in other languages (mostly in C) can't be done in Rust directly. In return Rust provides immense safety guarantees. Sometimes, however, you do need to write something which is safe per se, but this safety isn't obvious to the compiler. This often happens when you implement fundamental data structures and algorithms, like sorting. The ultimate tool are unsafe blocks, of course, but in this case you won't need them. Rust provides several very useful functions in std::mem module, in particular, swap() and replace(). Specifically for slices, however, there is a method called swap() directly on slices. It swaps elements at given indices. If you reformulate insertion sort in terms of swap operation, you would be able to write completely generic code which would work for all Ord types even if they are not copyable. I strongly suggest you attempting this, as this would help you understand how low-level Rust programs are written.

On the other hand, if you know in advance that you would only work with primitive types, like int, you can safely put Copy bound on T and leave your code as it is. Or you can use more generic Clone bound, but then you would need to call clone() method when you extract values from slices:

pub fn insertion_sort<T: Ord+Clone>(data: &mut [T]) {
  let n = data.len();
  for j in range(1, n) {
    let key = data[j].clone();
    // we insert data[j] into the sorted sequence 
    //data[0...j-1]
    let mut i = j -1;
    while data[i] > key {
        data[i + 1] = data[i].clone();
        if i == 0 {
            break;
        }
        i -= 1;
    }
    data[i] = key;
  }
}

rust reports cannot move out of dereference while templatizing a code

2 Answers