I just tested this in my code, it solved a sticky problem I had with updating owned data nested deep inside a tree-ish container. My original solution wasn't very nice (it just compromised on efficiency and copied too much data around). The new code is shorter and more efficient (no copies! yey!).
So, +1 for usefulness, and thanks! I wish I could also attest to the correctness, but that is harder to prove... On Sat, Aug 31, 2013 at 1:39 AM, Patrick Walton <[email protected]> wrote: > Hi everyone, > > I've been tossing around an idea for a library utility designed to make > unique pointers easier to use, especially for balanced binary search trees > and the like. The core of the idea is that I conjecture it's safe to > temporarily violate linearity *while the locations in question are > borrowed*, as long as linearity is *dynamically* preserved once the borrow > ends. > > First off, let me motivate this with an example, showing that this > generalizes "swap": > > struct Test { > a: ~str, > b: ~str, > } > > fn main() { > let mut test = Test { > a: ~"Burma", > b: ~"Shave", > }; > { > let (a, a_loc) = steal(&mut test.a); > let (b, b_loc) = steal(&mut test.b); > println(a); // prints "Burma" > println(b); // prints "Shave" > a_loc.put_back(b); > b_loc.put_back(a); > } > println(test.a); // prints "Shave" > println(test.b); // prints "Burma" > } > > Concretely, what "steal" does is that it takes a mutable borrow and > returns two things: (1) a shallow copy of the referent, temporarily > violating linearity; (2) a "stolen location" which must be filled with a > value of the same type as the referent via the `put_back` method before the > scope ends. If the scope ends (i.e. the borrow expires) without calling > `put_back` on a stolen location, then task failure occurs. For example, > this program fails (with the above definition of `Test`): > > fn main() { > let mut test = Test { > a: ~"Burma", > b: ~"Shave", > }; > { > let (a, a_loc) = steal(&mut test.a); > let (b, b_loc) = steal(&mut test.b); > a_loc.put_back(b); > } // dynamic failure: "b_loc" was not filled > } > > The idea behind this is to allow complex "pointer rewirings" such as those > that self-balancing binary search trees want to be expressed in a natural > way without a tricky series of swaps. > > The thing that initially seems questionable for soundness is that, while > borrowed and while linearity is violated, the original value is still > readable (although not immutably or mutably borrowable). I believe this is > OK, even in the fact of LLVM alias optimizations, because while something > is borrowed linearity is no longer guaranteed anyhow. > > The implementation is quite small and simple and fits here: > > struct Stolen<'self,T> { > priv location: &'self mut T, > } > > #[unsafe_destructor] > impl<'self,T> Drop for Stolen<'self,T> { > fn drop(&self) { > fail!("stolen") > } > } > > impl<'self,T> Stolen<'self,T> { > fn put_back(self, value: T) { > unsafe { > intrinsics::move_val_init(**self.location, value); > cast::forget(self) > } > } > } > > fn steal<'a,T>(value: &'a mut T) -> (T, Stolen<'a,T>) { > unsafe { > (cast::transmute_copy(value), Stolen { > location: value, > }) > } > } > > Thoughts? Does this seem useful? Are there soundness issues I didn't > notice? > > Patrick > ______________________________**_________________ > Rust-dev mailing list > [email protected] > https://mail.mozilla.org/**listinfo/rust-dev<https://mail.mozilla.org/listinfo/rust-dev> >
_______________________________________________ Rust-dev mailing list [email protected] https://mail.mozilla.org/listinfo/rust-dev
