Thoughts on safe GC-less slices

Ben Jones fake at fake.fake
Tue Nov 16 23:31:47 UTC 2021


After being inspired by some good ideas in a few of the other 
threads I distilled some of my thoughts on some ideas about how 
to get safe slices without GC.  I think it's kind of moon-shot-y 
and will probably not be backwards compatible, but wanted to 
share.

Currently slices conflate 2 different ideas: a view of a range of 
memory, and ownership of a range of memory.  I'd say it's sort of 
analogous to both std::vector and a pair of iterators in C++.  
I'm not sure there's a good way to do both things safely with a 
single type without GC due since the iterators can become 
unknowingly invalidated.

An analogous situation in D is objects vs `ref`s.  D avoids the 
"iterator invalidation" problem by not allowing ref variables, 
only ref parameters.  Because of that, the lifetime of the object 
is guaranteed to outlive the `ref` to that object.

So, one way to potentially have a GC-less dynamic array would be 
to define 2 different types: an owning slice and a borrowing 
slice.  You can store values of an owning slice, but borrowing 
slices can only be passed to functions.

That's sort of the solution that I think Paul Backus proposed 
where instead of returning a slice, the RCSlice type (or whatever 
it was) took a delegate to operate on the slice, which enforced 
that lifetime constraint.  His idea is what prompted me to write 
this.

The syntax for that is obviously not great, but we might be able 
to do better by stealing from functional languages.  Perhaps 
something like this:

```
let (borrowedSlice; owningSlice) in {
    //code
}
```

mean essentially the same as

```
owningSlice.apply( (borrowedSlice) => { //code} );
```

One way to implement this is to have owningSlice implement opLet 
(this is similar to (I think?) Andrei's opFunctionCall idea)

The safety provided here seems to align pretty well with what's 
in the @live implementation as it's mostly about passing `scope` 
stuff to functions.

Can it be implemented without horrendous breakage?   Probably 
not.  Ideally the existing `[]` could be used for both types of 
slice depending on context. Some thoughts on how to transition:

* All slice variables become owning slices
* Owning slice should have to be assigned from unique rvalues 
like from `.dup` or `new`
* It's OK to shrink a borrowed slice, but attempting to grow one 
would make a new owning slice or nor be allowed, I think

I originally thought this might be related to/helpful for an RC 
slice, but that's not really the same thing.  In that case, I 
think you'd have multiple "owningslice-like" objects that are 
related and you'd still use opLet to work with them as necessary.

Any ideas here worth exploring further?

Feel free to discuss [on 
github](https://gist.github.com/benjones/fa015904eba3e2a7ce1a75b3f6506cc7) if you prefer.


More information about the Digitalmars-d mailing list