3 ms·

Rust takes the approach of flat-out not letting you mutate any collection while you have any references to its contents. It eliminates all dangling pointer bugs

duped 5y ago
The underlying pointer to a unique_ptr won't be invalidated but the iterator might. Consider if you had a vector of unique_ptrs and inserted into it within a for loop. Depending on the implementation of the iterator this may not be sound (if it's an index, you're probably ok, if it's a pointer, you're screwed). If you wanted to do the same in Rust it would be Vec<Box<T>>. Mutating the collection won't invalidate the pointers.
- nyanpasu64 5y ago
  > Mutating the collection won't invalidate the pointers. Rust still won't let you mutate a Vec<Box<T>> while you hold a &T or &mut T borrowed from the Vec. Perhaps it would be sound to do so unsafely; Rust would let you mutate a Vec<Rc<T>> while you hold a Rc<T> cloned from the Vec. But I'm not clear on whether Stacked Borrows allows moving the Box while you have a &mut T pointing to the same memory as the Box points to. It definitely does not allow dereferencing the Box. (I heard Stacked Borrows will be updated to make self-referential types sound, and I don't know if it will affect this situation.)
  - Measter 5y ago
    In the case of a Vec<Box<T>> the Vec owns the box, so the only thing you could link the reference lifetime to is the Vec itself because if the lifetime isn't bound to the Vec, mutating the Vec might drop that item which in the case of Box<T> will also deallocate the memory. If any references point directly to that memory, then it would be dangling. In the case of Rc<T>, cloning the Rc creates a second owner of the heap allocation, so the Vec dropping its copy won't deallocate. Though I believe one complication to this would be that the lifetime any references created through the Vec's copy of the Rc will be linked specifically to that copy, so would result in a borrow check error when it's dropped. If the Vec is storing references, you can borrow the thing behind the reference and still mutate the Vec because that reference stays valid even if mutating the Vec drops its reference to the item. let (a, b, c, d) = (1, 2, 3, 4); let mut v = vec![&a, &b, &c, &d]; // If you change the type here to &&u32, or let the compiler infer the type // then you'll get a borrow check error because the outer reference // borrows the Vec. let borrowed_b: &u32 = &v[1]; v.remove(1); println!("{}", borrowed_b); println!("{:?}", v); https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=7762c73cf306917e28aaec2de8c4e131 https://play.rust-lang.org/?version=stable&mode=debug&editio... [1]
Animats 5y ago
Rust takes the approach of flat-out not letting you mutate any collection while you have any references to its contents. It eliminates all dangling pointer bugs... I don't know if it rules out any useful use cases of collections with iterator stability. It does. Some collections have a "collection.retain" method. collection.retain(|v| true_if_we_want_to_keep(v)) which goes through the collection in linear time and deletes any items for which the test is false. This is O(N). Some collections ("multi_map", which isn't used much, comes to mind) don't have that. You have to make a read pass over the collection, construct a list of things to delete, then go through the delete list and delete those items. Can't read and change with the same iterator. That's slower. But sound. I'm OK with that. It avoids subtle bugs.
ridiculous_fish 5y ago
An illustrative example is a string set which remembers its insertion order. In C++ you may write: struct OrderedSet { deque<string> storage; set<string_view> vals; } The deque holds the string contents, and the set holds views of those contents. This is safe because the deque has iterator stability, and it's pleasant because the `vals` set can just be a regular set. As you say Rust does not allow this; its answer is IndexSet, and it is implemented differently, like: struct OrderedSet { Vec<String> buckets; RawTable<usize> hashToBucketIndex; } RawTable is a hash table that doesn't know how to compute a hash or determine equality. Instead, you provide it with closures to do those tasks, but at the call site (not construction time). Basically Rust achieves the same thing through a layer of indirection involving indexes, which is a common pattern.

duped 5y ago

The underlying pointer to a unique_ptr won't be invalidated but the iterator might. Consider if you had a vector of unique_ptrs and inserted into it within a for loop. Depending on the implementation of the iterator this may not be sound (if it's an index, you're probably ok, if it's a pointer, you're screwed). If you wanted to do the same in Rust it would be Vec<Box<T>>. Mutating the collection won't invalidate the pointers.

nyanpasu64 5y ago
> Mutating the collection won't invalidate the pointers. Rust still won't let you mutate a Vec<Box<T>> while you hold a &T or &mut T borrowed from the Vec. Perhaps it would be sound to do so unsafely; Rust would let you mutate a Vec<Rc<T>> while you hold a Rc<T> cloned from the Vec. But I'm not clear on whether Stacked Borrows allows moving the Box while you have a &mut T pointing to the same memory as the Box points to. It definitely does not allow dereferencing the Box. (I heard Stacked Borrows will be updated to make self-referential types sound, and I don't know if it will affect this situation.)
- Measter 5y ago
  In the case of a Vec<Box<T>> the Vec owns the box, so the only thing you could link the reference lifetime to is the Vec itself because if the lifetime isn't bound to the Vec, mutating the Vec might drop that item which in the case of Box<T> will also deallocate the memory. If any references point directly to that memory, then it would be dangling. In the case of Rc<T>, cloning the Rc creates a second owner of the heap allocation, so the Vec dropping its copy won't deallocate. Though I believe one complication to this would be that the lifetime any references created through the Vec's copy of the Rc will be linked specifically to that copy, so would result in a borrow check error when it's dropped. If the Vec is storing references, you can borrow the thing behind the reference and still mutate the Vec because that reference stays valid even if mutating the Vec drops its reference to the item. let (a, b, c, d) = (1, 2, 3, 4); let mut v = vec![&a, &b, &c, &d]; // If you change the type here to &&u32, or let the compiler infer the type // then you'll get a borrow check error because the outer reference // borrows the Vec. let borrowed_b: &u32 = &v[1]; v.remove(1); println!("{}", borrowed_b); println!("{:?}", v); https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=7762c73cf306917e28aaec2de8c4e131 https://play.rust-lang.org/?version=stable&mode=debug&editio... [1]

Animats 5y ago

Rust takes the approach of flat-out not letting you mutate any collection while you have any references to its contents. It eliminates all dangling pointer bugs... I don't know if it rules out any useful use cases of collections with iterator stability. It does. Some collections have a "collection.retain" method. collection.retain(|v| true_if_we_want_to_keep(v)) which goes through the collection in linear time and deletes any items for which the test is false. This is O(N). Some collections ("multi_map", which isn't used much, comes to mind) don't have that. You have to make a read pass over the collection, construct a list of things to delete, then go through the delete list and delete those items. Can't read and change with the same iterator. That's slower. But sound. I'm OK with that. It avoids subtle bugs.

ridiculous_fish 5y ago

An illustrative example is a string set which remembers its insertion order. In C++ you may write: struct OrderedSet { deque<string> storage; set<string_view> vals; } The deque holds the string contents, and the set holds views of those contents. This is safe because the deque has iterator stability, and it's pleasant because the `vals` set can just be a regular set. As you say Rust does not allow this; its answer is IndexSet, and it is implemented differently, like: struct OrderedSet { Vec<String> buckets; RawTable<usize> hashToBucketIndex; } RawTable is a hash table that doesn't know how to compute a hash or determine equality. Instead, you provide it with closures to do those tasks, but at the call site (not construction time). Basically Rust achieves the same thing through a layer of indirection involving indexes, which is a common pattern.