Asked  6 Months ago    Answers:  5   Viewed   151 times

I'm trying to navigate a recursive data structure iteratively in order to insert elements at a certain position. To my limited understanding, this means taking a mutable reference to the root of the structure and successively replacing it by a reference to its follower:

type Link = Option<Box<Node>>;

struct Node {
    next: Link
}

struct Recursive {
    root: Link
}

impl Recursive {
    fn back(&mut self) -> &mut Link {
        let mut anchor = &mut self.root;
        while let Some(ref mut node) = *anchor {
            anchor = &mut node.next;
        }
        anchor
    }
}

(Rust playground link)

However, this fails:

error[E0499]: cannot borrow `anchor.0` as mutable more than once at a time
  --> src/main.rs:14:24
   |
14 |         while let Some(ref mut node) = *anchor {
   |                        ^^^^^^^^^^^^
   |                        |
   |                        second mutable borrow occurs here
   |                        first mutable borrow occurs here
...
18 |     }
   |     - first borrow ends here

error[E0506]: cannot assign to `anchor` because it is borrowed
  --> src/main.rs:15:13
   |
14 |         while let Some(ref mut node) = *anchor {
   |                        ------------ borrow of `anchor` occurs here
15 |             anchor = &mut node.next;
   |             ^^^^^^^^^^^^^^^^^^^^^^^ assignment to borrowed `anchor` occurs here

error[E0499]: cannot borrow `*anchor` as mutable more than once at a time
  --> src/main.rs:17:9
   |
14 |         while let Some(ref mut node) = *anchor {
   |                        ------------ first mutable borrow occurs here
...
17 |         anchor
   |         ^^^^^^ second mutable borrow occurs here
18 |     }
   |     - first borrow ends here

This makes sense as both anchor and node refer to the same structure, but I actually don't care about anchor any more after destructuring it.

How could back() be implemented correctly using safe Rust?

 Answers

70

It is possible... but I wish I had a more elegant solution.

The trick is NOT to borrow from anchor, and therefore to juggle between two accumulators:

  • one holding the reference to the current node
  • the other being assigned the reference to the next node

This leads me to:

impl Recursive {
    fn back(&mut self) -> &mut Link {
        let mut anchor = &mut self.root;

        loop {
            let tmp = anchor;
            if let Some(ref mut node) = *tmp {
                anchor = &mut node.next;
            } else {
                anchor = tmp;
                break;
            }
        }

        anchor
    }
}

Not exactly pretty, but this is something the borrow checker can get behind so ¯_(?)_/¯.

@ker has improved on this by creating an unnamed temporary:

impl Recursive {
    fn back(&mut self) -> &mut Link {
        let mut anchor = &mut self.root;

        loop {
            match {anchor} {
                &mut Some(ref mut node) => anchor = &mut node.next,
                other => return other,
            }
        }
    }
}

The trick here is that using {anchor} moves the content of anchor into an unnamed temporary on which the match executes. Therefore, in the match block we are not borrowing from anchor but from the temporary, leaving us free to modify anchor. See the related blog post Stuff the Identity Function Does (in Rust).

Tuesday, June 1, 2021
 
Revent
answered 6 Months ago
65

You have fallen into the lifetime-trap. Adding the same lifetime to more references will constrain your program more. Adding more lifetimes and giving each reference the minimal possible lifetime will permit more programs. As @o11c notes, removing the constraints to the 'a lifetime will solve your issue.

impl<'a> Context<'a> {
    fn get_function(&mut self, fun_name: &str) -> Result<Function<'a>, Error> {
        self.program
            .get(fun_name)
            .map(|f| *f)
            .ok_or(Error::FunctionNotFound)
    }

    fn call(&mut self, fun_name: &str) -> Result<(), Error> {
        let fun = try!(self.get_function(fun_name));

        self.call_stack.push(fun);

        Ok(())
    }
}

The reason this works is that Rust inserts new lifetimes, so in the compiler your function's signatures will look like this:

fn get_function<'b>(&'b mut self, fun_name: &'b str) -> Result<Function<'a>, Error>
fn call<'b>(&'b mut self, fun_name: &'b str) -> Result<(), Error>

Always try to not use any lifetimes and let the compiler be smart. If that fails, don't spray lifetimes everywhere, think about where you want to pass ownership, and where you want to limit the lifetime of a reference.

Tuesday, June 1, 2021
 
conmen
answered 6 Months ago
67

I modified Masklinn's code slightly to allow multiple .pop()s to be called on the same stack:

struct StackLike<'a, X> {
    data: &'a mut [X],
}

impl<'a, X> StackLike<'a, X> {
    pub fn pop(&mut self) -> Option<&'a mut X> {
        let data = std::mem::replace(&mut self.data, &mut []);
        if let Some((last, subslice)) = data.split_last_mut() {
            self.data = subslice;
            Some(last)
        } else {
            None
        }
    }
}

fn main() {
    let mut data = [1, 2, 3, 4, 5];
    let mut stack = StackLike { data: &mut data };

    let x = stack.pop().unwrap();
    let y = stack.pop().unwrap();
    println!("X: {}, Y: {}", x, y);
}

The tricky part here is this line (I added a type annotation for explicitness):

let data: &'a mut [X] = std::mem::replace(&mut self.data, &mut []);

We replace self.data with an empty slice temporarily so that we can split the slice. If you were to write simply

let data: &'a mut [X] = self.data;

the compiler would be unhappy:

error[E0312]: lifetime of reference outlives lifetime of borrowed content...
  --> src/main.rs:7:33
   |
7  |         let data: &'a mut [X] = self.data;
   |                                 ^^^^^^^^^
   |
note: ...the reference is valid for the lifetime `'a` as defined on the impl at 5:6...
  --> src/main.rs:5:6
   |
5  | impl<'a,  X> StackLike<'a, X> {
   |      ^^
note: ...but the borrowed content is only valid for the anonymous lifetime #1 defined on the method body at 6:5
  --> src/main.rs:6:5
   |
6  | /     pub fn pop(&mut self) -> Option<&'a mut X> {
7  | |         let data: &'a mut [X] = self.data;
8  | |         if let Some((last, subslice)) = data.split_last_mut() {
9  | |             self.data = subslice;
...  |
13 | |         }
14 | |     }
   | |_____^

As far as I understand it, the problem is that self.data is a mutable reference, and mutable references are not Copy (remember, you can only have one at a time). And you cannot move out of self.data since self is a mutable reference, not an owner. So what the compiler tries to do is to reborrow self.data, which "infects" it with with the lifetime of &mut self. This is a dead end: we want the reference to live for 'a, but it is actually valid only for the lifetime of &mut self, and these lifetimes are generally unrelated (and they don't need to be related), which leaves the compiler perplexed.

To aid the compiler, we use std::mem::replace to explicitly move the slice out of self.data and temporarily replace it with an empty slice, which can be any lifetime. Now we can do anything with data without tangling it with the lifetime of &mut self.

Saturday, June 26, 2021
 
Wickethewok
answered 6 Months ago
71

You have to use the Entry "pattern":

use std::collections::HashMap;
use std::collections::hash_map::Entry::{Occupied, Vacant};

fn main() {
    let mut words = vec!["word1".to_string(), "word2".to_string(), "word1".to_string(), "word3".to_string()];
    let mut wordCount = HashMap::<String, u32>::new();

    for w in words {
        let val = match wordCount.entry(w) {
           Vacant(entry) => entry.insert(0),
           Occupied(entry) => entry.into_mut(),
        };

        // do stuff with the value
        *val += 1;
    }

    for k in wordCount.iter() {
        println!("{:?}", k);
    }
}

The Entry object allows you to insert a value if its missing, or to modify it if it already exists.

https://doc.rust-lang.org/stable/std/collections/hash_map/enum.Entry.html

Thursday, August 12, 2021
 
phuongzzz
answered 4 Months ago
93

Disclaimer: there is no formal memory model, yet.1

First of all, I'd like to address:

The problem I see here is that x, being an &mut reference, can be assumed to be unique by the compiler.

Yes... and no. x can only be assumed to be unique if not borrowed, an important distinction:

fn doit(x: &mut T) {
    let y = &mut *x;
    //  x is re-borrowed at this point.
}

Therefore, currently, I would work with the assumption that deriving a pointer from x will temporarily "borrow" x in some sense.

This is all wishy washy in the absence of a formal model, of course, and part of the reason why the rustc compiler is not too aggressive with aliasing optimizations yet: until a formal model is defined, and code is checked to match it, optimizations have to be conservative.

1 The RustBelt project is all about establishing a formally proven memory model for Rust. The latest news from Ralf Jung were about a Stacked Borrows model.


From Ralf (comments): the key point in the above example is that there is a clear transfer from x to x_ptr and back to x again. So the x_ptr is a scoped borrow in a sense. Should the usage go x, x_ptr, back to x and back to x_ptr, then the latter would be Undefined Behavior:

fn main() {
    let x = &mut [1, 2, 4];
    let x_ptr = x.as_mut_ptr(); // x_ptr borrows the right to mutate

    unsafe {
        for i in 0..x.len() {
            *x_ptr.offset(i as isize) += 2; // Fine use of raw pointer.
        }
    }
    assert_eq!(x, &[3, 4, 6]);  // x is back in charge, x_ptr invalidated.

    unsafe { *x_ptr += 1; }     // BÄM! Used no-longer-valid raw pointer.
}
Sunday, October 10, 2021
 
Ahmed Haque
answered 2 Months ago
Only authorized users can answer the question. Please sign in first, or register a free account.
Not the answer you're looking for? Browse other questions tagged :  
Share