A better type system

classic Classic list List threaded Threaded
21 messages Options
12
Reply | Threaded
Open this post in threaded view
|

A better type system

Tommi Tissari
It certainly feels like a failure of the Rust type system that you cannot have multiple mutating references to the same variable when the variable is accessed only from a single thread. I know the reason for this is to prevent iterator invalidation, but this is too blunt of an instrument.

Iterator invalidation (as it's known in C++) is a risk to memory safety only when some of the memory that is accessible through an iterator (or a reference) is deallocated. A better type system would make a distinction between those expressions that may deallocate and those that cannot. Then, when multiple mutating references pointed to the same variable, the compiler would disallow only the use of the potentially deallocating expressions through those references.

If a variable may be accessed concurrently from multiple threads, only then would the current "no mutating references allowed to that variable" -rule be enforced.

Sorry for the brevity, I'm writing this from a phone and I haven't thought of this issue very thoroughly.


Reply | Threaded
Open this post in threaded view
|

A better type system

Patrick Walton-2
On 5/31/14 10:36 AM, Tommi wrote:
> It certainly feels like a failure of the Rust type system that you
> cannot have multiple mutating references to the same variable when
> the variable is accessed only from a single thread. I know the reason
> for this is to prevent iterator invalidation, but this is too blunt
> of an instrument.

No. Iterator invalidation is not the only reason.

> Iterator invalidation (as it's known in C++) is a risk to memory
> safety only when some of the memory that is accessible through an
> iterator (or a reference) is deallocated. A better type system would
> make a distinction between those expressions that may deallocate and
> those that cannot. Then, when multiple mutating references pointed to
> the same variable, the compiler would disallow only the use of the
> potentially deallocating expressions through those references.

Again, this is wrong. Iterator invalidation is the way I like to explain
the rule, but it is by no means the only thing that can go wrong if you
have two &mut references to the same location. If you have two &mut
pointers to the same memory address, it is quite easy to write
cast::transmute in safe code without any iterators or memory being
deallocated at all.

Patrick

Reply | Threaded
Open this post in threaded view
|

A better type system

Alex Crichton-2
In reply to this post by Tommi Tissari
> Sorry for the brevity, I'm writing this from a phone and I haven't thought of this issue very thoroughly.

You appear to dislike one of the most fundamental features of Rust, so
I would encourage you to think through ideas such as this before
hastily posting to the mailing list.

The current iteration of Rust has had a great deal of thought and
design poured into it, as well as having at least thousands of man
hours of effort being put behind it. Casually stating, with little
prior thought, that large chunks of this effort are flatly wrong is
disrespectful to those who have put so much time and effort into the
project.

We always welcome and encourage thoughtful reconsiderations of the
design decisions of Rust, but these must be performed in a
constructive and well-thought-out manner. There have been many times
in the past where the design decisions of Rust have been reversed or
redone, but these were always accompanied with a large amount of
research to fuel the changes.

If you have concrete suggestions, we have an RFC process in place for
proposing new changes to the language while gathering feedback at the
same time.

Reply | Threaded
Open this post in threaded view
|

A better type system

Matthieu Monrocq
Iterator invalidation is a sweet example, which strikes at the heart of C++
developer (those who never ran into it, please raise your hands).


However it is just an example, anytime you have aliasing + mutability, you
may have either memory issues or logical bugs.

Another example of memory issue:

    foo(left: &Option<Box<str>>, right: &mut Option<Box<str>>) {
        let ptr: &str = *left.unwrap();

        right = None;

        match ptr.len() { // Watch out! if left and right alias, then ptr
is no a dangling reference!
        // ...
        }
    }

The issue can actually occur in other ways: replace Box<str> by enum Point
{ Integral(int, int), Floating(f64, f64) } and you could manage to write
integral into floats or vice-versa, which is memory-corruption, not
segmentation fault.


The Rust type system allows, at the moment, to ensure that you never have
both aliasing and mutability. Mostly at compile-time, and at run-time
through a couple unsafe hatches (Cell, RefCell, Mutex, ...).

I admit it is jarring, and constraining. However the guarantee you get in
exchange (memory-safe & thread-safe) is extremely important.


> I'm writing this from a phone and I haven't thought of this issue very
thoroughly.

Well, think a bit more. If you manage to produce a more refined
type-system, I'd love to hear about it. In the mean time though, I advise
caution in criticizing the existing: it has the incredible advantage of
working.



On Sat, May 31, 2014 at 7:54 PM, Alex Crichton <acrichton at mozilla.com>
wrote:

> > Sorry for the brevity, I'm writing this from a phone and I haven't
> thought of this issue very thoroughly.
>
> You appear to dislike one of the most fundamental features of Rust, so
> I would encourage you to think through ideas such as this before
> hastily posting to the mailing list.
>
> The current iteration of Rust has had a great deal of thought and
> design poured into it, as well as having at least thousands of man
> hours of effort being put behind it. Casually stating, with little
> prior thought, that large chunks of this effort are flatly wrong is
> disrespectful to those who have put so much time and effort into the
> project.
>
> We always welcome and encourage thoughtful reconsiderations of the
> design decisions of Rust, but these must be performed in a
> constructive and well-thought-out manner. There have been many times
> in the past where the design decisions of Rust have been reversed or
> redone, but these were always accompanied with a large amount of
> research to fuel the changes.
>
> If you have concrete suggestions, we have an RFC process in place for
> proposing new changes to the language while gathering feedback at the
> same time.
> _______________________________________________
> Rust-dev mailing list
> Rust-dev at mozilla.org
> https://mail.mozilla.org/listinfo/rust-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.mozilla.org/pipermail/rust-dev/attachments/20140531/3da6387c/attachment.html>

Reply | Threaded
Open this post in threaded view
|

A better type system

Tommi Tissari
On 2014-05-31, at 22:13, Matthieu Monrocq <matthieu.monrocq at gmail.com> wrote:

> Another example of memory issue:
>
>     foo(left: &Option<Box<str>>, right: &mut Option<Box<str>>) {
>         let ptr: &str = *left.unwrap();
>
>         right = None;
>
>         match ptr.len() { // Watch out! if left and right alias, then ptr is no a dangling reference!
>         // ...
>         }
>     }

But the reason why there could be a dangling reference there is the (assumed) deallocation of Box<str> caused by the assignment to `right`. The type system should prevent assignment to a variable of type Option<Box<str>> if multiple mutable references could point to that variable.


> The issue can actually occur in other ways: replace Box<str> by enum Point { Integral(int, int), Floating(f64, f64) } and you could manage to write integral into floats or vice-versa, which is memory-corruption, not segmentation fault.

I don't think that counts as memory-corruption (according to http://en.wikipedia.org/wiki/Memory_corruption). That may be a bug in program logic, but then again, there might be a valid use for having two different pointers interpret the same of partly overlapping memory region as different types and mutating and using their memory according to their interpretation of it.

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.mozilla.org/pipermail/rust-dev/attachments/20140601/be0f2c88/attachment.html>

Reply | Threaded
Open this post in threaded view
|

A better type system

Tommi Tissari
In reply to this post by Patrick Walton-2
On 2014-05-31, at 20:44, Patrick Walton <pcwalton at mozilla.com> wrote:

> On 5/31/14 10:36 AM, Tommi wrote:
>> Iterator invalidation (as it's known in C++) is a risk to memory
>> safety only when some of the memory that is accessible through an
>> iterator (or a reference) is deallocated. A better type system would
>> make a distinction between those expressions that may deallocate and
>> those that cannot. Then, when multiple mutating references pointed to
>> the same variable, the compiler would disallow only the use of the
>> potentially deallocating expressions through those references.
>
> Again, this is wrong. Iterator invalidation is the way I like to explain the rule, but it is by no means the only thing that can go wrong if you have two &mut references to the same location. If you have two &mut pointers to the same memory address, it is quite easy to write cast::transmute in safe code without any iterators or memory being deallocated at all.

I don't understand that last sentence. How could you use `transmute` in safe code given that it's an `unsafe` function?

By the way, I said previously that:
>> Then, when multiple mutating references pointed to
>> the same variable, the compiler would disallow only the use of the
>> potentially deallocating expressions through those references.

...but I'd like to rephrase that:

The compiler should make sure that you can't deallocate memory that could potentially be accessible through multiple different variables (be they references or owning variables). But all other kind of mutation through different variables in a single-threaded code should be memory-safe at least in some definition of that word.

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.mozilla.org/pipermail/rust-dev/attachments/20140601/aaafc510/attachment.html>

Reply | Threaded
Open this post in threaded view
|

A better type system

Cameron Zwarich
In reply to this post by Tommi Tissari
When writing an email stating ?your programming language isn?t expressive enough?, it?s a good idea to include an example program that you would like to write that is rejected by the current type system. Then people replying to your email can give you some suggestions on how to best achieve your goals in Rust. The usual solution to the problem of safely mutating data is to use Cell, but we can?t be sure unless you give an example.

You are correct that mutation is only a risk to memory safety after deallocation occurs, but in a language with actual sum types this can occur when mutating a variable of a sum type to hold a different variant, since the storage is reused for a new variant after mutation, invalidating any references into the previous data. However, this doesn?t require preventing the mutation of things like integer fields of a struct.

The current guarantee (or the projected guarantee, since this isn?t actually implemented in all cases) for &mut references is that all accesses (both reads and writes) to &mut data occur through access paths derived from the &mut reference. This is helpful because the same guarantee holds regardless of type, and the guarantee is strong enough to provide race-free accesses to shared data.

Rust used to have an &const pointer type, which was similar to C++?s const in that it guaranteed that modifications didn?t occur through access paths derived from the &const pointer, but still allowed them to occur through other access paths. From what I understand, it was removed to simplify the type system, since most of its uses could be replaced with Cell.

In full generality, you could imagine Rust pointers allowing the specification of the following information:

1) Specific derived access paths that are unique, similar to the guarantee provided by &mut or the internal &uniq today.

2) Specific derived access paths that may be read through this pointer.

3) Specific derived access paths that may be mutated through this pointer.

4) Specific derived access paths that may observe mutations through access paths that do not involve this pointer.

Obviously, not all combinations would be sound or even coherent. This system would still permit reborrowing and would allow some interesting situations that are forbidden today. For example, you could have a vector v of

struct A { a: int, b: Box<int> }

and have an unrestricted number of mutable/const borrows of the path v[].a but a unique mutable borrow of v[].b and all derived paths. You could also pass partially initialized structs to other functions, knowing that they don?t read any of the uninitialized fields.

Would this be a better type system? Well, it would definitely be more expressive than the current system, and it wouldn?t even be extremely difficult to modify the borrow checker to implement it. However, it would be a dramatic increase in user-facing complexity, since shorthand would only take you so far. These complex pointer types would have to appear in every function signature. They would also leak implementation details of functions and types even moreso than Rust already does.

Cameron

On May 31, 2014, at 10:36 AM, Tommi <rusty.gates at icloud.com> wrote:

> It certainly feels like a failure of the Rust type system that you cannot have multiple mutating references to the same variable when the variable is accessed only from a single thread. I know the reason for this is to prevent iterator invalidation, but this is too blunt of an instrument.
>
> Iterator invalidation (as it's known in C++) is a risk to memory safety only when some of the memory that is accessible through an iterator (or a reference) is deallocated. A better type system would make a distinction between those expressions that may deallocate and those that cannot. Then, when multiple mutating references pointed to the same variable, the compiler would disallow only the use of the potentially deallocating expressions through those references.
>
> If a variable may be accessed concurrently from multiple threads, only then would the current "no mutating references allowed to that variable" -rule be enforced.
>
> Sorry for the brevity, I'm writing this from a phone and I haven't thought of this issue very thoroughly.
>
> _______________________________________________
> Rust-dev mailing list
> Rust-dev at mozilla.org
> https://mail.mozilla.org/listinfo/rust-dev


Reply | Threaded
Open this post in threaded view
|

A better type system

Patrick Walton-2
In reply to this post by Tommi Tissari
On 5/31/14 2:44 PM, Tommi wrote:
> I don't understand that last sentence. How could you use `transmute` in
> safe code given that it's an `unsafe` function?

I mean you could *write* transmute in safe code. Look:

     fn my_transmute<T:Clone,U>(value: T, other: U) -> U {
         let mut x = Left(other);
         let y = match x {
             Left(ref mut y) => y,
             Right(_) => fail!()
         };
         *x = Right(value);
         (*y).clone()
     }

Just by using two mutable references to the same location, I have
created a function that can cast any clonable type to any other type,
given at least one instance of the two. I didn't use any memory
allocation at all.

This was discussed quite a bit on the mailing list years ago.

> The compiler should make sure that you can't deallocate memory that
> could potentially be accessible through multiple different variables (be
> they references or owning variables). But all other kind of mutation
> through different variables in a single-threaded code should be
> memory-safe at least in some definition of that word.

No, it is not memory safe. See above.

Patrick


Reply | Threaded
Open this post in threaded view
|

A better type system

Tommi Tissari
On 2014-06-01, at 1:02, Patrick Walton <pcwalton at mozilla.com> wrote:

>    fn my_transmute<T:Clone,U>(value: T, other: U) -> U {
>        let mut x = Left(other);
>        let y = match x {
>            Left(ref mut y) => y,
>            Right(_) => fail!()
>        };
>        *x = Right(value);
>        (*y).clone()
>    }

If `U` implements `Copy`, then I don't see a (memory-safety) issue here. And if `U` doesn't implement `Copy`, then it's same situation as it was in the earlier example given by Matthieu, where there was an assignment to an `Option<Box<str>>` variable while a different reference pointing to that variable existed. The compiler shouldn't allow that assignment just as in your example the compiler shouldn't allow the assignment `x = Right(value);` (after a separate reference pointing to the contents of `x` has been created) if `U` is not a `Copy` type.

But, like I said in an earlier post, even though I don't see this (transmuting a `Copy` type in safe code) as a memory-safety issue, it is a code correctness issue. So it's a compromise between preventing logic bugs (in safe code) and the convenience of more liberal mutation.

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.mozilla.org/pipermail/rust-dev/attachments/20140601/f452022c/attachment.html>

Reply | Threaded
Open this post in threaded view
|

A better type system

Huon Wilson
References (&T) are Copy.


Huon

On 01/06/14 09:42, Tommi wrote:

> On 2014-06-01, at 1:02, Patrick Walton <pcwalton at mozilla.com
> <mailto:pcwalton at mozilla.com>> wrote:
>
>>    fn my_transmute<T:Clone,U>(value: T, other: U) -> U {
>>        let mut x = Left(other);
>>        let y = match x {
>>            Left(ref mut y) => y,
>>            Right(_) => fail!()
>>        };
>>        *x = Right(value);
>>        (*y).clone()
>>    }
>
> If `U` implements `Copy`, then I don't see a (memory-safety) issue
> here. And if `U` doesn't implement `Copy`, then it's same situation as
> it was in the earlier example given by Matthieu, where there was an
> assignment to an `Option<Box<str>>` variable while a different
> reference pointing to that variable existed. The compiler shouldn't
> allow that assignment just as in your example the compiler shouldn't
> allow the assignment `x = Right(value);` (after a separate reference
> pointing to the contents of `x` has been created) if `U` is not a
> `Copy` type.
>
> But, like I said in an earlier post, even though I don't see this
> (transmuting a `Copy` type in safe code) as a memory-safety issue, it
> is a code correctness issue. So it's a compromise between preventing
> logic bugs (in safe code) and the convenience of more liberal mutation.
>
>
>
> _______________________________________________
> Rust-dev mailing list
> Rust-dev at mozilla.org
> https://mail.mozilla.org/listinfo/rust-dev



-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.mozilla.org/pipermail/rust-dev/attachments/20140601/e3d16344/attachment.html>

Reply | Threaded
Open this post in threaded view
|

A better type system

Tommi Tissari
On 2014-06-01, at 2:45, Huon Wilson <dbau.pp at gmail.com> wrote:

> References (&T) are Copy.

That didn't occur to me. Okay, I can see how that would be a problem.


Reply | Threaded
Open this post in threaded view
|

A better type system

Patrick Walton
In reply to this post by Tommi Tissari
I assume what you're trying to say is that we should allow multiple mutable references to pointer-free data. (Note that, as Huon pointed out, this is not the same thing as the Copy bound.)

That is potentially plausible, but (a) it adds more complexity to the borrow checker; (b) it's a fairly narrow use case, since it'd only be safe for pointer-free data; (c) it admits casts like 3u8 -> bool, casts to out-of-range enum values, denormal floats, and the like, all of which would have various annoying consequences; (d) it complicates or defeats optimizations based on pointer aliasing of &mut; (e) it allows uninitialized data to be read, introducing undefined behavior into the language. I don't think it's worth it.

Patrick

On May 31, 2014 4:42:10 PM PDT, Tommi <rusty.gates at icloud.com> wrote:

>On 2014-06-01, at 1:02, Patrick Walton <pcwalton at mozilla.com> wrote:
>
>>    fn my_transmute<T:Clone,U>(value: T, other: U) -> U {
>>        let mut x = Left(other);
>>        let y = match x {
>>            Left(ref mut y) => y,
>>            Right(_) => fail!()
>>        };
>>        *x = Right(value);
>>        (*y).clone()
>>    }
>
>If `U` implements `Copy`, then I don't see a (memory-safety) issue
>here. And if `U` doesn't implement `Copy`, then it's same situation as
>it was in the earlier example given by Matthieu, where there was an
>assignment to an `Option<Box<str>>` variable while a different
>reference pointing to that variable existed. The compiler shouldn't
>allow that assignment just as in your example the compiler shouldn't
>allow the assignment `x = Right(value);` (after a separate reference
>pointing to the contents of `x` has been created) if `U` is not a
>`Copy` type.
>
>But, like I said in an earlier post, even though I don't see this
>(transmuting a `Copy` type in safe code) as a memory-safety issue, it
>is a code correctness issue. So it's a compromise between preventing
>logic bugs (in safe code) and the convenience of more liberal mutation.

--
Sent from my Android phone with K-9 Mail. Please excuse my brevity.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.mozilla.org/pipermail/rust-dev/attachments/20140531/ddd0fcdc/attachment.html>

Reply | Threaded
Open this post in threaded view
|

A better type system

Cameron Zwarich
FWIW, I think you could eliminate (c) by prohibiting mutation of sum types. What case are you thinking of for (e)?

For (d), this would probably have to be distinguished from the current &mut somehow, to allow for truly unique access paths to sum types or shared data, so you could preserve any aliasing optimizations for the current &mut. Of course, more functions might take the less restrictive version, eliminating the optimization that way.

Not that I think that this is a great idea; I?m just wondering whether there are any caveats that have escaped my mental model of the borrow checker.

Cameron

On May 31, 2014, at 5:01 PM, Patrick Walton <pwalton at mozilla.com> wrote:

> I assume what you're trying to say is that we should allow multiple mutable references to pointer-free data. (Note that, as Huon pointed out, this is not the same thing as the Copy bound.)
>
> That is potentially plausible, but (a) it adds more complexity to the borrow checker; (b) it's a fairly narrow use case, since it'd only be safe for pointer-free data; (c) it admits casts like 3u8 -> bool, casts to out-of-range enum values, denormal floats, and the like, all of which would have various annoying consequences; (d) it complicates or defeats optimizations based on pointer aliasing of &mut; (e) it allows uninitialized data to be read, introducing undefined behavior into the language. I don't think it's worth it.
>
> Patrick
>
> On May 31, 2014 4:42:10 PM PDT, Tommi <rusty.gates at icloud.com> wrote:
> On 2014-06-01, at 1:02, Patrick Walton <pcwalton at mozilla.com> wrote:
>
>>    fn my_transmute<T:Clone,U>(value: T, other: U) -> U {
>>        let mut x = Left(other);
>>        let y = match x {
>>            Left(ref mut y) => y,
>>            Right(_) => fail!()
>>        };
>>        *x = Right(value);
>>        (*y).clone()
>>    }
>
> If `U` implements `Copy`, then I don't see a (memory-safety) issue here. And if `U` doesn't implement `Copy`, then it's same situation as it was in the earlier example given by Matthieu, where there was an assignment to an `Option<Box<str>>` variable while a different reference pointing to that variable existed. The compiler shouldn't allow that assignment just as in your example the compiler shouldn't allow the assignment `x = Right(value);` (after a separate reference pointing to the contents of `x` has been created) if `U` is not a `Copy` type.
>
> But, like I said in an earlier post, even though I don't see this (transmuting a `Copy` type in safe code) as a memory-safety issue, it is a code correctness issue. So it's a compromise between preventing logic bugs (in safe code) and the convenience of more liberal mutation.
>
>
> --
> Sent from my Android phone with K-9 Mail. Please excuse my brevity.
> _______________________________________________
> Rust-dev mailing list
> Rust-dev at mozilla.org
> https://mail.mozilla.org/listinfo/rust-dev

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.mozilla.org/pipermail/rust-dev/attachments/20140531/8e91446d/attachment.html>

Reply | Threaded
Open this post in threaded view
|

A better type system

Patrick Walton
Yes, you could eliminate (c) by prohibiting taking references to the inside of sum types (really, any existential type). This is what Cyclone did. For (e) I'm thinking of sum types in which the two variants have different sizes (although maybe that doesn't work).

We'd basically have to bring back the old &mut as a separate type of pointer to make it work. Note that Niko was considering a system like this in older blog posts pre-INHTWAMA. (Search for "restrict pointers" on his blog.)

Patrick

On May 31, 2014 5:26:39 PM PDT, Cameron Zwarich <zwarich at mozilla.com> wrote:

>FWIW, I think you could eliminate (c) by prohibiting mutation of sum
>types. What case are you thinking of for (e)?
>
>For (d), this would probably have to be distinguished from the current
>&mut somehow, to allow for truly unique access paths to sum types or
>shared data, so you could preserve any aliasing optimizations for the
>current &mut. Of course, more functions might take the less restrictive
>version, eliminating the optimization that way.
>
>Not that I think that this is a great idea; I?m just wondering whether
>there are any caveats that have escaped my mental model of the borrow
>checker.
>
>Cameron
>
>On May 31, 2014, at 5:01 PM, Patrick Walton <pwalton at mozilla.com>
>wrote:
>
>> I assume what you're trying to say is that we should allow multiple
>mutable references to pointer-free data. (Note that, as Huon pointed
>out, this is not the same thing as the Copy bound.)
>>
>> That is potentially plausible, but (a) it adds more complexity to the
>borrow checker; (b) it's a fairly narrow use case, since it'd only be
>safe for pointer-free data; (c) it admits casts like 3u8 -> bool, casts
>to out-of-range enum values, denormal floats, and the like, all of
>which would have various annoying consequences; (d) it complicates or
>defeats optimizations based on pointer aliasing of &mut; (e) it allows
>uninitialized data to be read, introducing undefined behavior into the
>language. I don't think it's worth it.
>>
>> Patrick
>>
>> On May 31, 2014 4:42:10 PM PDT, Tommi <rusty.gates at icloud.com> wrote:
>> On 2014-06-01, at 1:02, Patrick Walton <pcwalton at mozilla.com> wrote:
>>
>>>    fn my_transmute<T:Clone,U>(value: T, other: U) -> U {
>>>        let mut x = Left(other);
>>>        let y = match x {
>>>            Left(ref mut y) => y,
>>>            Right(_) => fail!()
>>>        };
>>>        *x = Right(value);
>>>        (*y).clone()
>>>    }
>>
>> If `U` implements `Copy`, then I don't see a (memory-safety) issue
>here. And if `U` doesn't implement `Copy`, then it's same situation as
>it was in the earlier example given by Matthieu, where there was an
>assignment to an `Option<Box<str>>` variable while a different
>reference pointing to that variable existed. The compiler shouldn't
>allow that assignment just as in your example the compiler shouldn't
>allow the assignment `x = Right(value);` (after a separate reference
>pointing to the contents of `x` has been created) if `U` is not a
>`Copy` type.
>>
>> But, like I said in an earlier post, even though I don't see this
>(transmuting a `Copy` type in safe code) as a memory-safety issue, it
>is a code correctness issue. So it's a compromise between preventing
>logic bugs (in safe code) and the convenience of more liberal mutation.
>>
>>
>> --
>> Sent from my Android phone with K-9 Mail. Please excuse my brevity.
>> _______________________________________________
>> Rust-dev mailing list
>> Rust-dev at mozilla.org
>> https://mail.mozilla.org/listinfo/rust-dev

--
Sent from my Android phone with K-9 Mail. Please excuse my brevity.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.mozilla.org/pipermail/rust-dev/attachments/20140531/61582b59/attachment.html>

Reply | Threaded
Open this post in threaded view
|

A better type system

Matthieu Monrocq
FYI: I did a RFC for separating mut and "only" some times ago:
https://github.com/rust-lang/rfcs/pull/78#

I invite the interested readers to check it out and read the comments
(notably those by thestinger, aka Daniel Micay on this list).

For now, my understanding was that proposals on the topic were suspended
until the dev team manages to clear its plate of several big projects (such
as DST), especially as thestinger had a proposal to change the way lambda
captures are modeled so it no longer requires a "&uniq" (only accessible to
the compiler).

-- Matthieu



On Sun, Jun 1, 2014 at 2:32 AM, Patrick Walton <pwalton at mozilla.com> wrote:

> Yes, you could eliminate (c) by prohibiting taking references to the
> inside of sum types (really, any existential type). This is what Cyclone
> did. For (e) I'm thinking of sum types in which the two variants have
> different sizes (although maybe that doesn't work).
>
> We'd basically have to bring back the old &mut as a separate type of
> pointer to make it work. Note that Niko was considering a system like this
> in older blog posts pre-INHTWAMA. (Search for "restrict pointers" on his
> blog.)
>
> Patrick
>
> On May 31, 2014 5:26:39 PM PDT, Cameron Zwarich <zwarich at mozilla.com>
> wrote:
>>
>> FWIW, I think you could eliminate (c) by prohibiting mutation of sum
>> types. What case are you thinking of for (e)?
>>
>> For (d), this would probably have to be distinguished from the current
>> &mut somehow, to allow for truly unique access paths to sum types or shared
>> data, so you could preserve any aliasing optimizations for the current
>> &mut. Of course, more functions might take the less restrictive version,
>> eliminating the optimization that way.
>>
>> Not that I think that this is a great idea; I?m just wondering whether
>> there are any caveats that have escaped my mental model of the borrow
>> checker.
>>
>> Cameron
>>
>> On May 31, 2014, at 5:01 PM, Patrick Walton <pwalton at mozilla.com> wrote:
>>
>> I assume what you're trying to say is that we should allow multiple
>> mutable references to pointer-free data. (Note that, as Huon pointed out,
>> this is not the same thing as the Copy bound.)
>>
>> That is potentially plausible, but (a) it adds more complexity to the
>> borrow checker; (b) it's a fairly narrow use case, since it'd only be safe
>> for pointer-free data; (c) it admits casts like 3u8 -> bool, casts to
>> out-of-range enum values, denormal floats, and the like, all of which would
>> have various annoying consequences; (d) it complicates or defeats
>> optimizations based on pointer aliasing of &mut; (e) it allows
>> uninitialized data to be read, introducing undefined behavior into the
>> language. I don't think it's worth it.
>>
>> Patrick
>>
>> On May 31, 2014 4:42:10 PM PDT, Tommi <rusty.gates at icloud.com> wrote:
>>>
>>> On 2014-06-01, at 1:02, Patrick Walton <pcwalton at mozilla.com> wrote:
>>>
>>>    fn my_transmute<T:Clone,U>(value: T, other: U) -> U {
>>>        let mut x = Left(other);
>>>        let y = match x {
>>>            Left(ref mut y) => y,
>>>            Right(_) => fail!()
>>>        };
>>>        *x = Right(value);
>>>        (*y).clone()
>>>    }
>>>
>>>
>>> If `U` implements `Copy`, then I don't see a (memory-safety) issue here.
>>> And if `U` doesn't implement `Copy`, then it's same situation as it was in
>>> the earlier example given by Matthieu, where there was an assignment to an
>>> `Option<Box<str>>` variable while a different reference pointing to that
>>> variable existed. The compiler shouldn't allow that assignment just as in
>>> your example the compiler shouldn't allow the assignment `x =
>>> Right(value);` (after a separate reference pointing to the contents of `x`
>>> has been created) if `U` is not a `Copy` type.
>>>
>>> But, like I said in an earlier post, even though I don't see this
>>> (transmuting a `Copy` type in safe code) as a memory-safety issue, it is a
>>> code correctness issue. So it's a compromise between preventing logic bugs
>>> (in safe code) and the convenience of more liberal mutation.
>>>
>>>
>> --
>> Sent from my Android phone with K-9 Mail. Please excuse my brevity.
>> _______________________________________________
>> Rust-dev mailing list
>> Rust-dev at mozilla.org
>> https://mail.mozilla.org/listinfo/rust-dev
>>
>>
>>
> --
> Sent from my Android phone with K-9 Mail. Please excuse my brevity.
>
> _______________________________________________
> Rust-dev mailing list
> Rust-dev at mozilla.org
> https://mail.mozilla.org/listinfo/rust-dev
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.mozilla.org/pipermail/rust-dev/attachments/20140601/b0a4f226/attachment.html>

Reply | Threaded
Open this post in threaded view
|

A better type system

Tommi Tissari
In reply to this post by Patrick Walton
In my original post I stated that it feels like there's something wrong with the language when it doesn't allow multiple mutable references to the same data, but I didn't really explain why it feels like that. So, I just want to add this simple example to help explain my position. It is just plain obvious to everybody that the following code snippet is memory-safe, but the compiler refuses to compile it due to "cannot borrow `stuff[..]` as mutable more than once at a time":

let mut stuff = [1, 2, 3];
let r1 = stuff.mut_slice_to(2);
let r2 = stuff.mut_slice_from(1);

for i in std::iter::range(0u, 2) {
    if i % 2 == 0{
        r1[i] += 1;
    }
    else {
        r2[i] += 2;
    }
}

It's not even possible to forcefully deallocate the memory that is being referenced by multiple reference variables here, and the memory being referenced is just plain old data. Nothing can go wrong here, and yet the compiler thinks something is potentially unsafe and refuses to compile.

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.mozilla.org/pipermail/rust-dev/attachments/20140602/cf8f8d9a/attachment.html>

Reply | Threaded
Open this post in threaded view
|

A better type system

Tommi Tissari
On 2014-06-02, at 10:44, Tommi <rusty.gates at icloud.com> wrote:

> Nothing can go wrong here [..]

I just watched this video https://www.youtube.com/watch?v=awviiko59p8 and now I get the impression is that perhaps preventing aliasing bugs is more important than the convenience of unrestricted, aliased mutation.

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.mozilla.org/pipermail/rust-dev/attachments/20140602/7edb9642/attachment.html>

Reply | Threaded
Open this post in threaded view
|

A better type system

Patrick Walton-2
In reply to this post by Tommi Tissari
On 6/2/14 12:44 AM, Tommi wrote:

> In my original post I stated that it feels like there's something wrong
> with the language when it doesn't allow multiple mutable references to
> the same data, but I didn't really explain why it feels like that. So, I
> just want to add this simple example to help explain my position. It is
> just plain obvious to everybody that the following code snippet is
> memory-safe, but the compiler refuses to compile it due to "cannot
> borrow `stuff[..]` as mutable more than once at a time":
>
> let mut stuff = [1, 2, 3];
> let r1 = stuff.mut_slice_to(2);
> let r2 = stuff.mut_slice_from(1);

I'd like to have a function that splits up a vector in that way. That
should be doable in the standard library using some unsafe code under
the hood.

Patrick


Reply | Threaded
Open this post in threaded view
|

A better type system

Matthew McPherrin
Isn't this MutableVector's mut_split_at
<http://doc.rust-lang.org/std/slice/trait.MutableVector.html#tymethod.mut_split_at>
that we already have?


On Mon, Jun 2, 2014 at 8:25 AM, Patrick Walton <pcwalton at mozilla.com> wrote:

> On 6/2/14 12:44 AM, Tommi wrote:
>
>> In my original post I stated that it feels like there's something wrong
>> with the language when it doesn't allow multiple mutable references to
>> the same data, but I didn't really explain why it feels like that. So, I
>> just want to add this simple example to help explain my position. It is
>> just plain obvious to everybody that the following code snippet is
>> memory-safe, but the compiler refuses to compile it due to "cannot
>> borrow `stuff[..]` as mutable more than once at a time":
>>
>> let mut stuff = [1, 2, 3];
>> let r1 = stuff.mut_slice_to(2);
>> let r2 = stuff.mut_slice_from(1);
>>
>
> I'd like to have a function that splits up a vector in that way. That
> should be doable in the standard library using some unsafe code under the
> hood.
>
> Patrick
>
>
> _______________________________________________
> Rust-dev mailing list
> Rust-dev at mozilla.org
> https://mail.mozilla.org/listinfo/rust-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.mozilla.org/pipermail/rust-dev/attachments/20140602/7cd4c49a/attachment.html>

Reply | Threaded
Open this post in threaded view
|

A better type system

Sebastian Gesemann
On Mon, Jun 2, 2014 at 10:09 PM, Matthew McPherrin wrote:

> On Mon, Jun 2, 2014 at 8:25 AM, Patrick Walton wrote:
>> On 6/2/14 12:44 AM, Tommi wrote:
>>>
>>> In my original post I stated that it feels like there's something wrong
>>> with the language when it doesn't allow multiple mutable references to
>>> the same data, but I didn't really explain why it feels like that. So, I
>>> just want to add this simple example to help explain my position. It is
>>> just plain obvious to everybody that the following code snippet is
>>> memory-safe, but the compiler refuses to compile it due to "cannot
>>> borrow `stuff[..]` as mutable more than once at a time":
>>>
>>> let mut stuff = [1, 2, 3];
>>> let r1 = stuff.mut_slice_to(2);
>>> let r2 = stuff.mut_slice_from(1);
>>
>> I'd like to have a function that splits up a vector in that way. That
>> should be doable in the standard library using some unsafe code under the
>> hood.
>
> Isn't this MutableVector's mut_split_at that we already have?

I thought about mentioning mut_split_at just to make people aware of
it. But the resulting slices are not overlapping which is apparently
what Tommi was interested. My understanding is that even if one uses
an unsafe block to get two overlapping mutable slices, the use of
those might invoke undefined behaviour because it violates some
aliasing assumptions the compiler tends to exploit during
optimizations. Correct me if I'm wrong.

Cheers!
sg

12