Re: [rust-dev] RFC: Stealing: lexically-scoped temporary violation of linearity
Another thought on this. Currently, either the compiler is satisfies that the code is 100% safe, or we slap an unsafe keyword around the code and put 100% of the responsibility on the programmer, with no support from the Rust system. Wouldn't it make sense to have a not statically safe, but verified at run time safety as a middle ground? In the context of the stolen proposal, when one steals a pointer, the original location could be set to null, and only be restored to a non-null pointer when the value is put back. This means any access to it would cause an exception - which is what one would intuitively expect a hold to behave like. I have a feeling that there is a non-trivial amount of code which is actually safe but would impossible to convince the compiler it is statically safe. Surely having run-time safety in such cases is better than none at all...? On Sat, Aug 31, 2013 at 3:50 AM, Patrick Walton pwal...@mozilla.com wrote: On 8/30/13 3:39 PM, Patrick Walton wrote: Thoughts? Does this seem useful? Are there soundness issues I didn't notice? Brian pointed out a massive soundness hole in this, unfortunately. The problem is that you can read from the original locations; the right to read is not shut off during the borrow. I think the fix would have to be to replace this with some sort of generalized swap operation. Patrick __**_ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/**listinfo/rust-devhttps://mail.mozilla.org/listinfo/rust-dev ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] RFC: Stealing: lexically-scoped temporary violation of linearity
On 9/7/13 8:39 AM, Oren Ben-Kiki wrote: I have a feeling that there is a non-trivial amount of code which is actually safe but would impossible to convince the compiler it is statically safe. Surely having run-time safety in such cases is better than none at all...? I would be fine with this, but one big problem is that null pointer dereferences are undefined behavior in LLVM. Patrick ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] RFC: Stealing: lexically-scoped temporary violation of linearity
Is there any system in actual use where actually dereferencing a null pointer will not cause an exception? I mean, _sure_, the C spec says the result is undefined, but isn't this just a leftover from the bad old days, like also supporting non-byte-addressible machines (with non-power-of-two word size!), and other such horribleness? If in practice on any machine today (X86, ARM, PowerPC, MIPS, SPARC, ...) every null pointer will fault (which I strongly hope will...), then I'd be quite happy in saying formally that accessing a hole leads to undefined behavior and make good use of knowledge that any such access will, in fact, fault, on any machine I might be coding to today. On Sat, Sep 7, 2013 at 6:55 PM, Patrick Walton pwal...@mozilla.com wrote: On 9/7/13 8:39 AM, Oren Ben-Kiki wrote: I have a feeling that there is a non-trivial amount of code which is actually safe but would impossible to convince the compiler it is statically safe. Surely having run-time safety in such cases is better than none at all...? I would be fine with this, but one big problem is that null pointer dereferences are undefined behavior in LLVM. Patrick ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] RFC: Stealing: lexically-scoped temporary violation of linearity
On Sat, Sep 7, 2013 at 12:09 PM, Oren Ben-Kiki o...@ben-kiki.org wrote: If in practice on any machine today (X86, ARM, PowerPC, MIPS, SPARC, ...) every null pointer will fault (which I strongly hope will...), then I'd be quite happy in saying formally that accessing a hole leads to undefined behavior and make good use of knowledge that any such access will, in fact, fault, on any machine I might be coding to today. You get a segmentation fault on Linux because the first page is marked read-only for userland processes. It's valid on almost any hardware to dereference a pointer equal to zero, which is how LLVM defines the null pointer. However, LLVM explicitly considers a dereference of the null pointer to be undefined behaviour so it doesn't matter how it could or couldn't be implemented in hardware. ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] RFC: Stealing: lexically-scoped temporary violation of linearity
I miss-spoke; when I said machine I meant platform (combination of HW and SW). Is unintentionally dereferencing a null pointer a silent error on any existing platform? But isn't a very good question either. A better one would be: Would it be _useful_ to define `steal` and use it in programs, such that it triggers a null pointer dereference (undefined behavior and all) if someone tries to access the hole? This is a softer question and I suspect the answer is yes - at least until a better way to safely update structures in-place is found... On Sat, Sep 7, 2013 at 7:20 PM, Daniel Micay danielmi...@gmail.com wrote: On Sat, Sep 7, 2013 at 12:09 PM, Oren Ben-Kiki o...@ben-kiki.org wrote: If in practice on any machine today (X86, ARM, PowerPC, MIPS, SPARC, ...) every null pointer will fault (which I strongly hope will...), then I'd be quite happy in saying formally that accessing a hole leads to undefined behavior and make good use of knowledge that any such access will, in fact, fault, on any machine I might be coding to today. You get a segmentation fault on Linux because the first page is marked read-only for userland processes. It's valid on almost any hardware to dereference a pointer equal to zero, which is how LLVM defines the null pointer. However, LLVM explicitly considers a dereference of the null pointer to be undefined behaviour so it doesn't matter how it could or couldn't be implemented in hardware. ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] RFC: Stealing: lexically-scoped temporary violation of linearity
On Sat, Sep 7, 2013 at 4:15 PM, Oren Ben-Kiki o...@ben-kiki.org wrote: I miss-spoke; when I said machine I meant platform (combination of HW and SW). Is unintentionally dereferencing a null pointer a silent error on any existing platform? Yes, it's only a segmentation fault in userland code on platforms where the kernel is set up to make the lowest page read-only. Rust still needs to be memory safe in a kernel. But isn't a very good question either. A better one would be: Would it be _useful_ to define `steal` and use it in programs, such that it triggers a null pointer dereference (undefined behavior and all) if someone tries to access the hole? This is a softer question and I suspect the answer is yes - at least until a better way to safely update structures in-place is found... It would be undefined behaviour, so it wouldn't be useful. Rust is a memory safe language and can't allow safe code to generate LLVM IR invoking undefined behaviour. ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] RFC: Stealing: lexically-scoped temporary violation of linearity
To clarify why undefined behavior is really bad in practice: if LLVM ever detects that your code performs undefined behavior according to the standard, it is *designed* to take full advantage of that fact when making optimizations. In other words, all hell will break lose, in potentially very complicated and subtle ways. Geoffrey On Sep 7, 2013, at 1:22 PM, Daniel Micay danielmi...@gmail.com wrote: On Sat, Sep 7, 2013 at 4:15 PM, Oren Ben-Kiki o...@ben-kiki.org wrote: I miss-spoke; when I said machine I meant platform (combination of HW and SW). Is unintentionally dereferencing a null pointer a silent error on any existing platform? Yes, it's only a segmentation fault in userland code on platforms where the kernel is set up to make the lowest page read-only. Rust still needs to be memory safe in a kernel. But isn't a very good question either. A better one would be: Would it be _useful_ to define `steal` and use it in programs, such that it triggers a null pointer dereference (undefined behavior and all) if someone tries to access the hole? This is a softer question and I suspect the answer is yes - at least until a better way to safely update structures in-place is found... It would be undefined behaviour, so it wouldn't be useful. Rust is a memory safe language and can't allow safe code to generate LLVM IR invoking undefined behaviour. ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev signature.asc Description: Message signed with OpenPGP using GPGMail ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] RFC: Stealing: lexically-scoped temporary violation of linearity
On Sat, Sep 7, 2013 at 4:27 PM, Geoffrey Irving irv...@naml.us wrote: To clarify why undefined behavior is really bad in practice: if LLVM ever detects that your code performs undefined behavior according to the standard, it is *designed* to take full advantage of that fact when making optimizations. In other words, all hell will break lose, in potentially very complicated and subtle ways. Geoffrey Note that there's no detection of undefined behaviour or optimizations based upon it being detected. LLVM simply operates on valid LLVM bytecode, and if it performs undefined behaviour it is not valid LLVM bytecode. The optimization passes and code generation will base all of their assumptions on the invariants provided by the specification, including that null pointers are never dereferenced. ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] RFC: Stealing: lexically-scoped temporary violation of linearity
Alas. So I guess it all depends on someone finding a smart safe way to generalize the swap operation, or something... as things stand, it is extremely difficult to efficiently and safely implement complex nested containers. I will admit I am using the `steal` function for now, it just makes things so much easier, but I know I'll have to pay for my sins down the line... On Sat, Sep 7, 2013 at 11:27 PM, Geoffrey Irving irv...@naml.us wrote: To clarify why undefined behavior is really bad in practice: if LLVM ever detects that your code performs undefined behavior according to the standard, it is *designed* to take full advantage of that fact when making optimizations. In other words, all hell will break lose, in potentially very complicated and subtle ways. Geoffrey On Sep 7, 2013, at 1:22 PM, Daniel Micay danielmi...@gmail.com wrote: On Sat, Sep 7, 2013 at 4:15 PM, Oren Ben-Kiki o...@ben-kiki.org wrote: I miss-spoke; when I said machine I meant platform (combination of HW and SW). Is unintentionally dereferencing a null pointer a silent error on any existing platform? Yes, it's only a segmentation fault in userland code on platforms where the kernel is set up to make the lowest page read-only. Rust still needs to be memory safe in a kernel. But isn't a very good question either. A better one would be: Would it be _useful_ to define `steal` and use it in programs, such that it triggers a null pointer dereference (undefined behavior and all) if someone tries to access the hole? This is a softer question and I suspect the answer is yes - at least until a better way to safely update structures in-place is found... It would be undefined behaviour, so it wouldn't be useful. Rust is a memory safe language and can't allow safe code to generate LLVM IR invoking undefined behaviour. ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] RFC: Stealing: lexically-scoped temporary violation of linearity
On Sep 7, 2013, at 1:32 PM, Daniel Micay danielmi...@gmail.com wrote: On Sat, Sep 7, 2013 at 4:27 PM, Geoffrey Irving irv...@naml.us wrote: To clarify why undefined behavior is really bad in practice: if LLVM ever detects that your code performs undefined behavior according to the standard, it is *designed* to take full advantage of that fact when making optimizations. In other words, all hell will break lose, in potentially very complicated and subtle ways. Geoffrey Note that there's no detection of undefined behaviour or optimizations based upon it being detected. LLVM simply operates on valid LLVM bytecode, and if it performs undefined behaviour it is not valid LLVM bytecode. The optimization passes and code generation will base all of their assumptions on the invariants provided by the specification, including that null pointers are never dereferenced. That may be true; I got the opposite impression from this article: http://blog.llvm.org/2011/05/what-every-c-programmer-should-know_21.html Geoffrey signature.asc Description: Message signed with OpenPGP using GPGMail ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] RFC: Stealing: lexically-scoped temporary violation of linearity
On Sat, Sep 7, 2013 at 4:37 PM, Geoffrey Irving irv...@naml.us wrote: On Sep 7, 2013, at 1:32 PM, Daniel Micay danielmi...@gmail.com wrote: On Sat, Sep 7, 2013 at 4:27 PM, Geoffrey Irving irv...@naml.us wrote: To clarify why undefined behavior is really bad in practice: if LLVM ever detects that your code performs undefined behavior according to the standard, it is *designed* to take full advantage of that fact when making optimizations. In other words, all hell will break lose, in potentially very complicated and subtle ways. Geoffrey Note that there's no detection of undefined behaviour or optimizations based upon it being detected. LLVM simply operates on valid LLVM bytecode, and if it performs undefined behaviour it is not valid LLVM bytecode. The optimization passes and code generation will base all of their assumptions on the invariants provided by the specification, including that null pointers are never dereferenced. That may be true; I got the opposite impression from this article: http://blog.llvm.org/2011/05/what-every-c-programmer-should-know_21.html Geoffrey You're getting a very wrong impression if you think it optimizes based on those assumptions only when it can detect undefined behaviour. It completely ignores the possibility of undefined behaviour in the optimization passes by assuming all of the invariants required for the bytecode to be valid hold true. The `-fcatch-undefined-behaviour` switch inserts runtime checks. ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] RFC: Stealing: lexically-scoped temporary violation of linearity
On Sat, Sep 7, 2013 at 4:42 PM, Daniel Micay danielmi...@gmail.com wrote: On Sat, Sep 7, 2013 at 4:37 PM, Geoffrey Irving irv...@naml.us wrote: On Sep 7, 2013, at 1:32 PM, Daniel Micay danielmi...@gmail.com wrote: On Sat, Sep 7, 2013 at 4:27 PM, Geoffrey Irving irv...@naml.us wrote: To clarify why undefined behavior is really bad in practice: if LLVM ever detects that your code performs undefined behavior according to the standard, it is *designed* to take full advantage of that fact when making optimizations. In other words, all hell will break lose, in potentially very complicated and subtle ways. Geoffrey Note that there's no detection of undefined behaviour or optimizations based upon it being detected. LLVM simply operates on valid LLVM bytecode, and if it performs undefined behaviour it is not valid LLVM bytecode. The optimization passes and code generation will base all of their assumptions on the invariants provided by the specification, including that null pointers are never dereferenced. That may be true; I got the opposite impression from this article: http://blog.llvm.org/2011/05/what-every-c-programmer-should-know_21.html Geoffrey You're getting a very wrong impression if you think it optimizes based on those assumptions only when it can detect undefined behaviour. It completely ignores the possibility of undefined behaviour in the optimization passes by assuming all of the invariants required for the bytecode to be valid hold true. The `-fcatch-undefined-behaviour` switch inserts runtime checks. Note that `clang` generating traps on certain operations left undefined by C to aid in debugging is unrelated to Rust, because we don't compile to C and then compile with `clang`. There are no exceptions to the undefined behaviour rules for us. ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] RFC: Stealing: lexically-scoped temporary violation of linearity
On Sep 7, 2013, at 1:42 PM, Daniel Micay danielmi...@gmail.com wrote: On Sat, Sep 7, 2013 at 4:37 PM, Geoffrey Irving irv...@naml.us wrote: On Sep 7, 2013, at 1:32 PM, Daniel Micay danielmi...@gmail.com wrote: On Sat, Sep 7, 2013 at 4:27 PM, Geoffrey Irving irv...@naml.us wrote: To clarify why undefined behavior is really bad in practice: if LLVM ever detects that your code performs undefined behavior according to the standard, it is *designed* to take full advantage of that fact when making optimizations. In other words, all hell will break lose, in potentially very complicated and subtle ways. Geoffrey Note that there's no detection of undefined behaviour or optimizations based upon it being detected. LLVM simply operates on valid LLVM bytecode, and if it performs undefined behaviour it is not valid LLVM bytecode. The optimization passes and code generation will base all of their assumptions on the invariants provided by the specification, including that null pointers are never dereferenced. That may be true; I got the opposite impression from this article: http://blog.llvm.org/2011/05/what-every-c-programmer-should-know_21.html Geoffrey You're getting a very wrong impression if you think it optimizes based on those assumptions only when it can detect undefined behaviour. It completely ignores the possibility of undefined behaviour in the optimization passes by assuming all of the invariants required for the bytecode to be valid hold true. The `-fcatch-undefined-behaviour` switch inserts runtime checks. I think we're saying the same thing: I didn't intend to imply that it optimizes based on those assumptions only if it can prove that undefined behavior never occurs. If it detects undefined behavior along certain paths, it will assume those paths can never occur, and then propagate those assumptions backwards through the program in an attempt to make simplifications. Thus, a null pointer access somewhere could easily complete a weirdly incorrect assumption causing a previous branch to be taken incorrectly. Geoffrey signature.asc Description: Message signed with OpenPGP using GPGMail ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] RFC: Stealing: lexically-scoped temporary violation of linearity
On Sat, Sep 7, 2013 at 4:47 PM, Geoffrey Irving irv...@naml.us wrote: On Sep 7, 2013, at 1:42 PM, Daniel Micay danielmi...@gmail.com wrote: On Sat, Sep 7, 2013 at 4:37 PM, Geoffrey Irving irv...@naml.us wrote: On Sep 7, 2013, at 1:32 PM, Daniel Micay danielmi...@gmail.com wrote: On Sat, Sep 7, 2013 at 4:27 PM, Geoffrey Irving irv...@naml.us wrote: To clarify why undefined behavior is really bad in practice: if LLVM ever detects that your code performs undefined behavior according to the standard, it is *designed* to take full advantage of that fact when making optimizations. In other words, all hell will break lose, in potentially very complicated and subtle ways. Geoffrey Note that there's no detection of undefined behaviour or optimizations based upon it being detected. LLVM simply operates on valid LLVM bytecode, and if it performs undefined behaviour it is not valid LLVM bytecode. The optimization passes and code generation will base all of their assumptions on the invariants provided by the specification, including that null pointers are never dereferenced. That may be true; I got the opposite impression from this article: http://blog.llvm.org/2011/05/what-every-c-programmer-should-know_21.html Geoffrey You're getting a very wrong impression if you think it optimizes based on those assumptions only when it can detect undefined behaviour. It completely ignores the possibility of undefined behaviour in the optimization passes by assuming all of the invariants required for the bytecode to be valid hold true. The `-fcatch-undefined-behaviour` switch inserts runtime checks. I think we're saying the same thing: I didn't intend to imply that it optimizes based on those assumptions only if it can prove that undefined behavior never occurs. If it detects undefined behavior along certain paths, it will assume those paths can never occur, and then propagate those assumptions backwards through the program in an attempt to make simplifications. Thus, a null pointer access somewhere could easily complete a weirdly incorrect assumption causing a previous branch to be taken incorrectly. Geoffrey Ah okay, we're on the same page then :). ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] RFC: Stealing: lexically-scoped temporary violation of linearity
On Fri, Aug 30, 2013 at 05:50:40PM -0700, Patrick Walton wrote: Brian pointed out a massive soundness hole in this, unfortunately. The problem is that you can read from the original locations; the right to read is not shut off during the borrow. I think the fix would have to be to replace this with some sort of generalized swap operation. One thing that I've been wanting to do is to generalize our move rules. Currently, we do not permit you to move data from borrowed locations -- but we COULD safely permit this, under certain conso long as you ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] RFC: Stealing: lexically-scoped temporary violation of linearity
Sorry, sent that e-mail prematurely. Short version is that I think we could generalize our move rules somewhat precisely for the purpose of accommodating this situation, but the question is whether it would ultimately be expressive enough. There would have to be rules against making fn calls, reading const pointers, and similar things while borrowed data is in a moved out state. Ultimately, it probably winds up being equivalent to a multi-swap primitive, so perhaps that's a better approach anyhow! (Plus it avoids the need to worry about what to do in the case of failure, I haven't really about that before) Niko On Mon, Sep 02, 2013 at 08:04:17PM -0400, Niko Matsakis wrote: On Fri, Aug 30, 2013 at 05:50:40PM -0700, Patrick Walton wrote: Brian pointed out a massive soundness hole in this, unfortunately. The problem is that you can read from the original locations; the right to read is not shut off during the borrow. I think the fix would have to be to replace this with some sort of generalized swap operation. One thing that I've been wanting to do is to generalize our move rules. Currently, we do not permit you to move data from borrowed locations -- but we COULD safely permit this, under certain conso long as you ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] RFC: Stealing: lexically-scoped temporary violation of linearity
Since swap seems to have its own problems - would it be possible to tweak the stealing idea so the compiler would know there's a burrowed mutable pointer to the hole, effectively preventing further access to it in the vulnerable block? I really would like to be able to use this approach, it really improved my code... On Sat, Aug 31, 2013 at 3:50 AM, Patrick Walton pwal...@mozilla.com wrote: On 8/30/13 3:39 PM, Patrick Walton wrote: Thoughts? Does this seem useful? Are there soundness issues I didn't notice? Brian pointed out a massive soundness hole in this, unfortunately. The problem is that you can read from the original locations; the right to read is not shut off during the borrow. I think the fix would have to be to replace this with some sort of generalized swap operation. Patrick __**_ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/**listinfo/rust-devhttps://mail.mozilla.org/listinfo/rust-dev ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] RFC: Stealing: lexically-scoped temporary violation of linearity
On 9/1/13 8:23 AM, Oren Ben-Kiki wrote: Since swap seems to have its own problems - would it be possible to tweak the stealing idea so the compiler would know there's a burrowed mutable pointer to the hole, effectively preventing further access to it in the vulnerable block? I really would like to be able to use this approach, it really improved my code... What's the problem with a generalized swap (= 2 elements, any permutation) for your use case? Patrick ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] RFC: Stealing: lexically-scoped temporary violation of linearity
I'd settle for the ability to say: update_in_place(foo.owned_pointer, fn(~T)
- ~T) - surely this would be safe?
That would interact with Drop in a way that could cause a memory violation
after a task failure. The problem is that if you allow a moved value to be
destroyed before something else is swapped into an owned pointer, the task
could fail before the new value got put back in. Then a drop function could
try to access the destroyed value during unwind. Depending on how owned boxes
work, it still might try to free the memory twice, even if Drop was not
implemented.
An illustration--if the update_in_place function existed, this code would
violate memory safety without an unsafe:
use std::cast;
fn move_outT(x:~T) {
// do stuff with x...or not--either way, we're not returning it out, so x is
// destroyed at the end of this function
}
struct Bomb {
x:~str
}
impl Drop for Bomb {
fn drop(self) {
println(x);
}
}
fn violate_memory() {
// If the update_in_place function existed, it could cause a memory
// violation like so:
let mut b = ~Bomb{x: ~Kaboom}
do update_in_place(mut b) |t| {
move_out(t);
// At this point the memory pointed to by the owned pointer b.x is
// destroyed...but nothing else has been put its place! The
// compiler will prevent us from accessing b or t here, but...
fail!();
// The stack will be unwound, and the Bomb's drop function will
// be called. It will attempt to access the owned value that
// was already destroyed.
}
}
On Aug 30, 2013, at 8:58 PM, Oren Ben-Kiki wrote:
Sigh, I guess it was too good to be true :-(
Speaking of which, a secondary problem I encountered when doing this sort of
thing, is the Once function issue listed in
https://github.com/mozilla/rust/wiki/Doc-under-construction-FAQ.
Wouldn't it be possible to say, for example, that ~fn can only be invoked
once to resolve this issue?
On Sat, Aug 31, 2013 at 3:50 AM, Patrick Walton pwal...@mozilla.com wrote:
On 8/30/13 3:39 PM, Patrick Walton wrote:
Thoughts? Does this seem useful? Are there soundness issues I didn't
notice?
Brian pointed out a massive soundness hole in this, unfortunately. The
problem is that you can read from the original locations; the right to read
is not shut off during the borrow. I think the fix would have to be to
replace this with some sort of generalized swap operation.
Patrick
___
Rust-dev mailing list
Rust-dev@mozilla.org
https://mail.mozilla.org/listinfo/rust-dev
___
Rust-dev mailing list
Rust-dev@mozilla.org
https://mail.mozilla.org/listinfo/rust-dev
___
Rust-dev mailing list
Rust-dev@mozilla.org
https://mail.mozilla.org/listinfo/rust-dev
[rust-dev] RFC: Stealing: lexically-scoped temporary violation of linearity
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
Rust-dev@mozilla.org
https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] RFC: Stealing: lexically-scoped temporary violation of linearity
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 pwal...@mozilla.com 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
Rust-dev@mozilla.org
https://mail.mozilla.org/**listinfo/rust-devhttps://mail.mozilla.org/listinfo/rust-dev
___
Rust-dev mailing list
Rust-dev@mozilla.org
https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] RFC: Stealing: lexically-scoped temporary violation of linearity
On 8/30/13 3:39 PM, Patrick Walton wrote: Thoughts? Does this seem useful? Are there soundness issues I didn't notice? Brian pointed out a massive soundness hole in this, unfortunately. The problem is that you can read from the original locations; the right to read is not shut off during the borrow. I think the fix would have to be to replace this with some sort of generalized swap operation. Patrick ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] RFC: Stealing: lexically-scoped temporary violation of linearity
Sigh, I guess it was too good to be true :-( I'd settle for the ability to say: update_in_place(foo.owned_pointer, fn(~T) - ~T) - surely this would be safe? Speaking of which, a secondary problem I encountered when doing this sort of thing, is the Once function issue listed in https://github.com/mozilla/rust/wiki/Doc-under-construction-FAQ. Wouldn't it be possible to say, for example, that ~fn can only be invoked once to resolve this issue? On Sat, Aug 31, 2013 at 3:50 AM, Patrick Walton pwal...@mozilla.com wrote: On 8/30/13 3:39 PM, Patrick Walton wrote: Thoughts? Does this seem useful? Are there soundness issues I didn't notice? Brian pointed out a massive soundness hole in this, unfortunately. The problem is that you can read from the original locations; the right to read is not shut off during the borrow. I think the fix would have to be to replace this with some sort of generalized swap operation. Patrick __**_ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/**listinfo/rust-devhttps://mail.mozilla.org/listinfo/rust-dev ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
