Creating a simple linked list
I am having difficulty getting the earnings controller to work with a simple iterative linked list constructor.
fn main() {
let v = vec![1,5,3,8,12,56,1230,2,1];
let nodes = Vec::<Node>::with_capacity(v.len());
let mut root: Option<&mut Box<Node>> = None;
let mut prev: &Option<&mut Box<Node>> = &None;
for i in v {
let curr = Some(&mut Box::new(Node { value: i, next: None }));
match *prev {
Some(ref mut p) => {
p.next = curr;
prev = &mut p.next;
},
None => {
root = curr;
prev = &mut root;
}
}
}
}
struct Node<'a> {
value: i32,
next: Option<&'a mut Box<Node<'a>>>,
}
The errors I get when I try to compile:
linked_list.rs:8:30: 8:69 error: borrowed value does not live long enough
linked_list.rs:8 let curr = Some(&mut Box::new(Node { value: i, next: None }));
^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
note: in expansion of for loop expansion
linked_list.rs:7:5: 19:6 note: expansion site
linked_list.rs:4:49: 20:2 note: reference must be valid for the block suffix following statement 2 at 4:48...
linked_list.rs:4 let mut root: Option<&mut Box<Node>> = None;
linked_list.rs:5 let mut prev: &Option<&mut Box<Node>> = &None;
linked_list.rs:6
linked_list.rs:7 for i in v {
linked_list.rs:8 let curr = Some(&mut Box::new(Node { value: i, next: None }));
linked_list.rs:9 match *prev {
...
linked_list.rs:8:9: 8:71 note: ...but borrowed value is only valid for the statement at 8:8
linked_list.rs:8 let curr = Some(&mut Box::new(Node { value: i, next: None }));
^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
linked_list.rs:8:9: 8:71 help: consider using a `let` binding to increase its lifetime
linked_list.rs:8 let curr = Some(&mut Box::new(Node { value: i, next: None }));
^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
linked_list.rs:10:18: 10:27 error: cannot borrow immutable anonymous field `(prev:core::option::Some).0` as mutable
linked_list.rs:10 Some(ref mut p) => {
^~~~~~~~~
note: in expansion of for loop expansion
linked_list.rs:7:5: 19:6 note: expansion site
linked_list.rs:15:17: 15:28 error: cannot assign to `root` because it is borrowed
linked_list.rs:15 root = curr;
^~~~~~~~~~~
note: in expansion of for loop expansion
linked_list.rs:7:5: 19:6 note: expansion site
linked_list.rs:16:29: 16:33 note: borrow of `root` occurs here
linked_list.rs:16 prev = &mut root;
^~~~
note: in expansion of for loop expansion
linked_list.rs:7:5: 19:6 note: expansion site
linked_list.rs:16:29: 16:33 error: cannot borrow `root` as mutable more than once at a time
linked_list.rs:16 prev = &mut root;
^~~~
note: in expansion of for loop expansion
linked_list.rs:7:5: 19:6 note: expansion site
linked_list.rs:16:29: 16:33 note: previous borrow of `root` occurs here; the mutable borrow prevents subsequent moves, borrows, or modification of `root` until the borrow ends
linked_list.rs:16 prev = &mut root;
^~~~
note: in expansion of for loop expansion
linked_list.rs:7:5: 19:6 note: expansion site
linked_list.rs:20:2: 20:2 note: previous borrow ends here
linked_list.rs:1 fn main() {
...
linked_list.rs:20 }
^
error: aborting due to 4 previous errors
What I am trying to do is pretty simple. We iterate through the Vec, creating a new node on each iteration. If prev is None, this should be the start, so we make the root variable the property of the first node. If it is not, we will update the previous node value to point to this node.
I am new to Rust so I don’t know where I am going wrong. My interpretation is that the loan checker fails to handle this. It cannot infer that the "No" branch in the match containing the "root" assignment will ever be called only once, resulting in two errors about borrowing the root twice. Am I correct?
Is it possible this approach is possible in Rust? Is there a more idiomatic way to do things like this?
(The recursive approach is probably much simpler, but I would like to complete the iterative learning process.)
source to share
First of all, you should definitely make sure to read and understand the chapters of the Rust book on Ownership and References and Borrowings . Your immediate problem is that you are borrowing things that do not belong to anyone and thus simply disappear. You also have other problems like trying to mutate via an immutable pointer.
Let's get what does at least work:
fn main() { let v = vec![1,5,3,8,12,56,1230,2,1]; let mut root: Option<Box<Node>> = None; for i in v.into_iter().rev() { root = Some(Box::new(Node { value: i, next: root })); } println!("root: {}", root.map(|n| n.to_string()).unwrap_or(String::from("None"))); } struct Node { value: i32, next: Option<Box<Node>>, } impl std::fmt::Display for Node { fn fmt(&self, fmt: &mut std::fmt::Formatter) -> Result<(), std::fmt::Error> { let mut cur = Some(self); let mut first = true; try!(write!(fmt, "[")); while let Some(node) = cur { if !first { try!(write!(fmt, ", ")); } first = false; try!(write!(fmt, "{}", node.value)); cur = node.next.as_ref().map(|n| &**n); } try!(write!(fmt, "]")); Ok(()) } }
This creates a list and shows how you can iteratively display it. Pay attention to the complete absence of borrowings in the building code.
I was a little tricked into flipping the vector backwards to build the list.
The problem with the original code is that even if you cross out anything you don't need to something like this:
let v = vec![1,5,3,8,12,56,1230,2,1];
let mut v = v.into_iter();
let mut root: Option<Box<Node>> = None;
if let Some(i) = v.next() {
root = Some(Box::new(Node { value: i, next: None }));
let mut prev: &mut Box<Node> = root.as_mut().unwrap();
for i in v {
let curr = Some(Box::new(Node { value: i, next: None }));
prev.next = curr;
prev = prev.next.as_mut().unwrap();
}
}
You still find yourself in a situation where the compiler sees you mutating the thing that you borrowed in the second path. It's not entirely smart to realize that the reassignment prev
doesn't actually create any aliases. On the other hand, if you split the loop into an equivalent recursion:
if let Some(i) = v.next() {
root = Some(Box::new(Node { value: i, next: None }));
fn step<It>(prev: &mut Box<Node>, mut v: It) where It: Iterator<Item=i32> {
if let Some(i) = v.next() {
let curr = Some(Box::new(Node { value: i, next: None }));
prev.next = curr;
step(prev.next.as_mut().unwrap(), v)
}
}
step(root.as_mut().unwrap(), v);
}
Then it's completely normal. Unfortunately, even with optimizations enabled, Rust does not eliminate tail call elimination in this case. So between the constraints of check validation and the lack of guaranteed elimination of the tail call, this design may not be possible to do in safe code.
I ran into this problem myself; loops and pointers &mut
don't always go well with each other. You can work around this by switching to RefCell
with your associated cost at runtime, although this makes it harder to iterate over such a list in a loop. Another alternative is to use usize
pointers instead of and all nodes placed in Vec
, somewhere, although this introduces bounds checking overhead.
Otherwise, there is code unsafe
that allows you to write more or less exactly what you write in another language, such as C or C ++, but without Rust's usual security guarantees.
In the end, creating data structures that are not just wrappers around an existing data structure in secure Rust without the overhead is not possible. This is why all fundamental data structures in Rust are written with some unsafe code.
source to share