www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Scope Containers

reply bitwise <bitwise.pvt gmail.com> writes:
Hi,

Does anybody know if there are any container libraries that make 
use of scope for iterator/range safety? or is the implementation 
of scope even ready for that right now?

Thanks
Mar 09
next sibling parent reply Eugene Wissner <belka caraus.de> writes:
On Saturday, 9 March 2019 at 16:14:34 UTC, bitwise wrote:
 Hi,

 Does anybody know if there are any container libraries that 
 make use of scope for iterator/range safety? or is the 
 implementation of scope even ready for that right now?

 Thanks
tanya's containers are good candidates for scope/return, since they don't rely on reference counting and GC like Phobos containers. I intend to introduce scope/return ranges soon, because currently using the containers is not very safe. But honestly I'm not expecting much from these annotations. Last time I tested "return" with dip25 it could catch only some basic cases, but not more complicated cases where I assign ranges to variables and then use them.
Mar 09
parent bitwise <bitwise.pvt gmail.com> writes:
On Saturday, 9 March 2019 at 16:34:18 UTC, Eugene Wissner wrote:
 On Saturday, 9 March 2019 at 16:14:34 UTC, bitwise wrote:
 Hi,

 Does anybody know if there are any container libraries that 
 make use of scope for iterator/range safety? or is the 
 implementation of scope even ready for that right now?

 Thanks
tanya's containers are good candidates for scope/return, since they don't rely on reference counting and GC like Phobos containers. I intend to introduce scope/return ranges soon, because currently using the containers is not very safe. But honestly I'm not expecting much from these annotations. Last time I tested "return" with dip25 it could catch only some basic cases, but not more complicated cases where I assign ranges to variables and then use them.
Ok thanks, I'll have a look. All I really need is scoped return values so ranges/iterators and such can't leave the scope of their containers. So even a partial implementation would suffice if it was reliable.
Mar 09
prev sibling parent reply Atila Neves <atila.neves gmail.com> writes:
On Saturday, 9 March 2019 at 16:14:34 UTC, bitwise wrote:
 Hi,

 Does anybody know if there are any container libraries that 
 make use of scope for iterator/range safety? or is the 
 implementation of scope even ready for that right now?

 Thanks
I wrote this: https://github.com/atilaneves/automem/blob/master/source/automem/vector.d
Mar 10
parent reply bitwise <bitwise.pvt gmail.com> writes:
On Sunday, 10 March 2019 at 12:06:10 UTC, Atila Neves wrote:
 I wrote this:

 https://github.com/atilaneves/automem/blob/master/source/automem/vector.d
I'm confused by the use of scope. For example, what effect does scope have here? this(this) scope { ... } I don't see any ranges/iterators in that class either, which is what's at issue for me. At present, it seems impossible to create a memory-safe container that supports iterators or ranges in D, unless it's entirely GC. The best attempt I've seen is std.Array, which uses a ref-counted/pointer-to-pointer payload to make sure any ranges that were given out can see the changes to the payload. Isn't it specified that a struct should be moveable in D though? So as soon as you memcpy an std.Array everything starts exploding/double-deleting. Also, this seems like it would apply to *any* library based ref-counted implementation. So it seems like scope is the last hope for creating an safe nogc container that can give out ranges/iterators. Even adding a move-constructor to D seems like a no-go since it's expected that structs can be memcpy'ed. Am I wrong about this? Thanks
Mar 10
parent reply Atila Neves <atila.neves gmail.com> writes:
On Sunday, 10 March 2019 at 15:12:03 UTC, bitwise wrote:
 On Sunday, 10 March 2019 at 12:06:10 UTC, Atila Neves wrote:
 I wrote this:

 https://github.com/atilaneves/automem/blob/master/source/automem/vector.d
I'm confused by the use of scope. For example, what effect does scope have here? this(this) scope { ... }
Like `const`, `scope` on a member function means that the `this` reference is `scope`.
 I don't see any ranges/iterators in that class either,
https://github.com/atilaneves/automem/blob/2a97acba94d6fe0bf9ba07fec99e86e46aa0f2a1/source/automem/vector.d#L134 https://github.com/atilaneves/automem/blob/2a97acba94d6fe0bf9ba07fec99e86e46aa0f2a1/source/automem/vector.d#L159 https://github.com/atilaneves/automem/blob/2a97acba94d6fe0bf9ba07fec99e86e46aa0f2a1/source/automem/vector.d#L145 static assert(isInputRange!(Vector!int));
 At present, it seems impossible to create a memory-safe 
 container that supports iterators or ranges in D, unless it's 
 entirely GC.

 The best attempt I've seen is std.Array, which uses a 
 ref-counted/pointer-to-pointer payload to make sure any ranges 
 that were given out can see the changes to the payload. Isn't 
 it specified that a struct should be moveable in D though? So 
 as soon as you memcpy an std.Array everything starts 
 exploding/double-deleting. Also, this seems like it would apply 
 to *any* library based ref-counted implementation. So it seems 
 like scope is the last hope for creating an  safe  nogc 
 container that can give out ranges/iterators. Even adding a 
 move-constructor to D seems like a no-go since it's expected 
 that structs can be memcpy'ed.

 Am I wrong about this?
I would think so, especially since I wrote Vector to be safe with dip1000. Look at this unit test for not being able to escape the payload for example: https://github.com/atilaneves/automem/blob/master/tests/ut/vector.d#L229
Mar 10
parent reply bitwise <bitwise.pvt gmail.com> writes:
On Sunday, 10 March 2019 at 16:10:10 UTC, Atila Neves wrote:
 On Sunday, 10 March 2019 at 15:12:03 UTC, bitwise wrote:
 On Sunday, 10 March 2019 at 12:06:10 UTC, Atila Neves wrote:
 [...]
I'm confused by the use of scope. For example, what effect does scope have here? this(this) scope { ... }
Like `const`, `scope` on a member function means that the `this` reference is `scope`.
Interesting. I'll have to look up some examples.
 I don't see any ranges/iterators in that class either,
https://github.com/atilaneves/automem/blob/2a97acba94d6fe0bf9ba07fec99e86e46aa0f2a1/source/automem/vector.d#L134 https://github.com/atilaneves/automem/blob/2a97acba94d6fe0bf9ba07fec99e86e46aa0f2a1/source/automem/vector.d#L159 https://github.com/atilaneves/automem/blob/2a97acba94d6fe0bf9ba07fec99e86e46aa0f2a1/source/automem/vector.d#L145 static assert(isInputRange!(Vector!int));
 At present, it seems impossible to create a memory-safe 
 container that supports iterators or ranges in D, unless it's 
 entirely GC.

 The best attempt I've seen is std.Array, which uses a 
 ref-counted/pointer-to-pointer payload to make sure any ranges 
 that were given out can see the changes to the payload. Isn't 
 it specified that a struct should be moveable in D though? So 
 as soon as you memcpy an std.Array everything starts 
 exploding/double-deleting. Also, this seems like it would 
 apply to *any* library based ref-counted implementation. So it 
 seems like scope is the last hope for creating an  safe  nogc 
 container that can give out ranges/iterators. Even adding a 
 move-constructor to D seems like a no-go since it's expected 
 that structs can be memcpy'ed.

 Am I wrong about this?
I would think so, especially since I wrote Vector to be safe with dip1000. Look at this unit test for not being able to escape the payload for example: https://github.com/atilaneves/automem/blob/master/tests/ut/vector.d#L229
Ok, but this container copies the entire collection in postblit: https://github.com/atilaneves/automem/blob/2a97acba94d6fe0bf9ba07fec99e86e46aa0f2a1/source/automem/vector.d#L104 So if you try to treat it like a range, you'll take a performance hit every time you trigger the postblit, which seems likely. Isn't it reasonable to assume a range should act like a reference to data, rather than a copy of it?
Mar 10
next sibling parent Alex <sascha.orlov gmail.com> writes:
On Sunday, 10 March 2019 at 17:36:09 UTC, bitwise wrote:
 Isn't it reasonable to assume a range should act like a 
 reference to data, rather than a copy of it?
I think, this highly depends on data and the container. What if data is stored inside the container? How the container can reference data if it is the one and only holder? In which format do you expect the container to release the raw data? How do you suppose to synchronize a data movement and references to it, if the container contains only references? But what, if data may not be copied or moved, but the container manages the data by copy? Is data assumed to be destroyed/invalidated after the container is destroyed? And why?
Mar 10
prev sibling parent reply Atila Neves <atila.neves gmail.com> writes:
On Sunday, 10 March 2019 at 17:36:09 UTC, bitwise wrote:
 On Sunday, 10 March 2019 at 16:10:10 UTC, Atila Neves wrote:
 On Sunday, 10 March 2019 at 15:12:03 UTC, bitwise wrote:
 [...]
Like `const`, `scope` on a member function means that the `this` reference is `scope`.
Interesting. I'll have to look up some examples.
 [...]
https://github.com/atilaneves/automem/blob/2a97acba94d6fe0bf9ba07fec99e86e46aa0f2a1/source/automem/vector.d#L134 https://github.com/atilaneves/automem/blob/2a97acba94d6fe0bf9ba07fec99e86e46aa0f2a1/source/automem/vector.d#L159 https://github.com/atilaneves/automem/blob/2a97acba94d6fe0bf9ba07fec99e86e46aa0f2a1/source/automem/vector.d#L145 static assert(isInputRange!(Vector!int));
 [...]
I would think so, especially since I wrote Vector to be safe with dip1000. Look at this unit test for not being able to escape the payload for example: https://github.com/atilaneves/automem/blob/master/tests/ut/vector.d#L229
Ok, but this container copies the entire collection in postblit: https://github.com/atilaneves/automem/blob/2a97acba94d6fe0bf9ba07fec99e86e46aa0f2a1/source/automem/vector.d#L104
Well, yes. As it says in the module ddoc, it's my version of C++'s std::vector. If you don't want it to copy, pass by ref.
 So if you try to treat it like a range, you'll take a 
 performance hit every time you trigger the postblit, which 
 seems likely.
You can pass it by ref like I mention above, or you could slice it and pass the slice instead. Without DIP1000 passing the slice wouldn't be safe but with it, it is. Again, just like std::vector, which is pretty much always passed by const ref. But safer and with a default allocator.
 Isn't it reasonable to assume a range should act like a 
 reference to data, rather than a copy of it?
It depends.
Mar 10
parent reply bitwise <bitwise.pvt gmail.com> writes:
On Sunday, 10 March 2019 at 18:46:14 UTC, Atila Neves wrote:
 On Sunday, 10 March 2019 at 17:36:09 UTC, bitwise wrote:
 On Sunday, 10 March 2019 at 16:10:10 UTC, Atila Neves wrote:
 On Sunday, 10 March 2019 at 15:12:03 UTC, bitwise wrote:
 [...]
Like `const`, `scope` on a member function means that the `this` reference is `scope`.
Interesting. I'll have to look up some examples.
 [...]
https://github.com/atilaneves/automem/blob/2a97acba94d6fe0bf9ba07fec99e86e46aa0f2a1/source/automem/vector.d#L134 https://github.com/atilaneves/automem/blob/2a97acba94d6fe0bf9ba07fec99e86e46aa0f2a1/source/automem/vector.d#L159 https://github.com/atilaneves/automem/blob/2a97acba94d6fe0bf9ba07fec99e86e46aa0f2a1/source/automem/vector.d#L145 static assert(isInputRange!(Vector!int));
 [...]
I would think so, especially since I wrote Vector to be safe with dip1000. Look at this unit test for not being able to escape the payload for example: https://github.com/atilaneves/automem/blob/master/tests/ut/vector.d#L229
Ok, but this container copies the entire collection in postblit: https://github.com/atilaneves/automem/blob/2a97acba94d6fe0bf9ba07fec99e86e46aa0f2a1/source/automem/vector.d#L104
Well, yes. As it says in the module ddoc, it's my version of C++'s std::vector. If you don't want it to copy, pass by ref.
 So if you try to treat it like a range, you'll take a 
 performance hit every time you trigger the postblit, which 
 seems likely.
You can pass it by ref like I mention above, or you could slice it and pass the slice instead. Without DIP1000 passing the slice wouldn't be safe but with it, it is. Again, just like std::vector, which is pretty much always passed by const ref. But safer and with a default allocator.
 Isn't it reasonable to assume a range should act like a 
 reference to data, rather than a copy of it?
It depends.
This container seems good for short-lived usage. If I wanted to pass a bunch of filenames to a function for processing, I would consider this container Ok, because it would allocate once, then be consumed as a range without having to copy anything. For any kind of persistent storage though, I would consider the performance costs of using this container's range functionality too high. At this point, I'm leaning toward just building separate containers. One would be a vector-like container that's nogc and only has an indexer, but does not support iterators/ranges. The second would be a class-based container which *would* have range/iterator support since the ranges/iterators could safely contain pointers back to the GC-allocated collection for range checks and such. I do think the idea of making the container itself the range is interesting, but what ruins it for me is the fact that ranges are consumable. So I'm wondering if it would work well to use an integer index for the range implementation instead of actually depleting the elements as you iterate, and have a "reset" function to refill the range so that no copying is necessary. I wonder how useful it would be to have some sort of NonConsumableRange concept that included reset() function. Bit
Mar 11
parent reply Atila Neves <atila.neves gmail.com> writes:
On Monday, 11 March 2019 at 17:00:35 UTC, bitwise wrote:
 On Sunday, 10 March 2019 at 18:46:14 UTC, Atila Neves wrote:
 On Sunday, 10 March 2019 at 17:36:09 UTC, bitwise wrote:
 On Sunday, 10 March 2019 at 16:10:10 UTC, Atila Neves wrote:
 On Sunday, 10 March 2019 at 15:12:03 UTC, bitwise wrote:
 [...]
Like `const`, `scope` on a member function means that the `this` reference is `scope`.
Interesting. I'll have to look up some examples.
 [...]
https://github.com/atilaneves/automem/blob/2a97acba94d6fe0bf9ba07fec99e86e46aa0f2a1/source/automem/vector.d#L134 https://github.com/atilaneves/automem/blob/2a97acba94d6fe0bf9ba07fec99e86e46aa0f2a1/source/automem/vector.d#L159 https://github.com/atilaneves/automem/blob/2a97acba94d6fe0bf9ba07fec99e86e46aa0f2a1/source/automem/vector.d#L145 static assert(isInputRange!(Vector!int));
 [...]
I would think so, especially since I wrote Vector to be safe with dip1000. Look at this unit test for not being able to escape the payload for example: https://github.com/atilaneves/automem/blob/master/tests/ut/vector.d#L229
Ok, but this container copies the entire collection in postblit: https://github.com/atilaneves/automem/blob/2a97acba94d6fe0bf9ba07fec99e86e46aa0f2a1/source/automem/vector.d#L104
Well, yes. As it says in the module ddoc, it's my version of C++'s std::vector. If you don't want it to copy, pass by ref.
 So if you try to treat it like a range, you'll take a 
 performance hit every time you trigger the postblit, which 
 seems likely.
You can pass it by ref like I mention above, or you could slice it and pass the slice instead. Without DIP1000 passing the slice wouldn't be safe but with it, it is. Again, just like std::vector, which is pretty much always passed by const ref. But safer and with a default allocator.
 Isn't it reasonable to assume a range should act like a 
 reference to data, rather than a copy of it?
It depends.
This container seems good for short-lived usage.
Why?
 If I wanted to pass a bunch of filenames to a function for 
 processing, I would consider this container Ok, because it 
 would allocate once, then be consumed as a range without having 
 to copy anything.
Or you don't consume it all and slice it (as I mentioned in my last post): safe unittest { scope v = vector(1, 2, 3); static void fun(R)(R range) { import std.array: array; assert(range.array == [1, 2, 3]); } fun(v[]); // wasn't consumed assert(v[] == [1, 2, 3]); } Again, it's safe because the slice is scoped.
 For any kind of persistent storage though, I would consider the 
 performance costs of using this container's range functionality 
 too high.
There aren't any performance costs. You pass a fat pointer just like you would with a GC array.
 I do think the idea of making the container itself the range is 
 interesting, but what ruins it for me is the fact that ranges 
 are consumable.
Which is why Vector has both opSlice and copies by default. It's only a range itself if the element type is mutable, otherwise it doesn't even define popFront.
 So I'm wondering if it would work well to use an integer index 
 for the range implementation
That's what slices are.
Mar 11
next sibling parent reply "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Mon, Mar 11, 2019 at 06:29:23PM +0000, Atila Neves via Digitalmars-d wrote:
 On Monday, 11 March 2019 at 17:00:35 UTC, bitwise wrote:
[...]
 I do think the idea of making the container itself the range is
 interesting, but what ruins it for me is the fact that ranges are
 consumable.
Which is why Vector has both opSlice and copies by default. It's only a range itself if the element type is mutable, otherwise it doesn't even define popFront.
[...] Generally, it's a bad idea to conflate a container with a range over the container, precisely for this reason. In this respect, built-in arrays are a bad example, because we think of them as containers, yet they are at the same time ranges. (Though strictly speaking, "arrays" are just slices of the underlying containers that are managed by druntime and not really directly manipulatable. But nobody thinks of them in this way; the concept of "array" is much easier to grasp and reason with than "slice over druntime-managed container".) The recommended approach is to have the container be distinct from a range over its elements, and provide such a range via a member function, commonly chosen to be opSlice. T -- Real men don't take backups. They put their source on a public FTP-server and let the world mirror it. -- Linus Torvalds
Mar 11
parent Atila Neves <atila.neves gmail.com> writes:
On Monday, 11 March 2019 at 19:23:19 UTC, H. S. Teoh wrote:
 On Mon, Mar 11, 2019 at 06:29:23PM +0000, Atila Neves via 
 Digitalmars-d wrote:
 [...]
[...]
 [...]
[...] Generally, it's a bad idea to conflate a container with a range over the container, precisely for this reason. In this respect, built-in arrays are a bad example, because we think of them as containers, yet they are at the same time ranges. (Though strictly speaking, "arrays" are just slices of the underlying containers that are managed by druntime and not really directly manipulatable. But nobody thinks of them in this way; the concept of "array" is much easier to grasp and reason with than "slice over druntime-managed container".) [...]
Maybe so. I'll have to think about it and maybe change the API so it's no longer a range.
Mar 11
prev sibling parent reply bitwise <bitwise.pvt gmail.com> writes:
On Monday, 11 March 2019 at 18:29:23 UTC, Atila Neves wrote:
 On Monday, 11 March 2019 at 17:00:35 UTC, bitwise wrote:
 On Sunday, 10 March 2019 at 18:46:14 UTC, Atila Neves wrote:
 On Sunday, 10 March 2019 at 17:36:09 UTC, bitwise wrote:
 On Sunday, 10 March 2019 at 16:10:10 UTC, Atila Neves wrote:
 On Sunday, 10 March 2019 at 15:12:03 UTC, bitwise wrote:
 [...]
Like `const`, `scope` on a member function means that the `this` reference is `scope`.
Interesting. I'll have to look up some examples.
 [...]
https://github.com/atilaneves/automem/blob/2a97acba94d6fe0bf9ba07fec99e86e46aa0f2a1/source/automem/vector.d#L134 https://github.com/atilaneves/automem/blob/2a97acba94d6fe0bf9ba07fec99e86e46aa0f2a1/source/automem/vector.d#L159 https://github.com/atilaneves/automem/blob/2a97acba94d6fe0bf9ba07fec99e86e46aa0f2a1/source/automem/vector.d#L145 static assert(isInputRange!(Vector!int));
 [...]
I would think so, especially since I wrote Vector to be safe with dip1000. Look at this unit test for not being able to escape the payload for example: https://github.com/atilaneves/automem/blob/master/tests/ut/vector.d#L229
Ok, but this container copies the entire collection in postblit: https://github.com/atilaneves/automem/blob/2a97acba94d6fe0bf9ba07fec99e86e46aa0f2a1/source/automem/vector.d#L104
Well, yes. As it says in the module ddoc, it's my version of C++'s std::vector. If you don't want it to copy, pass by ref.
 So if you try to treat it like a range, you'll take a 
 performance hit every time you trigger the postblit, which 
 seems likely.
You can pass it by ref like I mention above, or you could slice it and pass the slice instead. Without DIP1000 passing the slice wouldn't be safe but with it, it is. Again, just like std::vector, which is pretty much always passed by const ref. But safer and with a default allocator.
 Isn't it reasonable to assume a range should act like a 
 reference to data, rather than a copy of it?
It depends.
This container seems good for short-lived usage.
Why?
 If I wanted to pass a bunch of filenames to a function for 
 processing, I would consider this container Ok, because it 
 would allocate once, then be consumed as a range without 
 having to copy anything.
Or you don't consume it all and slice it (as I mentioned in my last post): safe unittest { scope v = vector(1, 2, 3); static void fun(R)(R range) { import std.array: array; assert(range.array == [1, 2, 3]); } fun(v[]); // wasn't consumed assert(v[] == [1, 2, 3]); } Again, it's safe because the slice is scoped.
 For any kind of persistent storage though, I would consider 
 the performance costs of using this container's range 
 functionality too high.
There aren't any performance costs. You pass a fat pointer just like you would with a GC array.
 I do think the idea of making the container itself the range 
 is interesting, but what ruins it for me is the fact that 
 ranges are consumable.
Which is why Vector has both opSlice and copies by default. It's only a range itself if the element type is mutable, otherwise it doesn't even define popFront.
 So I'm wondering if it would work well to use an integer index 
 for the range implementation
That's what slices are.
At first, I missed the use of scope here:
 auto opSlice(this This)() scope return
My reasoning was that using automem/vector for persistent storage required it to be iterated over, which couldn't be done without consuming the container, or copying it. I see now that you can iterate by returning a scoped slice of the internal data store, but this could be unsafe too. If you called reserve on the container, the returned slice could end up dangling if a non-gc allocator was used, even if the returned slice was scoped. I think that if opSlice returned a scoped range with a pointer back to the original container, then it would be easy for the range object to detect the state of the container, even including if it had been moved from and left in it's initial state. As long as the range couldn't leave the stack-frame of the container, I think this would be totally safe.
Mar 11
parent reply Atila Neves <atila.neves gmail.com> writes:
On Monday, 11 March 2019 at 19:40:06 UTC, bitwise wrote:
 On Monday, 11 March 2019 at 18:29:23 UTC, Atila Neves wrote:
 On Monday, 11 March 2019 at 17:00:35 UTC, bitwise wrote:
 On Sunday, 10 March 2019 at 18:46:14 UTC, Atila Neves wrote:
 On Sunday, 10 March 2019 at 17:36:09 UTC, bitwise wrote:
 On Sunday, 10 March 2019 at 16:10:10 UTC, Atila Neves wrote:
 On Sunday, 10 March 2019 at 15:12:03 UTC, bitwise wrote:
 [...]
<snip>
 I see now that you can iterate by returning a scoped slice of 
 the internal data store, but this could be unsafe too. If you 
 called reserve on the container, the returned slice could end 
 up dangling if a non-gc allocator was used, even if the 
 returned slice was scoped.
Unless there's a bug in my implementation or in dip1000, no, it can't be unsafe.
 I think that if opSlice returned a scoped range with a pointer 
 back to the original container,
It does.
 As long as the range couldn't leave the stack-frame of the 
 container, I think this would be totally safe.
It can't; that's the whole point of dip1000. Again, that's why this test passes: https://github.com/atilaneves/automem/blob/e34b2b0c1510efd91064a9cbf83cbf43856c1a5c/tests/ut/vector.d#L229
Mar 11
next sibling parent bitwise <bitwise.pvt gmail.com> writes:
On Monday, 11 March 2019 at 20:02:05 UTC, Atila Neves wrote:
 On Monday, 11 March 2019 at 19:40:06 UTC, bitwise wrote:
 On Monday, 11 March 2019 at 18:29:23 UTC, Atila Neves wrote:
 On Monday, 11 March 2019 at 17:00:35 UTC, bitwise wrote:
 On Sunday, 10 March 2019 at 18:46:14 UTC, Atila Neves wrote:
 On Sunday, 10 March 2019 at 17:36:09 UTC, bitwise wrote:
 On Sunday, 10 March 2019 at 16:10:10 UTC, Atila Neves 
 wrote:
 On Sunday, 10 March 2019 at 15:12:03 UTC, bitwise wrote:
 [...]
<snip>
 I see now that you can iterate by returning a scoped slice of 
 the internal data store, but this could be unsafe too. If you 
 called reserve on the container, the returned slice could end 
 up dangling if a non-gc allocator was used, even if the 
 returned slice was scoped.
Unless there's a bug in my implementation or in dip1000, no, it can't be unsafe.
So if I use opSlice() to retrieve a slice of the internal array, then call reserve on the vector causing it to deallocate, then try to access the slice I just retrieved, what would you call that?
 I think that if opSlice returned a scoped range with a pointer 
 back to the original container,
It does.
https://github.com/atilaneves/automem/blob/e34b2b0c1510efd91064a9cbf83cbf43856c1a5c/source/automem/vector.d#L284 I mean a custom range object that contains a pointer back to the original container. This code returns a pointer directly to memory inside the container. It's not wrapped in a range object, and it doesn't have any pointer back to the vector, which it would need because the internal memory of the vector could be deallocated, but the actual vector object itself could not (relative to the scoped range). At most, the container could be moved from and considered empty by the range it returned.
 As long as the range couldn't leave the stack-frame of the 
 container, I think this would be totally safe.
It can't; that's the whole point of dip1000. Again, that's why this test passes: https://github.com/atilaneves/automem/blob/e34b2b0c1510efd91064a9cbf83cbf43856c1a5c/tests/ut/vector.d#L229
I was referring to my suggested implementation of a range, not the slice returned by automem/vector. automem/vector's opSlice() could potentially allow you to dereference an invalid pointer. I don't know if detecting that is within the scope of dip1000, but I would still consider it a hole in the implementation.
Mar 11
prev sibling parent reply Petar Kirov [ZombineDev] <petar.p.kirov gmail.com> writes:
On Monday, 11 March 2019 at 20:02:05 UTC, Atila Neves wrote:
 <snip>
 I see now that you can iterate by returning a scoped slice of 
 the internal data store, but this could be unsafe too. If you 
 called reserve on the container, the returned slice could end 
 up dangling if a non-gc allocator was used, even if the 
 returned slice was scoped.
Unless there's a bug in my implementation or in dip1000, no, it can't be unsafe.
I think that this is what bitwise was talking about: https://github.com/atilaneves/automem/issues/25
Mar 12
parent reply bitwise <bitwise.pvt gmail.com> writes:
On Tuesday, 12 March 2019 at 18:06:39 UTC, Petar Kirov 
[ZombineDev] wrote:
 On Monday, 11 March 2019 at 20:02:05 UTC, Atila Neves wrote:
 <snip>
 I see now that you can iterate by returning a scoped slice of 
 the internal data store, but this could be unsafe too. If you 
 called reserve on the container, the returned slice could end 
 up dangling if a non-gc allocator was used, even if the 
 returned slice was scoped.
Unless there's a bug in my implementation or in dip1000, no, it can't be unsafe.
I think that this is what bitwise was talking about: https://github.com/atilaneves/automem/issues/25
I hadn't seen this, but yes, thanks. Bit
Mar 12
parent reply Atila Neves <atila.neves gmail.com> writes:
On Tuesday, 12 March 2019 at 21:06:17 UTC, bitwise wrote:
 On Tuesday, 12 March 2019 at 18:06:39 UTC, Petar Kirov 
 [ZombineDev] wrote:
 On Monday, 11 March 2019 at 20:02:05 UTC, Atila Neves wrote:
 <snip>
 I see now that you can iterate by returning a scoped slice 
 of the internal data store, but this could be unsafe too. If 
 you called reserve on the container, the returned slice 
 could end up dangling if a non-gc allocator was used, even 
 if the returned slice was scoped.
Unless there's a bug in my implementation or in dip1000, no, it can't be unsafe.
I think that this is what bitwise was talking about: https://github.com/atilaneves/automem/issues/25
I hadn't seen this, but yes, thanks. Bit
After thinking about what bitwise said, I was actually going to post back similar code. The code in the github issue is problematic, but it's a far cry from how such errors are usually introduced in C++. Normally it's because another thread has a reference to the now dangling pointer, or calling a function with the slice means it gets escaped somewhere. Another way would be to write this: void oops(ref Vector!int vec, int[] slice); Which is also convoluted. Neither case would pass code review. Either way, thanks for pointing out the possible issue. I'm going to have to think long and hard about whether it's possible to fix it with the language we have now.
Mar 13
next sibling parent reply Olivier FAURE <couteaubleu gmail.com> writes:
On Wednesday, 13 March 2019 at 08:49:37 UTC, Atila Neves wrote:
 Either way, thanks for pointing out the possible issue. I'm 
 going to have to think long and hard about whether it's 
 possible to fix it with the language we have now.
One possibility might be to implement at run time what rust does at compile time, eg make it impossible to mutate vector as long as one or more readable view to its content exists. So for instance, make opSlice and opIndex return a struct that bumps a reference counter up inside the vector; the counter is bumped down once that struct is destructed. As long as the number of "live" slices is non-zero, the vector isn't allowed to re-allocate.
 The code in the github issue is problematic, but it's a far cry 
 from how such errors are usually introduced in C++. Normally 
 it's because another thread has a reference to the now dangling 
 pointer, or calling a function with the slice means it gets 
 escaped somewhere.
 Which is also convoluted. Neither case would pass code review.
I don't think that's the point. It's supposed to be *impossible* to get a memory corruption in safe code. Not "convoluted and wouldn't pass code review", impossible. When you write a trusted function, getting a memory corruption with that function is supposed to be impossible as well. Other people have gone over why memory safety is necessary before. Not all code goes through code review, sometimes review miss errors even for critical applications, etc.
Mar 13
next sibling parent reply Atila Neves <atila.neves gmail.com> writes:
On Wednesday, 13 March 2019 at 11:35:02 UTC, Olivier FAURE wrote:
 On Wednesday, 13 March 2019 at 08:49:37 UTC, Atila Neves wrote:
 [...]
One possibility might be to implement at run time what rust does at compile time, eg make it impossible to mutate vector as long as one or more readable view to its content exists. So for instance, make opSlice and opIndex return a struct that bumps a reference counter up inside the vector; the counter is bumped down once that struct is destructed. As long as the number of "live" slices is non-zero, the vector isn't allowed to re-allocate.
 [...]
 [...]
I don't think that's the point. It's supposed to be *impossible* to get a memory corruption in safe code. Not "convoluted and wouldn't pass code review", impossible. When you write a trusted function, getting a memory corruption with that function is supposed to be impossible as well. Other people have gone over why memory safety is necessary before. Not all code goes through code review, sometimes review miss errors even for critical applications, etc.
I just tagged v0.6.0. I made `opSlice` ` system` given what has been discussed here. I introduced a new member function `range` which return a forward range that keeps a pointer to the vector inside of it. Coupled with dip1000 it seems to do the trick. I also made it so `Vector` is no longer an input range itself.
Mar 13
next sibling parent reply bitwise <bitwise.pvt gmail.com> writes:
On Wednesday, 13 March 2019 at 13:29:51 UTC, Atila Neves wrote:
 [...]

 I introduced a new member function `range` which return a 
 forward range that keeps a pointer to the vector inside of it. 
 Coupled with dip1000 it seems to do the trick.
Awesome. I'm trying to test the same thing, but -dip1000 seems to have no effect, and -scope is unrecognized. Do I have to download the beta or GIT HEAD to get a functional DIP1000 implementation? Thanks again, Bit
Mar 15
parent Atila Neves <atila.neves gmail.com> writes:
On Friday, 15 March 2019 at 16:11:43 UTC, bitwise wrote:
 On Wednesday, 13 March 2019 at 13:29:51 UTC, Atila Neves wrote:
 [...]

 I introduced a new member function `range` which return a 
 forward range that keeps a pointer to the vector inside of it. 
 Coupled with dip1000 it seems to do the trick.
Awesome. I'm trying to test the same thing, but -dip1000 seems to have no effect, and -scope is unrecognized. Do I have to download the beta or GIT HEAD to get a functional DIP1000 implementation? Thanks again, Bit
It definitely has an effect. This code compiles with -dip1000, doesn't without: void main() safe { int i; fun(&i); } void fun(scope int* i) safe { } Works as intended on dmd 2.085.0 and 2.084.1.
Mar 18
prev sibling parent reply Olivier FAURE <couteaubleu gmail.com> writes:
On Wednesday, 13 March 2019 at 13:29:51 UTC, Atila Neves wrote:
 I made `opSlice` ` system` given what has been discussed here.

 I introduced a new member function `range` which return a 
 forward range that keeps a pointer to the vector inside of it. 
 Coupled with dip1000 it seems to do the trick.
Have you tested it with opIndex? You'd probably get the same problem, since it returns a reference to data that might be reallocated later.
Mar 16
parent Atila Neves <atila.neves gmail.com> writes:
On Saturday, 16 March 2019 at 12:17:20 UTC, Olivier FAURE wrote:
 On Wednesday, 13 March 2019 at 13:29:51 UTC, Atila Neves wrote:
 I made `opSlice` ` system` given what has been discussed here.

 I introduced a new member function `range` which return a 
 forward range that keeps a pointer to the vector inside of it. 
 Coupled with dip1000 it seems to do the trick.
Have you tested it with opIndex? You'd probably get the same problem, since it returns a reference to data that might be reallocated later.
Ugh, you're right. Not sure what to do about that one, but thanks for bringing it up!
Mar 18
prev sibling parent bitwise <bitwise.pvt gmail.com> writes:
On Wednesday, 13 March 2019 at 11:35:02 UTC, Olivier FAURE wrote:
 One possibility might be to implement at run time what rust 
 does at compile time, eg make it impossible to mutate vector as 
 long as one or more readable view to its content exists.

 So for instance, make opSlice and opIndex return a struct that 
 bumps a reference counter up inside the vector; the counter is 
 bumped down once that struct is destructed. As long as the 
 number of "live" slices is non-zero, the vector isn't allowed 
 to re-allocate.
I'm not 100% sure, but it kinda seeems like this solution requires, but is obviated by scope.
 It's supposed to be *impossible* to get a memory corruption in 
  safe code. Not "convoluted and wouldn't pass code review", 
 impossible. When you write a  trusted function, getting a 
 memory corruption with that function is supposed to be 
 impossible as well.
I agree that safety should be a strict guarantee.
Mar 15
prev sibling parent bitwise <bitwise.pvt gmail.com> writes:
On Wednesday, 13 March 2019 at 08:49:37 UTC, Atila Neves wrote:
 On Tuesday, 12 March 2019 at 21:06:17 UTC, bitwise wrote:
 [...]
    Bit
After thinking about what bitwise said, I was actually going to post back similar code. The code in the github issue is problematic, but it's a far cry from how such errors are usually introduced in C++. Normally it's because another thread has a reference to the now dangling pointer, or calling a function with the slice means it gets escaped somewhere.
I think that in C++, iterator validity is a hard concept to overlook. I would bet that even relatively new C++ programmers are familiar with the idea. I think most intro C++ classes teach this type of thing relatively early on. This awareness prevents/mitigates a lot of potential problems, resulting in the issue being underrepresented in peoples negative views of C++ (or so it would seem, I've seen no actual data on this). In any case, it would be great if callers could just ignore the issue completely.
 void oops(ref Vector!int vec, int[] slice);
Yeah, I remember Walter's post about how this will mess with ref-counted objects as well. IIRC, the solution was compiler support double-incrementing the ref-count when it finds this case. I wonder if this is actually necessary though, because in C++, shared_ptr has the aliasing constructor, and with D's templates, something like RefCounted could be modified to expose the members of it's contained type as properties that worked like shared_ptr's aliasing constructor, wrapping the returned field value in a ref-counted object that shares the ref-count of its parent object. If this was done, the member exposing that slice would do the extra increment without compiler support.
 Either way, thanks for pointing out the possible issue. I'm 
 going to have to think long and hard about whether it's 
 possible to fix it with the language we have now.
Thanks for exploring this issue with me. I agree its tough to build a proper container right now, but I do believe I have more options than when I started. I just found this as well, which I'm pretty excited about: https://github.com/dlang/DIPs/blob/master/DIPs/accepted/DIP1014.md The version of std::vector from Visual Studio makes use of this for iterator validation in debug mode. The vector heap-allocates a "proxy" object and stores it's own pointer in it. When the vector moves (and it's move ctor is called), it updates the pointer in the proxy object. It also gives this proxy out to iterators so they can track the original vector. Without any type of move callback in D, such an implementation would have been impossible, so this is awesome news.
Mar 15