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
