i'm having difficulty getting borrow checker working simple iterative linked list builder.
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; 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'm receiving when try compile:
linked_list.rs:8:30: 8:69 error: borrowed value not live long enough linked_list.rs:8 let curr = some(&mut box::new(node { value: i, next: none })); ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ note: in expansion of loop expansion linked_list.rs:7:5: 19:6 note: expansion site linked_list.rs:4:49: 20:2 note: reference must valid block suffix following statement 2 @ 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 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 valid statement @ 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 `let` binding increase 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` mutable linked_list.rs:10 some(ref mut p) => { ^~~~~~~~~ note: in expansion of loop expansion linked_list.rs:7:5: 19:6 note: expansion site linked_list.rs:15:17: 15:28 error: cannot assign `root` because borrowed linked_list.rs:15 root = curr; ^~~~~~~~~~~ note: in expansion of 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 loop expansion linked_list.rs:7:5: 19:6 note: expansion site linked_list.rs:16:29: 16:33 error: cannot borrow `root` mutable more once @ time linked_list.rs:16 prev = &mut root; ^~~~ note: in expansion of 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; mutable borrow prevents subsequent moves, borrows, or modification of `root` until borrow ends linked_list.rs:16 prev = &mut root; ^~~~ note: in expansion of 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 4 previous errors what i'm trying go simple. iterate through vec, creating new node on each iteration. if prev none must start, make root variable take ownership of first node. if it's not, update previous node's next value point node.
i'm new rust i'm not sure i'm going wrong. interpretation borrow checker isn't handling well. can't infer none branch in match, containing 'root' assignment, ever called once, causing 2 errors root being borrowed twice. correct?
is approach possible in rust? there more idiomatic way sort of thing?
(a recursive approach easier i'd complete iterative 1 learning exercise.)
first of all, should make sure you've read , understood rust book chapters on ownership , references , borrowing. immediate problem you're borrowing things aren't owned anything, , disappear. have other problems trying mutate through immutable pointer.
let's does, @ least, work:
fn main() { let v = vec![1,5,3,8,12,56,1230,2,1]; let mut root: option<box<node>> = none; 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 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 constructs list , shows how can iteratively display it. note complete lack of borrows in construction code.
i have cheated somewhat, in i've iterated vector backwards construct list.
the problem original code that, if strip out isn't necessary, down 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(); in v { let curr = some(box::new(node { value: i, next: none })); prev.next = curr; prev = prev.next.as_mut().unwrap(); } } you still end in situation compiler sees mutating thing you've borrowed second path. it's not quite smart enough realise re-assigning prev doesn't actually create aliases. on other hand, if break loop 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) 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 totally fine it. sadly, optimisations turned on, rust doesn't perform tail call elimination in case. between borrow checker limitations , lack of guaranteed tail call elimination, design might impossible in safe code.
i've run problem myself; loops , &mut pointers don't play nicely 1 another. can work around switching refcell, associated runtime cost, although complicates iterating on such list in loop. alternative use usizes instead of pointers, , have nodes allocated vec somewhere, although introduces bounds checking overhead.
failing that, there's unsafe code, lets write more or less write in language c or c++, without rust's usual safety guarantees.
at end of day, writing data structures are not wrappers around existing data structure in safe rust without overhead borderline impossible. it's why fundamental data structures in rust written using amount of unsafe code.
Comments
Post a Comment