Avoiding borrow check assertions with @mut

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

Avoiding borrow check assertions with @mut

Jeaye Wilkerson
Howdy,

I've become a big fan of @mut throughout my codebase for its
compatibility with closures, but I think it's really biting me in the
ass right now. >.<

Assume there's a state stack (in a state Director) that I'm looping
through to let the states know about an event. In this particular
instance, the event is a key action of ENTER, since 'load_map q3ctf1'
was just typed into the in-game console and ENTER was pressed. The
console state is interested in this event, no doubt.

When the console state gets this load_map command, it'll spring off a
function that creates a game and game_renderer, which are both states
that need to be pushed onto the state stack. But wait! We're currently
looping through the state stack, so trying to add something to it is an
assertion failure on the borrow (BAM, hard failure).

In C++, this could would be perfectly valid, so long as I'm iterating
through the state stack with indices and I'm pushing to the end of it,
thus not affecting the current index. In Rust, this is a big no-no. My
question is: how can I avoid this? Is it just because I'm using @mut
that I'm having this problem? What are some potential solutions that
people can think of, and has anyone hit the same snag in their own code?

Something I have tried: Adding a queue to the state Director of callback
functions (deferred modifications to the states) that states will push
closures onto instead of modifying the Director while it's looping. With
this, the Director could loop through each state, updating it, and then
loop through the queue of deferred callbacks and run them, which would
update the states stack. This didn't work for me since the Director
itself has the borrow lock on it, not just the states stack -- I reckon
I could put the deferred queue into TLS so that I wouldn't need a
mutable reference to the Director to add to it... but there has to be a
better way.

Any tips would be appreciated.

Jeaye
_______________________________________________
Rust-dev mailing list
[hidden email]
https://mail.mozilla.org/listinfo/rust-dev
Reply | Threaded
Open this post in threaded view
|

Re: Avoiding borrow check assertions with @mut

Oren Ben-Kiki
I had a similar problem when writing an iterator for a tree-like data structure. The iterator held a stack (vector) of per-node iterators and needed to push into it while accessing the last node.

In my case the whole thing works with owned and burrowed pointers. I managed to implement the immutable iterator by providing the correct lifetime incantation and, like you said, only using indices (actually I implemented a `mut_last()` function for mutable vectors - somehow this isn't in the standard library - but this is just a shorthand for accessing by `[len() - 1]`).

I couldn't get any safe code to work for the mutable iterator though :-( I ended up using an unsafe code with a `*mut` pointer. It seems like you could do the same, if you are willing to give up the type-enforced safety...

I love the compiler-enforced safety wrt. pointer lifetime and ownership, but like all type systems it has its limitations. It seems that the current approach is to implement safe containers with very careful sprinkling of `unsafe` (hey, even std::vec does it!), and then to have the bulk of the code use these safe containers. Maybe you could do something similar.

It would be awesome if one could come up with a non-zero-cost extension to the type system where one could say "I know this seems unsafe but I assert it is just because the static type system is too weak; please insert minimal efficient dynamic assertions that things are OK". This would need to be explicit since it would incur some (hopefully low) run-time penalty.

Probably such a mechanism wouldn't be 100% generic, but if we had a list of cases where people were forced to resort to unsafe code, perhaps we could cover the interesting "80%" of the cases and somehow provide them as a library or macro or something. ARC and RW ARC are sort of like that (libraries compensating for too-weak builtin-types system), maybe we need more?


On Tue, Aug 20, 2013 at 7:54 AM, Jeaye <[hidden email]> wrote:
Howdy,

I've become a big fan of @mut throughout my codebase for its compatibility with closures, but I think it's really biting me in the ass right now. >.<

Assume there's a state stack (in a state Director) that I'm looping through to let the states know about an event. In this particular instance, the event is a key action of ENTER, since 'load_map q3ctf1' was just typed into the in-game console and ENTER was pressed. The console state is interested in this event, no doubt.

When the console state gets this load_map command, it'll spring off a function that creates a game and game_renderer, which are both states that need to be pushed onto the state stack. But wait! We're currently looping through the state stack, so trying to add something to it is an assertion failure on the borrow (BAM, hard failure).

In C++, this could would be perfectly valid, so long as I'm iterating through the state stack with indices and I'm pushing to the end of it, thus not affecting the current index. In Rust, this is a big no-no. My question is: how can I avoid this? Is it just because I'm using @mut that I'm having this problem? What are some potential solutions that people can think of, and has anyone hit the same snag in their own code?

Something I have tried: Adding a queue to the state Director of callback functions (deferred modifications to the states) that states will push closures onto instead of modifying the Director while it's looping. With this, the Director could loop through each state, updating it, and then loop through the queue of deferred callbacks and run them, which would update the states stack. This didn't work for me since the Director itself has the borrow lock on it, not just the states stack -- I reckon I could put the deferred queue into TLS so that I wouldn't need a mutable reference to the Director to add to it... but there has to be a better way.

Any tips would be appreciated.

Jeaye
_______________________________________________
Rust-dev mailing list
[hidden email]
https://mail.mozilla.org/listinfo/rust-dev


_______________________________________________
Rust-dev mailing list
[hidden email]
https://mail.mozilla.org/listinfo/rust-dev
Reply | Threaded
Open this post in threaded view
|

Re: Avoiding borrow check assertions with @mut

Huon Wilson
On 20/08/13 15:19, Oren Ben-Kiki wrote:
>
> I love the compiler-enforced safety wrt. pointer lifetime and
> ownership, but like all type systems it has its limitations. It seems
> that the current approach is to implement safe containers with very
> careful sprinkling of `unsafe` (hey, even std::vec does it!), and then
> to have the bulk of the code use these safe containers. Maybe you
> could do something similar.
>

Note that the iterator-related unsafe in vec is entirely for efficiency,
it can easily be implemented manipulating &[] slices directly.

(I'm fairly sure the &mut [] iterator is possible without unsafe, but my
experimentation revealed a (possible) bug:
https://github.com/mozilla/rust/issues/8636.)


Huon
_______________________________________________
Rust-dev mailing list
[hidden email]
https://mail.mozilla.org/listinfo/rust-dev
Reply | Threaded
Open this post in threaded view
|

Re: Avoiding borrow check assertions with @mut

Daniel Micay
In reply to this post by Oren Ben-Kiki
On Tue, Aug 20, 2013 at 1:19 AM, Oren Ben-Kiki <[hidden email]> wrote:

> I had a similar problem when writing an iterator for a tree-like data
> structure. The iterator held a stack (vector) of per-node iterators and
> needed to push into it while accessing the last node.
>
> In my case the whole thing works with owned and burrowed pointers. I managed
> to implement the immutable iterator by providing the correct lifetime
> incantation and, like you said, only using indices (actually I implemented a
> `mut_last()` function for mutable vectors - somehow this isn't in the
> standard library - but this is just a shorthand for accessing by `[len() -
> 1]`).
>
> I couldn't get any safe code to work for the mutable iterator though :-( I
> ended up using an unsafe code with a `*mut` pointer. It seems like you could
> do the same, if you are willing to give up the type-enforced safety...

It's possible to implement a mutable iterator through a tree-like
object without unsafe code. If you're using unsafe code to return a
reference overlapping with the children, it's not a memory safe
interface.

You can use pattern matching to split a mutable reference into
disjoint mutable references (one as the yielded value, the other
pointing to the children):

     // can be done with a struct too
     let mut t = (1, 2); let (ref mut x, ref mut y) = t;

> I love the compiler-enforced safety wrt. pointer lifetime and ownership, but
> like all type systems it has its limitations. It seems that the current
> approach is to implement safe containers with very careful sprinkling of
> `unsafe` (hey, even std::vec does it!), and then to have the bulk of the
> code use these safe containers. Maybe you could do something similar.

Vectors are the lowest-level dynamically sized memory allocation
primitive in Rust. There's no existing safe code for them to leverage,
so it either has to be implemented in the compiler or the library, and
library code is simpler.

There are many containers implemented entirely without unsafe code,
copies or managed pointers including `std::hashmap`, `std::trie`,
`extra::treemap` and `extra::ringbuf`. The `extra::priority_queue`
implementation was originally safe, but contains a simple
micro-optimization with a bit of unsafe code.

It's likely that the `ringbuf` implementation will be micro-optimized
with unsafe code in the future, but for the others it's a matter of
improving the compiler's codegen.

> It would be awesome if one could come up with a non-zero-cost extension to
> the type system where one could say "I know this seems unsafe but I assert
> it is just because the static type system is too weak; please insert minimal
> efficient dynamic assertions that things are OK". This would need to be
> explicit since it would incur some (hopefully low) run-time penalty.

The minimal dynamic assertions are the dynamic borrow checking errors
provided by mutable managed/reference-counted pointers. I don't think
there's going to be anything cheaper than reference counting +
freezing/unfreezing on borrow scopes.

> Probably such a mechanism wouldn't be 100% generic, but if we had a list of
> cases where people were forced to resort to unsafe code, perhaps we could
> cover the interesting "80%" of the cases and somehow provide them as a
> library or macro or something. ARC and RW ARC are sort of like that
> (libraries compensating for too-weak builtin-types system), maybe we need
> more?

I wouldn't really say `extra::arc` is working around the type system.
It exists only to provide atomic reference counting for references
from multiple tasks, and a mutex to guard mutability. Rust implements
concurrency in the standard library, so the building blocks in the
standard library have to use unsafe code. The type system allows them
to be *used* within entirely safe code.
_______________________________________________
Rust-dev mailing list
[hidden email]
https://mail.mozilla.org/listinfo/rust-dev
Reply | Threaded
Open this post in threaded view
|

Re: Avoiding borrow check assertions with @mut

Niko Matsakis
In reply to this post by Jeaye Wilkerson
One simple way to iterate over a vector and preserve the right to push
onto it is to use something like a while loop instead:

    let mut i = 0;
    while i < vec.len() {
        process(vec[i]); // may alter vec
    }


It would be trivial to package this pattern up into a special iterator
that only works on `@mut` vectors and which iterated by value (not by
reference). Rust won't let you push while iterating by reference,
because pushing onto the vector may resize it and hence free the
memory.

Would this solve your problem?



Niko



On Mon, Aug 19, 2013 at 09:54:17PM -0700, Jeaye wrote:

> Howdy,
>
> I've become a big fan of @mut throughout my codebase for its
> compatibility with closures, but I think it's really biting me in the
> ass right now. >.<
>
> Assume there's a state stack (in a state Director) that I'm looping
> through to let the states know about an event. In this particular
> instance, the event is a key action of ENTER, since 'load_map q3ctf1'
> was just typed into the in-game console and ENTER was pressed. The
> console state is interested in this event, no doubt.
>
> When the console state gets this load_map command, it'll spring off a
> function that creates a game and game_renderer, which are both states
> that need to be pushed onto the state stack. But wait! We're
> currently looping through the state stack, so trying to add something
> to it is an assertion failure on the borrow (BAM, hard failure).
>
> In C++, this could would be perfectly valid, so long as I'm iterating
> through the state stack with indices and I'm pushing to the end of
> it, thus not affecting the current index. In Rust, this is a big
> no-no. My question is: how can I avoid this? Is it just because I'm
> using @mut that I'm having this problem? What are some potential
> solutions that people can think of, and has anyone hit the same snag
> in their own code?
>
> Something I have tried: Adding a queue to the state Director of
> callback functions (deferred modifications to the states) that states
> will push closures onto instead of modifying the Director while it's
> looping. With this, the Director could loop through each state,
> updating it, and then loop through the queue of deferred callbacks
> and run them, which would update the states stack. This didn't work
> for me since the Director itself has the borrow lock on it, not just
> the states stack -- I reckon I could put the deferred queue into TLS
> so that I wouldn't need a mutable reference to the Director to add to
> it... but there has to be a better way.
>
> Any tips would be appreciated.
>
> Jeaye
> _______________________________________________
> Rust-dev mailing list
> [hidden email]
> https://mail.mozilla.org/listinfo/rust-dev
_______________________________________________
Rust-dev mailing list
[hidden email]
https://mail.mozilla.org/listinfo/rust-dev
Reply | Threaded
Open this post in threaded view
|

Re: Avoiding borrow check assertions with @mut

Oren Ben-Kiki
Here is the heart of the code, maybe it will be clearer why I had to use unsafe (or, maybe, how I could avoid it):

/// A path is just an array of atoms.
#[deriving(Eq, TotalEq, Ord, TotalOrd, Clone, IterBytes)]
pub struct Path {
    /// The array of atoms the path consists of.
    pub atoms: ~[Atom],
}

/// An entry contained in the tree map.
#[deriving(Eq, TotalEq, Ord, TotalOrd)]
pub struct TreeMapEntry<T> {
    /// The full path of the entry.
    path: Path,

    /// The value of the entry.
    value: T,
}

/// A tree map holds values of some arbitrary type, indexed by a path.
pub struct TreeMap<T> {
    /// The entry of this node, if any.
    priv entry: Option<TreeMapEntry<T>>,

    /// The sub-trees under this node, if any.
    priv sub_trees: HashMap<Atom, ~TreeMap<T>>
}

/// Iterate and mutate on a single level of the tree map.
struct LevelMutIterator<'self, T> {
    /// The root node to return the value of (as the 1st result).
    root: Option<&'self mut TreeMapEntry<T>>,

    /// The iterator at the current level of the tree.
    iterator: HashMapMutIterator<'self, Atom, ~TreeMap<T>>,
}

/// Iterate and mutate on a tree map in an arbitrary order.
pub struct TreeMapMutIterator<'self, T> {
    /// The iterators of all levels we have reached so far.
    priv levels: ~[LevelMutIterator<'self, T>]
}

/// Iterate and mutate on a tree map in an arbitrary order.
impl<'self, T> Iterator<(&'self Path, &'self mut T)> for TreeMapMutIterator<'self, T> {
    /// Move to the next value contained in the tree map.
    fn next(&mut self) -> Option<(&'self Path, &'self mut T)> {
        if self.levels.len() == 0 {
            None
        } else {
            unsafe {
                let last: *mut LevelMutIterator<'self, T> = &mut self.levels[self.levels.len() - 1];
                match (*last).root {
                    Some(ref mut entry) => {
                        let path = &entry.path;
                        let value = &mut entry.value;
                        // TRICKY: This makes the entry inaccessible, which is
                        // why we took the returned path and value above.
                        (*last).root = None;
                        Some((path, value))
                    }
                    None => {
                        match self.levels[self.levels.len() - 1].iterator.next() {
                            Some((_atom, treemap)) => {
                                self.levels.push(treemap.level_mut_iter());
                            }
                            None => {
                                self.levels.pop();
                            }
                        }
                        self.next()
                    }
                }
            }
        }
    }
}

I tried for around a day to make this work without the unsafe, to no avail. The trick is I want to take the value out of the option (leaving None behind), and return the value. I'm probably missing some solution which may be obvious to a non-newbie to Rust...?

_______________________________________________
Rust-dev mailing list
[hidden email]
https://mail.mozilla.org/listinfo/rust-dev
Reply | Threaded
Open this post in threaded view
|

Re: Avoiding borrow check assertions with @mut

Sebastian Sylvan
In reply to this post by Jeaye Wilkerson


On Mon, Aug 19, 2013 at 9:54 PM, Jeaye <[hidden email]> wrote:
Howdy,

I've become a big fan of @mut throughout my codebase for its compatibility with closures, but I think it's really biting me in the ass right now. >.<

Assume there's a state stack (in a state Director) that I'm looping through to let the states know about an event. In this particular instance, the event is a key action of ENTER, since 'load_map q3ctf1' was just typed into the in-game console and ENTER was pressed. The console state is interested in this event, no doubt.

When the console state gets this load_map command, it'll spring off a function that creates a game and game_renderer, which are both states that need to be pushed onto the state stack. But wait! We're currently looping through the state stack, so trying to add something to it is an assertion failure on the borrow (BAM, hard failure).

In C++, this could would be perfectly valid, so long as I'm iterating through the state stack with indices and I'm pushing to the end of it, thus not affecting the current index. In Rust, this is a big no-no. My question is: how can I avoid this? Is it just because I'm using @mut that I'm having this problem? What are some potential solutions that people can think of, and has anyone hit the same snag in their own code?

Something I have tried: Adding a queue to the state Director of callback functions (deferred modifications to the states) that states will push closures onto instead of modifying the Director while it's looping. With this, the Director could loop through each state, updating it, and then loop through the queue of deferred callbacks and run them, which would update the states stack. This didn't work for me since the Director itself has the borrow lock on it, not just the states stack -- I reckon I could put the deferred queue into TLS so that I wouldn't need a mutable reference to the Director to add to it... but there has to be a better way.

Any tips would be appreciated.
 
I'm not entirely sure I understand why that last thing you mentioned wouldn't work. Maybe you could refactor your event handlers to return changes to the state stack instead of mutating? Or perhaps just make changes to the stack itself work differently - while you're looping through them any calls to modify the stack gets put on a side-queue, and then after you've finished looping you apply them all. You're not running arbitrary code at this point, just adding stuff to the stack.



--
Sebastian Sylvan

_______________________________________________
Rust-dev mailing list
[hidden email]
https://mail.mozilla.org/listinfo/rust-dev
Reply | Threaded
Open this post in threaded view
|

Re: Avoiding borrow check assertions with @mut

Niko Matsakis
In reply to this post by Oren Ben-Kiki
There may be another way, but one safe option is to use util::replace
to always set the `root` field to None but preserve the old value, as
shown below (this code compiles).

In general, the rule you are running into (which prevents mutation to
the path that contains a borrowed &mut) is one that I have gone back
and forth on. I have to go consult my notes as to the reason it is
setup the way it is; it may be that we could potentially loosen the
rule in this case, but I seem to recall that doing so had dangerous
consequences that I cannot remember at the moment.

> /// Iterate and mutate on a tree map in an arbitrary order.
> impl<'self, T> Iterator<(&'self Path, &'self mut T)> for
> TreeMapMutIterator<'self, T> {
>     /// Move to the next value contained in the tree map.
>     fn next(&mut self) -> Option<(&'self Path, &'self mut T)> {
>         if self.levels.len() == 0 {
>             None
>         } else {
>             let last = self.levels.len() - 1;
>             let root = util::replace(&mut self.levels[last].root, None);
>             match root {
>                 Some(&ref mut entry) => {
>                     let path = &entry.path;
>                     let value = &mut entry.value;
>                     Some((path, value))
>                 }
>                 None => {
>                     match self.levels[last].iterator.next() {
>                         Some((_atom, treemap)) => {
>                             self.levels.push(fail!());
>                         }
>                         None => {
>                             self.levels.pop();
>                         }
>                     }
>                     self.next()
>                 }
>             }
>         }
>     }
> }


Niko


On Tue, Aug 20, 2013 at 05:50:31PM +0300, Oren Ben-Kiki wrote:

> Here is the heart of the code, maybe it will be clearer why I had to use
> unsafe (or, maybe, how I could avoid it):
>
> /// A path is just an array of atoms.
> #[deriving(Eq, TotalEq, Ord, TotalOrd, Clone, IterBytes)]
> pub struct Path {
>     /// The array of atoms the path consists of.
>     pub atoms: ~[Atom],
> }
>
> /// An entry contained in the tree map.
> #[deriving(Eq, TotalEq, Ord, TotalOrd)]
> pub struct TreeMapEntry<T> {
>     /// The full path of the entry.
>     path: Path,
>
>     /// The value of the entry.
>     value: T,
> }
>
> /// A tree map holds values of some arbitrary type, indexed by a path.
> pub struct TreeMap<T> {
>     /// The entry of this node, if any.
>     priv entry: Option<TreeMapEntry<T>>,
>
>     /// The sub-trees under this node, if any.
>     priv sub_trees: HashMap<Atom, ~TreeMap<T>>
> }
>
> /// Iterate and mutate on a single level of the tree map.
> struct LevelMutIterator<'self, T> {
>     /// The root node to return the value of (as the 1st result).
>     root: Option<&'self mut TreeMapEntry<T>>,
>
>     /// The iterator at the current level of the tree.
>     iterator: HashMapMutIterator<'self, Atom, ~TreeMap<T>>,
> }
>
> /// Iterate and mutate on a tree map in an arbitrary order.
> pub struct TreeMapMutIterator<'self, T> {
>     /// The iterators of all levels we have reached so far.
>     priv levels: ~[LevelMutIterator<'self, T>]
> }
>
> /// Iterate and mutate on a tree map in an arbitrary order.
> impl<'self, T> Iterator<(&'self Path, &'self mut T)> for
> TreeMapMutIterator<'self, T> {
>     /// Move to the next value contained in the tree map.
>     fn next(&mut self) -> Option<(&'self Path, &'self mut T)> {
>         if self.levels.len() == 0 {
>             None
>         } else {
>             unsafe {
>                 let last: *mut LevelMutIterator<'self, T> = &mut
> self.levels[self.levels.len() - 1];
>                 match (*last).root {
>                     Some(ref mut entry) => {
>                         let path = &entry.path;
>                         let value = &mut entry.value;
>                         // TRICKY: This makes the entry inaccessible, which
> is
>                         // why we took the returned path and value above.
>                         (*last).root = None;
>                         Some((path, value))
>                     }
>                     None => {
>                         match self.levels[self.levels.len() -
> 1].iterator.next() {
>                             Some((_atom, treemap)) => {
>                                 self.levels.push(treemap.level_mut_iter());
>                             }
>                             None => {
>                                 self.levels.pop();
>                             }
>                         }
>                         self.next()
>                     }
>                 }
>             }
>         }
>     }
> }
>
> I tried for around a day to make this work without the unsafe, to no avail.
> The trick is I want to take the value out of the option (leaving None
> behind), and return the value. I'm probably missing some solution which may
> be obvious to a non-newbie to Rust...?

> _______________________________________________
> Rust-dev mailing list
> [hidden email]
> https://mail.mozilla.org/listinfo/rust-dev

_______________________________________________
Rust-dev mailing list
[hidden email]
https://mail.mozilla.org/listinfo/rust-dev
Reply | Threaded
Open this post in threaded view
|

Re: Avoiding borrow check assertions with @mut

Kevin Ballard-2
You should be able to just use .take() instead of invoking util::replace(), although the end-result should be the same.

    let root = self.levels[last].root.take();

-Kevin

On Aug 20, 2013, at 7:35 PM, Niko Matsakis <[hidden email]> wrote:

> There may be another way, but one safe option is to use util::replace
> to always set the `root` field to None but preserve the old value, as
> shown below (this code compiles).
>
> In general, the rule you are running into (which prevents mutation to
> the path that contains a borrowed &mut) is one that I have gone back
> and forth on. I have to go consult my notes as to the reason it is
> setup the way it is; it may be that we could potentially loosen the
> rule in this case, but I seem to recall that doing so had dangerous
> consequences that I cannot remember at the moment.
>
>> /// Iterate and mutate on a tree map in an arbitrary order.
>> impl<'self, T> Iterator<(&'self Path, &'self mut T)> for
>> TreeMapMutIterator<'self, T> {
>>    /// Move to the next value contained in the tree map.
>>    fn next(&mut self) -> Option<(&'self Path, &'self mut T)> {
>>        if self.levels.len() == 0 {
>>            None
>>        } else {
>>            let last = self.levels.len() - 1;
>>            let root = util::replace(&mut self.levels[last].root, None);
>>            match root {
>>                Some(&ref mut entry) => {
>>                    let path = &entry.path;
>>                    let value = &mut entry.value;
>>                    Some((path, value))
>>                }
>>                None => {
>>                    match self.levels[last].iterator.next() {
>>                        Some((_atom, treemap)) => {
>>                            self.levels.push(fail!());
>>                        }
>>                        None => {
>>                            self.levels.pop();
>>                        }
>>                    }
>>                    self.next()
>>                }
>>            }
>>        }
>>    }
>> }
>
>
> Niko
>
>
> On Tue, Aug 20, 2013 at 05:50:31PM +0300, Oren Ben-Kiki wrote:
>> Here is the heart of the code, maybe it will be clearer why I had to use
>> unsafe (or, maybe, how I could avoid it):
>>
>> /// A path is just an array of atoms.
>> #[deriving(Eq, TotalEq, Ord, TotalOrd, Clone, IterBytes)]
>> pub struct Path {
>>    /// The array of atoms the path consists of.
>>    pub atoms: ~[Atom],
>> }
>>
>> /// An entry contained in the tree map.
>> #[deriving(Eq, TotalEq, Ord, TotalOrd)]
>> pub struct TreeMapEntry<T> {
>>    /// The full path of the entry.
>>    path: Path,
>>
>>    /// The value of the entry.
>>    value: T,
>> }
>>
>> /// A tree map holds values of some arbitrary type, indexed by a path.
>> pub struct TreeMap<T> {
>>    /// The entry of this node, if any.
>>    priv entry: Option<TreeMapEntry<T>>,
>>
>>    /// The sub-trees under this node, if any.
>>    priv sub_trees: HashMap<Atom, ~TreeMap<T>>
>> }
>>
>> /// Iterate and mutate on a single level of the tree map.
>> struct LevelMutIterator<'self, T> {
>>    /// The root node to return the value of (as the 1st result).
>>    root: Option<&'self mut TreeMapEntry<T>>,
>>
>>    /// The iterator at the current level of the tree.
>>    iterator: HashMapMutIterator<'self, Atom, ~TreeMap<T>>,
>> }
>>
>> /// Iterate and mutate on a tree map in an arbitrary order.
>> pub struct TreeMapMutIterator<'self, T> {
>>    /// The iterators of all levels we have reached so far.
>>    priv levels: ~[LevelMutIterator<'self, T>]
>> }
>>
>> /// Iterate and mutate on a tree map in an arbitrary order.
>> impl<'self, T> Iterator<(&'self Path, &'self mut T)> for
>> TreeMapMutIterator<'self, T> {
>>    /// Move to the next value contained in the tree map.
>>    fn next(&mut self) -> Option<(&'self Path, &'self mut T)> {
>>        if self.levels.len() == 0 {
>>            None
>>        } else {
>>            unsafe {
>>                let last: *mut LevelMutIterator<'self, T> = &mut
>> self.levels[self.levels.len() - 1];
>>                match (*last).root {
>>                    Some(ref mut entry) => {
>>                        let path = &entry.path;
>>                        let value = &mut entry.value;
>>                        // TRICKY: This makes the entry inaccessible, which
>> is
>>                        // why we took the returned path and value above.
>>                        (*last).root = None;
>>                        Some((path, value))
>>                    }
>>                    None => {
>>                        match self.levels[self.levels.len() -
>> 1].iterator.next() {
>>                            Some((_atom, treemap)) => {
>>                                self.levels.push(treemap.level_mut_iter());
>>                            }
>>                            None => {
>>                                self.levels.pop();
>>                            }
>>                        }
>>                        self.next()
>>                    }
>>                }
>>            }
>>        }
>>    }
>> }
>>
>> I tried for around a day to make this work without the unsafe, to no avail.
>> The trick is I want to take the value out of the option (leaving None
>> behind), and return the value. I'm probably missing some solution which may
>> be obvious to a non-newbie to Rust...?
>
>> _______________________________________________
>> Rust-dev mailing list
>> [hidden email]
>> https://mail.mozilla.org/listinfo/rust-dev
>
> _______________________________________________
> Rust-dev mailing list
> [hidden email]
> https://mail.mozilla.org/listinfo/rust-dev

_______________________________________________
Rust-dev mailing list
[hidden email]
https://mail.mozilla.org/listinfo/rust-dev
Reply | Threaded
Open this post in threaded view
|

Re: Avoiding borrow check assertions with @mut

Oren Ben-Kiki
Thanks for all the responses!

I knew there was something simple I could do in my specific case - in this case, `.take()` or more generically `utils::replace`. Thanks for the pointers.

That said, the general problem remains. I think it goes as follows:

- There is a container accessible from some root pointer.
- One burrows a mutable pointer to some entry nested in the container.
- At this point, we can split all the memory reachable from the root pointer into three kinds:
  A. The mutable entry data we burrowed a pointer to.
  B. The data along the path leading from (including) the root pointer to the mutable entry.
  C. Other data reachable by the container.

For example, if I have a `&mut T` to the `i`th entry of a `~[T]` array, then:
  A. Is the `&mut T` and anything reached from it.
  B. Is the pointer to the base of the array (the `&mut T` is that base plus `i` * the size of `T`).
  C. Is all the data contained in all the entries other than the `i`th, and anything reached from them.

Now, there are three kinds of mutations one can do to the container - these that mutate A, B or C data.

Burrowing a 2nd mutable pointer to A data is forbidden, to avoid two mutable pointers to the same data. So far, so good.

Burrowing a mutable pointer to B data is forbidden, because if it mutates than the entry we have a pointer to might be disconnected from the container or compromised in another way.

Burrowing a mutable pointer to C data should be allowed, as it doesn't overlap with our mutable pointer in any way.

For example, one could reasonably expect to be able to burrow a mutable pointer to both `vec[0]` and `vec[1]` at the same time.

However, the type system can't tell (in general) whether a specific mutable operation on the container touches only B date or also C data.  It doesn't know that `vec.push()` might change the base pointer (B data) but `vec[1]` doesn't. All it can see is that there is mutable access in both case, so it plays it safe.

It is hard to do better. Even in the simple vector case. Suppose I get two parameters, `i` and `j`, and I tryu to get `&mut T` for both `vec[i]` and `vec[j]`. This is OK as long as i is different from j. If they are equal, this is forbidden. But there's no way to make these kinds of decisions in the type system - this requires a run-time check.

It might be able to do somewhat better by using nested lifetimes. I'm not certain this can be done in a general way using the current type system, though. But even with nested lifetimes, this wouldn't solve the general problem.

When the static type system fails, one must rely on either unsafe code ("trust me") or a dynamic type system ("verify me"). The latter may be expensive - in fact, supporting "verify me" might require extra cost for code that has no need for this feature (to make relevant meta-data available and up-to-date).

Right now, Rust goes along the way of "trust me". That said, there are idioms (like `take`) which can hide the nastiness in their inside. Perhaps we need a cheat cheat of common use cases and the patterns for achieving them using the current mechanisms (that is, libraries that provide support for the common use cases). ARC for example, but also `take` and `replace` and I guess a few more besides. Then we could say "if you feel none of them is enough, define a new useful generic safe mechanism (with unsafe internals) to cover the case"; but in general all containers code should not include any `unsafe` blocks, it should just use one of the debugger/approved standard library "trust me" functions (which would presumably be well-debugged).

This would be quite a project, though... even when based on existing code.

_______________________________________________
Rust-dev mailing list
[hidden email]
https://mail.mozilla.org/listinfo/rust-dev