www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Will D always have a way to rebind an arbitrary data type?

reply FeepingCreature <feepingcreature gmail.com> writes:
I'm trying to get a utility type `HeadMutable` merged in an 
internal utility library,
and one of the points of criticism in review is that the 
mechanism I'm using (Turducken, if you remember 
https://forum.dlang.org/thread/ekbxqxhnttihkoszzvxl forum.dlang.org ) is
extremely hacky; even though all parts of it are probably technically
deliberately added to the language, it seems they add up to a pretty evil
backdoor in the type system.

Anyway, it's not a problem if this specific (semi-intentional?) 
"loophole" gets closed. What we're worried about is ending up in 
a state where this idiom is not expressible in the language *at 
all*.

So my question, are the language developers willing to commit to 
the following statement?

"There will always be a way in D to write a ` nogc` container 
type with two operations: `put(T)` and `T get()`, so that the 
result value of `get` is value identical to the parameter of 
`put`, *for any arbitrary `T`,* especially value-immutable T, 
with correct lifetime accounting of the stored value."
Sep 20 2021
next sibling parent Johan <j j.nl> writes:
On Monday, 20 September 2021 at 08:43:48 UTC, FeepingCreature 
wrote:

 "There will always be a way in D to write a ` nogc` container 
 type with two operations: `put(T)` and `T get()`, so that the 
 result value of `get` is value identical to the parameter of 
 `put`, *for any arbitrary `T`,* especially value-immutable T, 
 with correct lifetime accounting of the stored value."


I believe this is the reason for the introduction of std::launder 
in C++.

-Johan
Sep 20 2021
prev sibling next sibling parent reply FeepingCreature <feepingcreature gmail.com> writes:
On Monday, 20 September 2021 at 08:43:48 UTC, FeepingCreature 
wrote:

 So my question, are the language developers willing to commit 
 to the following statement?

 "There will always be a way in D to write a ` nogc` container 
 type with two operations: `put(T)` and `T get()`, so that the 
 result value of `get` is value identical to the parameter of 
 `put`, *for any arbitrary `T`,* especially value-immutable T, 
 with correct lifetime accounting of the stored value."


Ping? I feel this is kind of important.
Sep 27 2021
parent reply Dennis <dkorpel gmail.com> writes:
On Monday, 27 September 2021 at 14:34:40 UTC, FeepingCreature 
wrote:

 Ping? I feel this is kind of important.


When I try to answer the question, several issues come up.
- I don't understand the concrete problem you're trying to solve. 
I haven't found the need for head mutable yet so I don't know the 
challenges that arise when trying to write such a type.
- I don't understand the code in your Turducken post because it's 
too complex to just read and comprehend for me. I need something 
to look for when analyzing code like that.
- The question is addressed to "the language developers", which 
is a group of people that come and go and submit pull requests to 
official dlang repos. I can't speak on behalf of everyone and 
can't promise an indefinite commitment like that.
- What is "value-immutable T" and "correct lifetime accounting"?
Sep 27 2021
parent FeepingCreature <feepingcreature gmail.com> writes:
On Monday, 27 September 2021 at 16:00:01 UTC, Dennis wrote:

 When I try to answer the question, several issues come up.
 - I don't understand the concrete problem you're trying to 
 solve. I haven't found the need for head mutable yet so I don't 
 know the challenges that arise when trying to write such a type.


I want to be able to write, in user code, containers that 
encapsulate arbitrary, ie. including immutable, data types, 
without *necessarily* becoming immutable themselves, and without 
requiring constant allocations. Efficient, safe, low-gc 
containers for arbitrary data types.


 - I don't understand the code in your Turducken post because 
 it's too complex to just read and comprehend for me. I need 
 something to look for when analyzing code like that.


The core of it is just

T value;

union { T value; }

struct { union { T value; } }

The ornamental union disables T's destructor, because unions 
disable destructors: https://github.com/dlang/dmd/pull/5830 This 
protects us from the destructor ever running for instance during 
Turducken cleanup, and noticing an invalid value of `T`.

The ornamental struct forces a particular codepath in 
`moveEmplace` that uses memcpy in a way that lets us bypass the 
`immutable` fields in T. This is the one thing that I think is 
kind of a bug. But if we're not escaping `value` by ref, it's 
still safe - because nobody can observe `T`'s immutable values 
changing.


 - The question is addressed to "the language developers", which 
 is a group of people that come and go and submit pull requests 
 to official dlang repos. I can't speak on behalf of everyone 
 and can't promise an indefinite commitment like that.
 - What is "value-immutable T" and "correct lifetime accounting"?


`immutable int i` = "value immutable" or "head immutable".
`immutable(char)[] str;` = "reference immutable" or "tail 
immutable".

Head/value immutable types cannot be reassigned; their value is 
immutable. (Tail immutable types can.)

This makes it hard to store value immutable types in a 
datastructure. For instance, appending to an array of an 
immutable data type only works because D's runtime magically 
ignores array immutability for the purposes of appending.

All I'm asking for is the same capability as a user. Preferably 
without having to resort to GC breaking, unstable hacks like 
`cast(void[]) (&member[0 .. 1])`. (But I will if I have to!)

edit: On consideration, as long as the actual data is just `union 
{ T; }` I can probably get away with the void cast and skip the 
`moveEmplace` entirely. That should make my approach less 
magical, and maybe get it to pass review? I will go try.
Sep 27 2021
prev sibling parent reply Paul Backus <snarwin gmail.com> writes:
On Monday, 20 September 2021 at 08:43:48 UTC, FeepingCreature 
wrote:

 I'm trying to get a utility type `HeadMutable` merged in an 
 internal utility library,
 and one of the points of criticism in review is that the 
 mechanism I'm using (Turducken, if you remember 
 https://forum.dlang.org/thread/ekbxqxhnttihkoszzvxl forum.dlang.org ) is
extremely hacky; even though all parts of it are probably technically
deliberately added to the language, it seems they add up to a pretty evil
backdoor in the type system.


And indeed `Turducken` as presented in that post is unsound, 
since it allows ` safe` code to observe mutation of `immutable` 
data:

     void main()  safe
     {
         Turducken!(immutable(int)) td;
         td.bind(123);
         (ref immutable(int) value) {
             assert(value == 123);
             td.bind(456);
             assert(value == 123); // kaboom
         }(td.value);
     }

(Runnable: https://run.dlang.io/is/xCjYIz)

Because D does not have any notion of exclusive references (like 
Rust's `&mut`), the container has to assume that when `bind` is 
called, there may be outstanding references to the contained 
value. Which means that the call to `moveEmplace` cannot actually 
be ` trusted` unless the value is mutable.

So, at the very least, this has to be ` system`. Whether it's 
legitimate even then is a deeper question--if you mutate 
`immutable` data in the woods and nobody hears it, does it cause 
undefined behavior?
Sep 27 2021
parent reply FeepingCreature <feepingcreature gmail.com> writes:
On Monday, 27 September 2021 at 20:55:56 UTC, Paul Backus wrote:

 And indeed `Turducken` as presented in that post is unsound, 
 since it allows ` safe` code to observe mutation of `immutable` 
 data:

     void main()  safe
     {
         Turducken!(immutable(int)) td;
         td.bind(123);
         (ref immutable(int) value) {
             assert(value == 123);
             td.bind(456);
             assert(value == 123); // kaboom
         }(td.value);
     }

 (Runnable: https://run.dlang.io/is/xCjYIz)

 Because D does not have any notion of exclusive references 
 (like Rust's `&mut`), the container has to assume that when 
 `bind` is called, there may be outstanding references to the 
 contained value. Which means that the call to `moveEmplace` 
 cannot actually be ` trusted` unless the value is mutable.

 So, at the very least, this has to be ` system`. Whether it's 
 legitimate even then is a deeper question--if you mutate 
 `immutable` data in the woods and nobody hears it, does it 
 cause undefined behavior?


Yes, in a real implementation of Turducken (not just a concept 
demo), `value` would be `private` and not ref readable. It's 
purely the `ref T value` that ruins the const system, but that's 
not a necessary or even desired part of my feature set. This is 
why I'm also not interested in the current "Rebindable for 
structs" PR, because `Rebindable` exposes its value by ref and is 
thus inherently unsafe for exactly the reason you describe.

Hence the thing I asked for was "the value to be returned from a 
(non-ref) function", an operation which copies exactly the parts 
of the value that head-mutable makes mutable. ("head" == 
"by-value", pretty much exactly.)
Sep 27 2021
parent reply Paul Backus <snarwin gmail.com> writes:
On Tuesday, 28 September 2021 at 06:09:19 UTC, FeepingCreature 
wrote:

 Yes, in a real implementation of Turducken (not just a concept 
 demo), `value` would be `private` and not ref readable. It's 
 purely the `ref T value` that ruins the const system, but 
 that's not a necessary or even desired part of my feature set. 
 This is why I'm also not interested in the current "Rebindable 
 for structs" PR, because `Rebindable` exposes its value by ref 
 and is thus inherently unsafe for exactly the reason you 
 describe.

 Hence the thing I asked for was "the value to be returned from 
 a (non-ref) function", an operation which copies exactly the 
 parts of the value that head-mutable makes mutable. ("head" == 
 "by-value", pretty much exactly.)


This sounds like basically the same thing as Rust's [`Cell`][1] 
type.

I think to implement this safely it might be necessary to have 
the storage typed as mutable (something like `union { Unconst!T 
payload; }`) and cast to/from `T` in `get` and `set`, since 
otherwise `set` invokes UB by [mutating memory typed as `const` 
or `immutable`][2]. Other than that, I don't see any problem.

[1]: https://doc.rust-lang.org/std/cell/
[2]: https://dlang.org/spec/const3.html#removing_with_cast
Sep 28 2021
parent reply FeepingCreature <feepingcreature gmail.com> writes:
On Tuesday, 28 September 2021 at 16:37:53 UTC, Paul Backus wrote:

 This sounds like basically the same thing as Rust's [`Cell`][1] 
 type.

 I think to implement this safely it might be necessary to have 
 the storage typed as mutable (something like `union { Unconst!T 
 payload; }`) and cast to/from `T` in `get` and `set`, since 
 otherwise `set` invokes UB by [mutating memory typed as `const` 
 or `immutable`][2]. Other than that, I don't see any problem.

 [1]: https://doc.rust-lang.org/std/cell/
 [2]: https://dlang.org/spec/const3.html#removing_with_cast


Now that you mention it, this causes a problem: it's 
**impossible** to have correctly typed memory here in D as it 
stands. Unqual/Unconst is *not* enough, because structs can have 
const fields, a state that cannot be stripped by any means. And 
`void[sizeof(T)]` breaks garbage collector typing.

The only recourse I can see offhand, without language changes, 
would be to laborously build an "equivalent but mutable type" out 
of `void[size_t.sizeof]` and `ubyte[size_t.sizeof]` fragments.

Or ignore that UB and hope it doesn't matter.

Ideas? Options? Any hope at all?
Sep 29 2021
parent FeepingCreature <feepingcreature gmail.com> writes:
On Wednesday, 29 September 2021 at 07:27:50 UTC, FeepingCreature 
wrote:

 The only recourse I can see offhand, without language changes, 
 would be to laborously build an "equivalent but mutable type" 
 out of `void[size_t.sizeof]` and `ubyte[size_t.sizeof]` 
 fragments.


I've done this: https://code.dlang.org/packages/rebindable 
https://forum.dlang.org/thread/qnzxruolyeozohflretb forum.dlang.org
Sep 29 2021