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