[rust-dev] Vectors, mutability & vec::dedup

Patrick Walton pwalton at mozilla.com
Tue Dec 18 16:45:34 PST 2012

On 12/17/12 10:53 PM, Tom Lee wrote:
> So here, though the data type of the RHS is immutable, the underlying
> memory is /not/ because the "owner" of that memory is mutable?

More or less, yes. An ownership path is any path that is either flat in 
memory or involves ~ pointers.

Since having two sources of mutability is confusing, we've talked about 
getting rid of mutability in the type, and making mutability *only* a 
property of the owner.

> Are you talking about something like this?
>     // x is the owner & thus the underlying memory is mutable.
>     let mut x = ~[1, 2, 3];
>     x[0] = 10;                   // ok, x[0] is reassigned
>     // y is the owner & the underlying memory is now immutable.
>     let y = move x;
>     y[0] = 10;           // compile time error: y is immutable.


> Okay, I think that answers a few of my questions. I'm guessing when you
> talk about mutability being "inherited" here, you're referring to the
> fact the type system will enforce things like borrowed pointers?
> Something like:
>     let mut x = ~[1, 2, 3];
>     foo(&mut x);               // ok: x is mutable, mutable borrowed pointer
>     let mut y = ~[4, 5, 6];
>     foo(&mut y);               // compile error: y is immutable, but we
>     want a mutable borrowed pointer

(I assume you mean "let y = ..." here)

> I think that makes sense. The only question I'd have here is why we need
> to be specific about whether the borrowed pointer is immutable or not?
> Couldn't it be inferred from the underlying variable? What do we gain by
> being explicit?

The kind of pointer you take can actually be different from the 
mutability of the underlying type. This may sound strange, but it's 
actually really important for usability, as it allows you to do things 
like iterate over a mutable hash table with `each`. This code compiles:

     use core::*;

     fn main() {
         let mut mymap = send_map::linear::LinearMap();
         mymap.insert(~"foo", ~"bar");
         mymap.insert(~"baz", ~"boo");
         for mymap.each |&key, &value| {
             io::println(key + ~"=" + value);

Notice that the signatures of `LinearMap::each()` and 
`LinearMap::insert()` are as follows:

     // Mutable self:
     fn insert(&mut self, k: K, +v: V) -> bool;

     // Immutable self:
     pure fn each(&self, blk: fn(k: &K, v: &V) -> bool);

There are several things to note here:

* Method call syntax causes the compiler to choose the right type of 
pointer for the `self` parameter automatically.

* `each` takes an immutable pointer. You might ask why it doesn't take a 
`const` pointer (`const` being the supertype of immutable and mutable), 
or why there isn't an `each_mut` for mutable hash tables. The reason is 
that it's unsafe to mutate a hash table while you iterate over it. With 
a garbage collector, doing so merely results in unpredictable behavior; 
without one, it results in crashes and segfaults. So we forbid this 
entirely in Rust with the type system--you cannot mutate a container 
while you iterate over it.

* This raises the question of how it can possibly be safe to take an 
immutable pointer to something that's mutable. This is where *borrowing* 
comes in. Taking a pointer to a uniquely owned variable *borrows* that 
variable--you cannot access the original variable in any way that would 
cause the pointers you created to become invalid. In this case, since we 
created an immutable pointer to the hash table with the call to 
`LinearMap::each()`, we cannot violate the guarantee of immutability by 
mutating the hash table while that pointer exists. The compiler enforces 
this. For example, if I try to mutate the hash table inside the loop:

     use core::*;

     fn main() {
         let mut mymap = send_map::linear::LinearMap();
         mymap.insert(~"foo", ~"bar");
         mymap.insert(~"baz", ~"boo");
         for mymap.each |&key, &value| {
             mymap.insert(~"quux", ~"qux");

I get the following error:

     test2.rs:8:12: 8:17 error: loan of mutable local variable as 
mutable conflicts with prior loan
     test2.rs:8             mymap.insert(~"quux", ~"qux");
     test2.rs:7:12: 7:17 note: prior loan as immutable granted here
     test2.rs:7         for mymap.each |&key, &value| {

As you can see, the compiler is complaining that I have an immutable 
*loan* of the variable `mymap` (where a "loan" basically means "a 
pointer that I've created"), but I tried to mutate the hash map, 
violating the rule that immutable pointers must point to immutable data.

So, to answer your question: For convenience's sake, the mutability of 
your pointer may differ from the mutability of the object, as long as 
the compiler can prove that you aren't doing anything illogical. In 
general, we don't know which kind of pointer you want, since in many 
cases a value may legally be pointed to by either an immutable or a 
mutable pointer. So, with the exception of method calls, we require that 
you be explicit about mutability of pointers.


More information about the Rust-dev mailing list