Challenge: write a reference counted slice that works as much as possible like a built-in slice

[Andrei Alexandrescu]

On 2021-11-08 20:14, tsbockman wrote:
> On Monday, 8 November 2021 at 21:42:12 UTC, Andrei Alexandrescu wrote:
>> Eduard Staniloiu (at the time a student I was mentoring) tried really 
>> hard to define a built-in slice RCSlice(T) from the following spec:
> 
> Your spec is very focused on homogenizing the API for GC and RC slices 
> as much as (or rather, more than) possible.
> 
> But, it isn't possible to make a truly `@safe`, general-purpose RC slice 
> in D *at all* right now, even without all the additional constraints 
> that you are placing on the problem.
> 
> Borrowing is required for a general-purpose RC type, so that the payload 
> can actually be used without a reference to the payload escaping outside 
> the lifetime of the counting reference. But, the effective lifetime of 
> the counting reference is not visible to the `scope` borrow checker, 
> because at any point the reference's destructor may be manually called, 
> potentially `free`ing the payload while there is still an extant 
> borrowed reference.

Walter would argue that his work on scope makes that possible too. The 
short of it is getting an answer to "can it be done" is important in and 
of itself because it gives us hints on what needs to be done.

> With current language semantics, the destructor (and any other similar 
> operations, such as reassignment) of the reference type must be 
> `@system` to prevent misuse of the destructor in `@safe` code.
>      https://issues.dlang.org/show_bug.cgi?id=21981
> 
> The solution to this problem is to introduce some way of telling the 
> compiler, "this destructor is `@safe` to call automatically at the end 
> of the object's scope, but `@system` to call early or manually."

This I'm not worried about. `@trusted` should be fine in low-level code, 
no? `destroy` is not safe. What am I missing?

> Also, the DIP1000 implementation is very buggy and incomplete; it 
> doesn't work right for several kinds of indirections, including slices 
> and `class` objects:
> https://forum.dlang.org/thread/zsjqqeftthxtfkytrnwp@forum.dlang.org?page=1

<nod>

>> - work in pure code just like T[] does
>> - work with qualifiers like T[] does, both RCSlice!(qual T) and 
>> qual(RCSlice!T)
> 
> I wrote a semi-`@safe` reference counting system for D recently, which 
> includes slices, weak references, shared references with atomic 
> counting, etc. It works well enough to be useful to me (way better than 
> manual `malloc` and `free`), but not well enough to be a candidate for 
> the standard library due to the above compiler bugs.

Interesting, have you published the code?

> `RCSlice!(qual T)` is no problem; the reference count and the payload do 
> not need to use the same qualifiers. Whether the count is `shared` or 
> not can be tracked statically as part of the RC type, so the "const 
> might be immutable, and therefore have a shared reference count, and 
> therefore require expensive atomic operations" issue that you raise is 
> easy enough to solve.
> 
> On the other hand, `pure` compatibility and a usable 
> `immutable(RCSlice!T)` are mutually exclusive, I think:
> 
> **Either** the reference count is part of the target of the RC type's 
> internal indirection, in which case it can be mutated in `pure` code, 
> but is frozen by an outer, transitive `immutable`, **or** the reference 
> count is conceptualized as an entry in a separate global data structure 
> which can be located by using the address of the payload as a key, 
> meaning that incrementing it does not mutate the target, but is im`pure`.

Yah, my thoughts exactly. My money is on the latter option. The 
reference counter is metadata, not data, and should not be treated as 
part of the data even though implementation-wise it is.

Eduard and I stopped short of being able to formalize this.

> I believe the former solution (compatible with `pure`, but not outer 
> `immutable`) is preferable since it is the most honest, least weird 
> solution, and therefore least likely to trip up either the compiler 
> developers or the users somehow.
> 
> What you seem to be asking for instead is a way to trick the type system 
> into agreeing that mutating a reference count doesn't actually mutate 
> anything, which is nonsense. If that's really necessary for some reason, 
> it needs to be special cased into the language spec, like how `pure` 
> explicitly permits memory allocation.

It's not nonsense. Or if it is a lot other things can be categorized as 
nonsense, such as the GC recycling memory of one type and presenting it 
as a different type etc.