From 9123bb02ca3d71e16ce3e4a2ebb1fca49fcd93e2 Mon Sep 17 00:00:00 2001 From: Alexis Beingessner Date: Tue, 28 Jul 2015 15:38:39 -0700 Subject: fix borrow-splitting --- src/doc/tarpl/SUMMARY.md | 2 +- src/doc/tarpl/borrow-splitting.md | 281 +++++++++++++++++++++++++++++++++++ src/doc/tarpl/lifetime-splitting.md | 282 ------------------------------------ src/doc/tarpl/unchecked-uninit.md | 10 +- 4 files changed, 287 insertions(+), 288 deletions(-) create mode 100644 src/doc/tarpl/borrow-splitting.md delete mode 100644 src/doc/tarpl/lifetime-splitting.md diff --git a/src/doc/tarpl/SUMMARY.md b/src/doc/tarpl/SUMMARY.md index a7014d7f020..aeab8fc7276 100644 --- a/src/doc/tarpl/SUMMARY.md +++ b/src/doc/tarpl/SUMMARY.md @@ -17,7 +17,7 @@ * [Subtyping and Variance](subtyping.md) * [Drop Check](dropck.md) * [PhantomData](phantom-data.md) - * [Splitting Lifetimes](lifetime-splitting.md) + * [Splitting Borrows](borrow-splitting.md) * [Type Conversions](conversions.md) * [Coercions](coercions.md) * [The Dot Operator](dot-operator.md) diff --git a/src/doc/tarpl/borrow-splitting.md b/src/doc/tarpl/borrow-splitting.md new file mode 100644 index 00000000000..fe5f2343dec --- /dev/null +++ b/src/doc/tarpl/borrow-splitting.md @@ -0,0 +1,281 @@ +% Splitting Borrows + +The mutual exclusion property of mutable references can be very limiting when +working with a composite structure. The borrow checker understands some basic +stuff, but will fall over pretty easily. It *does* understand structs +sufficiently to know that it's possible to borrow disjoint fields of a struct +simultaneously. So this works today: + +```rust +struct Foo { + a: i32, + b: i32, + c: i32, +} + +let mut x = Foo {a: 0, b: 0, c: 0}; +let a = &mut x.a; +let b = &mut x.b; +let c = &x.c; +*b += 1; +let c2 = &x.c; +*a += 10; +println!("{} {} {} {}", a, b, c, c2); +``` + +However borrowck doesn't understand arrays or slices in any way, so this doesn't +work: + +```rust,ignore +let x = [1, 2, 3]; +let a = &mut x[0]; +let b = &mut x[1]; +println!("{} {}", a, b); +``` + +```text +:3:18: 3:22 error: cannot borrow immutable indexed content `x[..]` as mutable +:3 let a = &mut x[0]; + ^~~~ +:4:18: 4:22 error: cannot borrow immutable indexed content `x[..]` as mutable +:4 let b = &mut x[1]; + ^~~~ +error: aborting due to 2 previous errors +``` + +While it was plausible that borrowck could understand this simple case, it's +pretty clearly hopeless for borrowck to understand disjointness in general +container types like a tree, especially if distinct keys actually *do* map +to the same value. + +In order to "teach" borrowck that what we're doing is ok, we need to drop down +to unsafe code. For instance, mutable slices expose a `split_at_mut` function +that consumes the slice and returns *two* mutable slices. One for everything to +the left of the index, and one for everything to the right. Intuitively we know +this is safe because the slices don't overlap, and therefore alias. However +the implementation requires some unsafety: + +```rust,ignore +fn split_at_mut(&mut self, mid: usize) -> (&mut [T], &mut [T]) { + let len = self.len(); + let ptr = self.as_mut_ptr(); + assert!(mid <= len); + unsafe { + (from_raw_parts_mut(ptr, mid), + from_raw_parts_mut(ptr.offset(mid as isize), len - mid)) + } +} +``` + +This is actually a bit subtle. So as to avoid ever making two `&mut`'s to the +same value, we explicitly construct brand-new slices through raw pointers. + +However more subtle is how iterators that yield mutable references work. +The iterator trait is defined as follows: + +```rust +trait Iterator { + type Item; + + fn next(&mut self) -> Option; +} +``` + +Given this definition, Self::Item has *no* connection to `self`. This means that +we can call `next` several times in a row, and hold onto all the results +*concurrently*. This is perfectly fine for by-value iterators, which have +exactly these semantics. It's also actually fine for shared references, as they +admit arbitrarily many references to the same thing (although the iterator needs +to be a separate object from the thing being shared). + +But mutable references make this a mess. At first glance, they might seem +completely incompatible with this API, as it would produce multiple mutable +references to the same object! + +However it actually *does* work, exactly because iterators are one-shot objects. +Everything an IterMut yields will be yielded *at most* once, so we don't +*actually* ever yield multiple mutable references to the same piece of data. + +Perhaps surprisingly, mutable iterators *don't* require unsafe code to be +implemented for many types! + +For instance here's a singly linked list: + +```rust +# fn main() {} +type Link = Option>>; + +struct Node { + elem: T, + next: Link, +} + +pub struct LinkedList { + head: Link, +} + +pub struct IterMut<'a, T: 'a>(Option<&'a mut Node>); + +impl LinkedList { + fn iter_mut(&mut self) -> IterMut { + IterMut(self.head.as_mut().map(|node| &mut **node)) + } +} + +impl<'a, T> Iterator for IterMut<'a, T> { + type Item = &'a mut T; + + fn next(&mut self) -> Option { + self.0.take().map(|node| { + self.0 = node.next.as_mut().map(|node| &mut **node); + &mut node.elem + }) + } +} +``` + +Here's a mutable slice: + +```rust +use std::mem; + +pub struct IterMut<'a, T: 'a>(&'a mut[T]); + +impl<'a, T> Iterator for IterMut<'a, T> { + type Item = &'a mut T; + + fn next(&mut self) -> Option { + let slice = mem::replace(&mut self.0, &mut []); + if slice.is_empty() { return None; } + + let (l, r) = slice.split_at_mut(1); + self.0 = r; + l.get_mut(0) + } +} + +impl<'a, T> DoubleEndedIterator for IterMut<'a, T> { + fn next_back(&mut self) -> Option { + let slice = mem::replace(&mut self.0, &mut []); + if slice.is_empty() { return None; } + + let new_len = slice.len() - 1; + let (l, r) = slice.split_at_mut(new_len); + self.0 = l; + r.get_mut(0) + } +} +``` + +And here's a binary tree: + +```rust +use std::collections::VecDeque; + +type Link = Option>>; + +struct Node { + elem: T, + left: Link, + right: Link, +} + +pub struct Tree { + root: Link, +} + +struct NodeIterMut<'a, T: 'a> { + elem: Option<&'a mut T>, + left: Option<&'a mut Node>, + right: Option<&'a mut Node>, +} + +enum State<'a, T: 'a> { + Elem(&'a mut T), + Node(&'a mut Node), +} + +pub struct IterMut<'a, T: 'a>(VecDeque>); + +impl Tree { + pub fn iter_mut(&mut self) -> IterMut { + let mut deque = VecDeque::new(); + self.root.as_mut().map(|root| deque.push_front(root.iter_mut())); + IterMut(deque) + } +} + +impl Node { + pub fn iter_mut(&mut self) -> NodeIterMut { + NodeIterMut { + elem: Some(&mut self.elem), + left: self.left.as_mut().map(|node| &mut **node), + right: self.right.as_mut().map(|node| &mut **node), + } + } +} + + +impl<'a, T> Iterator for NodeIterMut<'a, T> { + type Item = State<'a, T>; + + fn next(&mut self) -> Option { + match self.left.take() { + Some(node) => Some(State::Node(node)), + None => match self.elem.take() { + Some(elem) => Some(State::Elem(elem)), + None => match self.right.take() { + Some(node) => Some(State::Node(node)), + None => None, + } + } + } + } +} + +impl<'a, T> DoubleEndedIterator for NodeIterMut<'a, T> { + fn next_back(&mut self) -> Option { + match self.right.take() { + Some(node) => Some(State::Node(node)), + None => match self.elem.take() { + Some(elem) => Some(State::Elem(elem)), + None => match self.left.take() { + Some(node) => Some(State::Node(node)), + None => None, + } + } + } + } +} + +impl<'a, T> Iterator for IterMut<'a, T> { + type Item = &'a mut T; + fn next(&mut self) -> Option { + loop { + match self.0.front_mut().and_then(|node_it| node_it.next()) { + Some(State::Elem(elem)) => return Some(elem), + Some(State::Node(node)) => self.0.push_front(node.iter_mut()), + None => if let None = self.0.pop_front() { return None }, + } + } + } +} + +impl<'a, T> DoubleEndedIterator for IterMut<'a, T> { + fn next(&mut self) -> Option { + loop { + match self.0.back_mut().and_then(|node_it| node_it.next_back()) { + Some(State::Elem(elem)) => return Some(elem), + Some(State::Node(node)) => self.0.push_back(node.iter_mut()), + None => if let None = self.0.pop_back() { return None }, + } + } + } +} +``` + +All of these are completely safe and work on stable Rust! This ultimately +falls out of the simple struct case we saw before: Rust understands that you +can safely split a mutable reference into subfields. We can then encode +permanently consuming a reference via Options (or in the case of slices, +replacing with an empty slice). diff --git a/src/doc/tarpl/lifetime-splitting.md b/src/doc/tarpl/lifetime-splitting.md deleted file mode 100644 index e320c5c7b6b..00000000000 --- a/src/doc/tarpl/lifetime-splitting.md +++ /dev/null @@ -1,282 +0,0 @@ -% Splitting Lifetimes - -The mutual exclusion property of mutable references can be very limiting when -working with a composite structure. The borrow checker understands some basic -stuff, but will fall over pretty easily. It *does* understand structs -sufficiently to know that it's possible to borrow disjoint fields of a struct -simultaneously. So this works today: - -```rust -struct Foo { - a: i32, - b: i32, - c: i32, -} - -let mut x = Foo {a: 0, b: 0, c: 0}; -let a = &mut x.a; -let b = &mut x.b; -let c = &x.c; -*b += 1; -let c2 = &x.c; -*a += 10; -println!("{} {} {} {}", a, b, c, c2); -``` - -However borrowck doesn't understand arrays or slices in any way, so this doesn't -work: - -```rust,ignore -let x = [1, 2, 3]; -let a = &mut x[0]; -let b = &mut x[1]; -println!("{} {}", a, b); -``` - -```text -:3:18: 3:22 error: cannot borrow immutable indexed content `x[..]` as mutable -:3 let a = &mut x[0]; - ^~~~ -:4:18: 4:22 error: cannot borrow immutable indexed content `x[..]` as mutable -:4 let b = &mut x[1]; - ^~~~ -error: aborting due to 2 previous errors -``` - -While it was plausible that borrowck could understand this simple case, it's -pretty clearly hopeless for borrowck to understand disjointness in general -container types like a tree, especially if distinct keys actually *do* map -to the same value. - -In order to "teach" borrowck that what we're doing is ok, we need to drop down -to unsafe code. For instance, mutable slices expose a `split_at_mut` function -that consumes the slice and returns *two* mutable slices. One for everything to -the left of the index, and one for everything to the right. Intuitively we know -this is safe because the slices don't overlap, and therefore alias. However -the implementation requires some unsafety: - -```rust,ignore -fn split_at_mut(&mut self, mid: usize) -> (&mut [T], &mut [T]) { - let len = self.len(); - let ptr = self.as_mut_ptr(); - assert!(mid <= len); - unsafe { - (from_raw_parts_mut(ptr, mid), - from_raw_parts_mut(ptr.offset(mid as isize), len - mid)) - } -} -``` - -This is pretty plainly dangerous. We use transmute to duplicate the slice with -an *unbounded* lifetime, so that it can be treated as disjoint from the other -until we unify them when we return. - -However more subtle is how iterators that yield mutable references work. -The iterator trait is defined as follows: - -```rust -trait Iterator { - type Item; - - fn next(&mut self) -> Option; -} -``` - -Given this definition, Self::Item has *no* connection to `self`. This means that -we can call `next` several times in a row, and hold onto all the results -*concurrently*. This is perfectly fine for by-value iterators, which have -exactly these semantics. It's also actually fine for shared references, as they -admit arbitrarily many references to the same thing (although the iterator needs -to be a separate object from the thing being shared). - -But mutable references make this a mess. At first glance, they might seem -completely incompatible with this API, as it would produce multiple mutable -references to the same object! - -However it actually *does* work, exactly because iterators are one-shot objects. -Everything an IterMut yields will be yielded *at most* once, so we don't -*actually* ever yield multiple mutable references to the same piece of data. - -Perhaps surprisingly, mutable iterators *don't* require unsafe code to be -implemented for many types! - -For instance here's a singly linked list: - -```rust -# fn main() {} -type Link = Option>>; - -struct Node { - elem: T, - next: Link, -} - -pub struct LinkedList { - head: Link, -} - -pub struct IterMut<'a, T: 'a>(Option<&'a mut Node>); - -impl LinkedList { - fn iter_mut(&mut self) -> IterMut { - IterMut(self.head.as_mut().map(|node| &mut **node)) - } -} - -impl<'a, T> Iterator for IterMut<'a, T> { - type Item = &'a mut T; - - fn next(&mut self) -> Option { - self.0.take().map(|node| { - self.0 = node.next.as_mut().map(|node| &mut **node); - &mut node.elem - }) - } -} -``` - -Here's a mutable slice: - -```rust -use std::mem; - -pub struct IterMut<'a, T: 'a>(&'a mut[T]); - -impl<'a, T> Iterator for IterMut<'a, T> { - type Item = &'a mut T; - - fn next(&mut self) -> Option { - let slice = mem::replace(&mut self.0, &mut []); - if slice.is_empty() { return None; } - - let (l, r) = slice.split_at_mut(1); - self.0 = r; - l.get_mut(0) - } -} - -impl<'a, T> DoubleEndedIterator for IterMut<'a, T> { - fn next_back(&mut self) -> Option { - let slice = mem::replace(&mut self.0, &mut []); - if slice.is_empty() { return None; } - - let new_len = slice.len() - 1; - let (l, r) = slice.split_at_mut(new_len); - self.0 = l; - r.get_mut(0) - } -} -``` - -And here's a binary tree: - -```rust -use std::collections::VecDeque; - -type Link = Option>>; - -struct Node { - elem: T, - left: Link, - right: Link, -} - -pub struct Tree { - root: Link, -} - -struct NodeIterMut<'a, T: 'a> { - elem: Option<&'a mut T>, - left: Option<&'a mut Node>, - right: Option<&'a mut Node>, -} - -enum State<'a, T: 'a> { - Elem(&'a mut T), - Node(&'a mut Node), -} - -pub struct IterMut<'a, T: 'a>(VecDeque>); - -impl Tree { - pub fn iter_mut(&mut self) -> IterMut { - let mut deque = VecDeque::new(); - self.root.as_mut().map(|root| deque.push_front(root.iter_mut())); - IterMut(deque) - } -} - -impl Node { - pub fn iter_mut(&mut self) -> NodeIterMut { - NodeIterMut { - elem: Some(&mut self.elem), - left: self.left.as_mut().map(|node| &mut **node), - right: self.right.as_mut().map(|node| &mut **node), - } - } -} - - -impl<'a, T> Iterator for NodeIterMut<'a, T> { - type Item = State<'a, T>; - - fn next(&mut self) -> Option { - match self.left.take() { - Some(node) => Some(State::Node(node)), - None => match self.elem.take() { - Some(elem) => Some(State::Elem(elem)), - None => match self.right.take() { - Some(node) => Some(State::Node(node)), - None => None, - } - } - } - } -} - -impl<'a, T> DoubleEndedIterator for NodeIterMut<'a, T> { - fn next_back(&mut self) -> Option { - match self.right.take() { - Some(node) => Some(State::Node(node)), - None => match self.elem.take() { - Some(elem) => Some(State::Elem(elem)), - None => match self.left.take() { - Some(node) => Some(State::Node(node)), - None => None, - } - } - } - } -} - -impl<'a, T> Iterator for IterMut<'a, T> { - type Item = &'a mut T; - fn next(&mut self) -> Option { - loop { - match self.0.front_mut().and_then(|node_it| node_it.next()) { - Some(State::Elem(elem)) => return Some(elem), - Some(State::Node(node)) => self.0.push_front(node.iter_mut()), - None => if let None = self.0.pop_front() { return None }, - } - } - } -} - -impl<'a, T> DoubleEndedIterator for IterMut<'a, T> { - fn next(&mut self) -> Option { - loop { - match self.0.back_mut().and_then(|node_it| node_it.next_back()) { - Some(State::Elem(elem)) => return Some(elem), - Some(State::Node(node)) => self.0.push_back(node.iter_mut()), - None => if let None = self.0.pop_back() { return None }, - } - } - } -} -``` - -All of these are completely safe and work on stable Rust! This ultimately -falls out of the simple struct case we saw before: Rust understands that you -can safely split a mutable reference into subfields. We can then encode -permanently consuming a reference via Options (or in the case of slices, -replacing with an empty slice). diff --git a/src/doc/tarpl/unchecked-uninit.md b/src/doc/tarpl/unchecked-uninit.md index d0397c37190..da9fb294a1e 100644 --- a/src/doc/tarpl/unchecked-uninit.md +++ b/src/doc/tarpl/unchecked-uninit.md @@ -15,11 +15,11 @@ initialization. Unfortunately, this opens us up to all kinds of problems. Assignment has a different meaning to Rust based on whether it believes that a variable is -initialized or not. If it's uninitialized, then Rust will semantically just -memcopy the bits over the uninitialized ones, and do nothing else. However if Rust -believes a value to be initialized, it will try to `Drop` the old value! -Since we've tricked Rust into believing that the value is initialized, we -can no longer safely use normal assignment. +initialized or not. If it's believed uninitialized, then Rust will semantically +just memcopy the bits over the uninitialized ones, and do nothing else. However +if Rust believes a value to be initialized, it will try to `Drop` the old value! +Since we've tricked Rust into believing that the value is initialized, we can no +longer safely use normal assignment. This is also a problem if you're working with a raw system allocator, which returns a pointer to uninitialized memory. -- cgit 1.4.1-3-g733a5