[back]
A Familar Pointer With A Rusty Twist
modified: 2015-03-22 04:22:15

1. A Familar Pointer With A Rusty Twist
1.1. Brief Explanation Of Concurrency
1.2. Rust Major Pointer Types
1.3. Preferred Previous Experience
1.4. Simple Variable And Reference Declarations
1.5. Data Structures
1.5.1. Illegal Recursive Type
1.5.2. Legal Recursive Type But Not Possible To Use
1.5.3. Using The Option<T>
1.5.4. Introduction To Box<T>
1.5.5. Box<T> Limitations, Copy, And Clone
1.5.6. Introduction To Rc<T>
1. A Familar Pointer With A Rusty Twist

If you are here because you need help with pointers in Rust then you have come to the right place. There is a lot of information out there covering pointers, but sometimes you just need to see things from a different perspective. I hope this perspective is as close to the level of what one would consider a pointer laymen. I hope you have experience with pointers in another language and that you are familar with concurrency, threads, and processes, however if you are not then I will try to give you a quick crash course and for those of you that are a little fuzzy and hopefully I will refresh your memory and not make things more confusing!

1.1. Brief Explanation Of Concurrency

I must make a quote, "In programming, concurrency is the composition of independently executing processes, while parallelism is the simultaneous execution of (possibly related) computations." In the following paragraphs I use the word concurrency to mean both. You should however be aware that it is incorrect and instead understand the meaning of both. Just read concurrency (in the following paragraphs) as concurrency/parallelism.

The word concurrency when used here referes to multiple program executions happening at the same time either on different cores on the same chip, different cpus on the same motherboard, or on a single CPU. A twist is if using a single CPU then they are not actually accuring simultaneously but rather each program execution is occuring in a time sharing manner. I think it is important that you have a basic understanding of this concept. On a single CPU (core) system using a very simple operating system there is a timer that interrupts the CPU after a certain amount of time which causes the CPU to save it's current execution state then load a new execution state and start back executing. This occurs continously many times a second. If you have five programs running then you could imagine the CPU switching five times each second. On each switch it loads the next program's execution state onto the CPU and lets the program run for say 1/5th of a second, then it saves the state of the current program and loads the next, and this repeats. This gives the illusion of many programs running at once. The actual way in which the program state is saved is beyond this guide. However, programs actually may have more than one execution state (also called the thread). I will explain threads and processes (programs) in the following paragraph. Also, in modern operating systems the rate at which switching occurs is fast enough to allow programs to run many times per second and can be variable depending on the OS scheduler implementation.

In modern operating systems you have two major parts to concurrency that you need to know and understand at the moment. There are other major parts that we will get into a little later. There is an process and an thread. Each thread lives under a process. Each program runs as a separate process from other programs, however each process may have one or more threads. The important part is to understand that each thread under a process can under the rules of the OS access the same memory as all other threads. The memory of each process is separate and can be access through normal means and this provides isolation between programs which helps prevent one program from crashing another by writing to it's memory by accident. Rust however applies some extra rules when sharing data between threads under the same process. Those rules are not important at this time, but you should be aware that they exist.

1.2. Rust Major Pointer Types

The four most common pointers in Rust that you will use are:

    &   - reference pointer
    Box - box pointer
    Rc  - reference counted pointer                (shared in single thread)
    Arc - atomicaly reference counted pointer      (shared with more than one thread)

The last two, the Rc and Arc, are the most flexible but also have an impact on performance. The reference pointer is the most used pointer but has some limitations that can make programming more difficult compared to other languages. Also to note the Box, Rc, and Arc all allocate data space in the heap instead of one the stack. We will start with the reference-pointer, then the box-pointer, and finally look at the reference counted pointers.

1.3. Preferred Previous Experience

I would like, but not require that, you have played with Rust a little or have already done some reading and are at least a little familar with variables. I wrote this guide mainly to help those that have tried all other resources but still find themselves a little lost when it comes to pointers. Also I sometimes use the long form of declaration to help you get a good understanding of the full form of a declaration instead of relying on the compiler to infer what type you are declaring.

1.4. Simple Variable And Reference Declarations

Let us examine some simple variable and reference pointer declarations. We will work through the examples by trial and error. At first we will try just a simple integer variable, and then we will add in a reference type pointer.

1.4.1. error: re-assignment of immutable variable `x`
    let x: int = 5;
    x = 3;

All variable are immutable by default. This means they can not be changed from their inital value. This helps you the programmer not accidentally change a variable that was never intended to change.

1.4.1.1. success
    let mut x: int = 5;
    x = 3;

As you can see once we applied the mutable mut keyword we can now re-assign the value to the variable.

1.4.1.2. error: mismatched types: expected `&int`, found `_` (expected &-ptr, found integral variable)
    let x: int = 5;
    let z: &int = &x;
    z = 2;

This involves pointers. You shall notice that we create a pointer which points to the variable x, but we can not treat the pointer as a normal value. The error message is telling you that it expected an assignment from a type of &int. The type &int is an immutable pointer to a int type. Pay close attention when error messages state what they expected and what they found! To assign to the pointer we must dereference it with a special symbol which is shown below.

1.4.1.3. error: cannot assign to immutable dereference of `&`-pointer `*z`
    let x: int = 5;
    let z: &int = &x;
    *z = 2;

We did not make x mutable! Therefore the compiler enforces this safety even through the indirection of pointers. Let us try changing x to be mutable. The special * character denotes a dereference operation.

1.4.1.4. error: cannot assign to immutable dereference of `&`-pointer `*z`
    let mut x: int = 5;
    let z: &int = &x;
    *z = 2;

It was almost correct! But, what in the world is wrong? We made x mutable but we did not make the pointer mutable.

1.4.1.5. success
    let mut x: int = 5;
    let z: &mut int = &mut x;
    *z = 2;

Now, we have successfuly declared and pointer and pointed it at x!

Also you should be aware of the following:

    let x: int = 5i;
    let a: &int = &x;
    let b: &&int = &a;

This is not a commonly encountered situation when writing programs, but it does happen enough that you should be aware of it. Here we allocate x on the stack and store the signed integer 5 on the stack. Then we allocate a on the stack and store the address of x. Finally, we create a second pointer b which stores the address of a on the stack. Do not worry about understanding this so much you may be better off contuing to read the guide and coming back later.

If you are still confused try the following program:

    let x: int = 5i;
    let a: &int = &x;
    let b: &&int = &a;
    println!("The value of x is {} and the address of x is {:p}", x, &x);
    println!("The value of a is {:p} and the address of a on the stack is {:p}", a, &a);
    println!("The value of b is {:p} and the address of b on the stack is {:p}", b, &b);
    println!("The value of *a is {} and the value of *b is {:p}, but the value of **b is {}", *a, *b, **b);

For extra knowledge you may notice the addresses are seperated, generally, by the value 8 on a 64-bit machine (X86-64) and the value 4 on a 32-bit machine (X86). This is because the size of the `uint`, `int`, and `pointer` are the size of the each slot in the stack and the CPU general register size. However, this is subject to change depending on the architecture of the computer that your Rust program is targeted too. Your Rust program is compiled specifically for a certain CPU architecture or sub-set of a architecture. This is a entirely different dicussion but bears enough important to be made known.

This program will print out the value of each variable, adjusting for if it is a pointer or a value. The memory addresses are highly likely to be on the stack, since Rust produces stack based code for most architectures.

The `{:p}` is a really useful diagnostic and learning tool. It can allow you to experiment with references in Rust as you learn to see exactly where it points to.

1.5. Data Structures
1.5.1. Illegal Recursive Type

Our first problem will deal with type recursion. Type recusion is where a type includes it's own self. This is impossible to represent because it means the type is infinite in size. To create an instance of this type would be impossible since where would you stop:

    struct Apple {
        next:   Apple
    }

To overcome this problem we would use pointers because this would allow us to optionaly have another item attached or not, however in Rust you are not allowed to have null pointers. A null pointer is generally a pointer with an address of zero. Most operating systems setup memory so that accessing memory starting at zero and extending to some multiple of 1024 will cause an error to occur. This error causes the program to be terminated and tells the user that the program has had a fatal error. This helps to catch null pointer bugs in programs that are not safe like Rust. If your program has multiple threads then the entire program may not crash but instead that particular thread will.

1.5.2. Legal Recursive Type But Not Possible To Use

Since Rust forces us to always initialize pointers to a valid memory location this would not work either, however the equivilent would work in some other languages:

    struct Apple {
        next:   &Apple
    }

The reason it would not work is because it would be impossible to create an instance of this structure because you would have to initialize the pointer and thus create a new structure and of course initialize the field in that structure and so on and forth to infinity.

1.5.3. Using The Option<T>

There is a way and we can do it using the Option<T> type:

    struct Apple<'a> {
        next:   Option<& 'a Apple<'a>>
    }

    fn main() {
        let a: Apple = Apple { next: None };
    }

That should work fine. Now, let us try to initialize another element:

    struct Apple<'a> {
        next:   Option<& 'a Apple<'a>>
    }

    fn main() {
        let a: Apple = Apple { next: Some(&Apple { next: None }) };
    }

You will get an error as follows:

    <anon>:7:40: 7:60 error: borrowed value does not live long enough
    <anon>:7     let a: Apple = Apple { next: Some(&Apple { next: None }) };
    [..remaining diagnostic error messages omitted by me]

This error means the the value used in next only lives as long as the statement, and since a live as long as the function it would be invalid to allow this to compile since next could then point to invalid memory. So what do we do? Well, I would like to introduce you to the box.

1.5.4. Introduction To Box<T>

Let me introduce you to my friend the box. In Rust there are many types which act like Box<T> such as Rc<T> or Arc<T>. However, each is different yet similar. We only need to use Box<T> here to accomplish our recursive structure problem. Later, we will take a look at when to use the others.

With box let us try the same program with some modifications:

    struct Apple {
        next:   Option<Box<Apple>>
    }

    fn main() {
        let a: Apple = Apple { next: Some(box Apple { next: None }) };
    }

The Box<T> (Box<Apple>) acts exactly like a pointer. You may notice the expression box Apple { next: None }. That expresion creates a box with Apple { next: None } in it. It actually causes Apple to be initialized directly into the memory on the heap allocated by the box which is likely contrary to your thought that Apple is created on the stack and then copied into the box. [[The ability for Apple to be directly and originally written to the box is an optimization.]]

Because we use an Option<Apple> you have to do a little fiddling to get access to the Apple. Let us examine the following code:

    fn main() {
        let mut a: Apple = Apple { next: Some(box Apple { next: None }) };
    
        a.next.as_mut().unwrap().next = Some(box Apple { next: None });
    }

Here we changed a to be mutable with the keyword mut so we can modify it after its initialization. The mut helps protect something from accidental change. It is kind of a safe guard against you making something unchangable in your code, then later trying to change it, which can happen and cause bugs. The most complex of these changes is the:

    a.next.as_mut().unwrap().next = Some(box Apple { next: None });

What happens is we access the field next of a with a.next. This yeilds the type Option<Apple> then we call as_mut() which yeilds Option<&Apple> then we call unwrap which yeilds &Apple and finally we access the next field of Apple through the reference. You may remember that we had trouble a while back with:

    let mut b: uint = 3u;
    let c: &mut uint = &mut b;
    c = 4u;     // INCORRECT
    *c = 4u;    // CORRECT

We were unable to use c alone since it was a pointer. We had to prefix * to dereference it so we could treat it as the actual type it pointed to right? Well, this only applies to to direct assignment. A pointer will be automatically dereferenced when calling methods, but if trying to assign or take as a value you must explicitly dereference because the compiler is unsure of your intentions therefore it requires you to specify what you mean. That is why after we called unwrap() we had a &Apple but we were able to access the field next. See the following. Both are the same:

    a.next.as_mut().unwrap().next = Some(box Apple { next: None });
    (*a.next.as_mut().unwrap()).next = Some(box Apple { next: None });

The compiler just automatically dereferences the pointer for us because it knows that we wish to call the method on the type not the pointer since pointers have no methods. The difference is when we try to take the value of or assign to the pointer.

1.5.5. Box<T> Limitations, Copy, And Clone

The Box<T> has limitations. Firstly, it is non-copyable meaning it can not be byte copied from location to another in memory. That is we are talking about the actual type Box<T> which in our cases was represented on the stack not T which is pointed to by the box. The T may have the Copy trait but Box does not. Also Box does not provide a clone() method meaning not only is the compiler unable to byte copy the box type but box also does not provide a way to duplicate the box or at to have more than one box point to the same memory location. This means that box is a unique pointer in that only one pointer of it's type exists. Take for example the following problem code. We wish to do the following but we are unable to do it with box:

    struct Apple {
        next:   Option<Box<Apple>>
    }

    fn test(mut a: Box<Apple>, mut b: Box<Apple>) {
        a.next = Some(b);
    }

    fn main() {
        let mut a: Box<Apple> = box Apple { next: None };
        let mut b: Box<Apple> = box Apple { next: None };
        let mut c: Box<Apple> = box Apple { next: None };

        a.next = Some(c);
        b.next = Some(c);       // ERROR: c was moved
        test(b, c);             // ERROR: c was moved
    }

This seems very reasonable. We simply wish to have two Apples where both point to the same one. You may wonder well why would a restriction like this be created? The answer is because the Box<T> has very low overhead and to faciliate two different boxes pointing to the same memory would require additional overhead. Since Rust was designed with performance in mind Box<T> was also created for situations where you needed only a unique pointer. Also consider when must the memory pointed to by the box be freed? When the box is destroyed is when the memory is freed. If you had two boxes both pointing to the same memory you would need additional logic to determine when the last box was left. Well the Rc<T> type provides this additional logic. To prevent the programmer from accidentally having two Box<Apple> pointing to the same Apple the box does not have the Copy trait which firstly prevents the compiler from doing a byte copy, and secondly not providing the Clone trait which would provide the clone() method.

1.5.5.1. What Does Move Do?

If you are a little confused about what move means let me try to explain. Essentially, if a value can not be copied byte by byte by the compiler then it will move the value (which represents the instance of the type) which essentially means to pass it by reference and by doing so it prevents future usage of the moved value. Let us look at an example of two different methods:

    struct Apple {
        next:   Option<Box<Apple>>
    }

    // `a` is passed by reference
    fn take1(a: Box<Apple>) {
    }

    // `a` is passed by reference
    fn take2(a: &Box<Apple>) {
    
    }

    fn main() {
        let mut a: Box<Apple> = box Apple { next: None };
    
        take2(&a);
        take1(a);
    }

In both functions a is passed by pointer. You may be confused because one takes it by value and the other by immutable reference-pointer. On my test system both functions compile to effectively the exact same code and accept the argument in the exact same way. How can this be you ask? Well, it is actually quite simple. The compiler knows that Box<T> is not copyable therefore it can not pass it by value and must accept a pointer so it treats the argument behind the scenes so that a: Box<Apple> is really treated just like a: &Box<Apple>.

You may be wondering why even move a value. Why not just pass in a reference and then continue to use the type even after the function returns, right? Well, the ownership is passed to the function when the value is moved, or in other words consumed by the function. If you only meant to lend it out then take2 would have been more appropriate. If you wish to return ownership you can pass the value back through a return argument such as:

    fn take3(a: Box<Apple>) -> Box<Apple> {
        a
    }

    fn main() {
        let mut a: Box<Apple> = box Apple { next: None };
    
        a = take3(a);
        take2(&a);
        take1(a);
    }

As you can see take3 returns the value (or moves the value out) and ownership returns to the main function. It can then be loaned out to take2 by immutable reference and finally moved into (consumed by) take1 which keeps ownership and is responsible for destroying/deconstructing/freeing the value. In this case destruction of the value would release the memory allocated by the box.

It is beyond my ability to currently explain to you exactly why this behavior was desired but it may have to do with performance. The Box<T> is designed to have a low of overhead as possible and therefore it is retrained by the rules of ownership which allows the compiler to determine with great accuracy at compile time when to call the deconstructor code for the Box<T>. There do exist unique situations in which something called a drop flag helps faciliate the release of resources by the box but that condition is not very common in most code. Therefore you need to be aware of the rules for which a value is moved into or out of a function and understand the implications of doing so.

1.5.5.2. Lifetimes.. Non-Copyable By Reference Or Moved Value?

At the moment you have a choice. You can implement a take2 version for a non-copyable value or a take1 version, but he question you should have is when do I need which one, right? Well, let me help you to decide. For non-copyable values that you wish to continue using after calling the function passing by reference is fairly obvious or in some situations you can return the value back to the calling function. One reason you may accept a non-copyable value type by value as an argument is if your function will move the value into something else. With out ownership you will be unable to do so. For example you implement a collection or container like structure like so:

    struct Apple {
        next:   Option<Box<Apple>>
    }

    struct Bucket {
        item:   Option<Box<Apple>>
    }

    impl Bucket {
        fn putin(b: &mut Bucket, a: Box<Apple>) {
            (*b).item = Some(a);
        }
    }

    fn main() {
        let a: Box<Apple> = box Apple { next: None };
        let mut b: Bucket = Bucket { item: None };
    
        Bucket::putin(&mut b, a);
    }

There is no way that Bucket::putin can place a into the bucket unless it has ownership because it is required to move the value into the bucket which allows the bucket to take ownership. When bucket takes ownership it becomes responsible for destruction of the value when it is destructed. You could do something like this:

    struct Apple {
        next:   Option<Box<Apple>>
    }

    struct Bucket<'a> {
        item:   Option<& 'a Box<Apple>>
    }

    impl<'a> Bucket<'a> {
        fn putin(b: &mut Bucket<'a>, a: & 'a Box<Apple>) {
            (*b).item = Some(a);
        }
    }

    fn main() {
        let a: Box<Apple> = box Apple { next: None };
        let mut b: Bucket = Bucket { item: None };
    
        Bucket::putin(&mut b, &a);
    }

Now we have changed the bucket to store an immutable-reference to Apple. So what have we lost or gained? We actually have not gained much. We did not gain anything in performance since Box<Apple> was already a pointer. We did however lose the ability to destroy the value in the bucket when we decide since we are now at the mercy of the owner of a. For example consider the following change:

    fn example(b: &mut Bucket) {
        let a: Box<Apple> = box Apple { next: None };
        Bucket::putin(b, &a);
    }

    fn main() {
        let mut b: Bucket = Bucket { item: None };
        example(&mut b);
    }

Now you will get the error error: 'a' does not live long enough. So because we did not take ownership we were unable to move the value into the bucket we had to use a reference, and because of the compilers compile time checks it determined that with out runtime intervention the bucket would out live the reference meaning it allowed once example returned the bucket would contain a pointer to recently freed memory which is called a dangling pointers. If this pointer is accessed (read/write) you can potentially read undesired memory, cause a program crash, or wrose write over completely irrelavent memory causing memory corruption which can create all sorts of bizzare and strange bugs. So Rust is trying to help us! It is trying to protect us from hurting outselves essentially. For some people this could result in a flustraiting amount of time trying to make the compiler happy. The reality is that in this case you simply need to pass it by value, or use the clone method if it is implemented. Let us talk about the clone method in the next section with the introduction of the Rc<T> pointer!

I think the overall point is if you are going to need to transfer something into a collection or container you need a non-copyable by value, and if you just want to use it then you need it by reference. So most of the time you will likely be passing non-copyable types by reference. As you are writting your code ask yourself do I need to place this non-copyable value into something? If the answer is yes then you will need to accept it by value.

1.5.6. Introduction To Rc<T>

We noticed one major limitation of Box<T> was the inability to have multiple box-pointers which point to the same memory/value. The Rc<T> can overcome that limitation with some help during run-time. This help comes at a price of less speed. Now do not be afraid because Rust produces very fast code and even using Rc<T> can be extremely fast. However, it is worth mentioning because otherwise we could just use Rc<T> for just about everything that we can use box for. Rc<T> does have a big limitation because by default it's contents are immutable! There is a way to circumvent this limitation and it is called inner mutability which we will discuss later. For now let me show you an example of something that Rc<T> can do that Box<T> can not.