Orphan ranges

[Jonathan M Davis]

On Sunday, April 15, 2012 11:34:11 Andrei Alexandrescu wrote:
> I'm making good progress on an allocator design. If things come together
> as I hope, it'll kick some serious ass.
> 
> I'm currently looking at four allocation models:
> 
> * straight GC, safe (no deallocation)
> * GC + the ability to free memory
> * malloc/free, unsafe, buyer beware (STL-level safety)
> * reference counted (based on either malloc or GC+free)
> * region (scoped)
> 
> I need to kink out a few details, most important being - is safety part
> of the allocator or an extricable property that's a different policy?
> For now I have a related question about orphan ranges.
> 
> Consider this motivating example:
> 
> void main()
> {
> int[] x;
> {
> auto b = new int[20];
> x = b[5 .. $ - 5];
> }
> ... use x ...
> }
> 
> The range x is a 10-elements range that originates in a 20-element
> array. There is no safe way to access the original array again, so in a
> sense the other 10 elements are "lost". That's why I call x an orphan
> range - a range of which original container is gone.
> 
> Built-in arrays work routinely like that, and in fact the originating
> arrays are not distinguished by type in any way from their ranges (be
> they orphan or not). The question is, what should std.container do about
> orphan ranges in general? Should it allow them, disallow them, or leave
> the decision open (e.g. to be made by the allocator)? Depending on what
> way we go, the low-level design would be quite different.

So, the problem that we have is basically

void main()
{
 Range r;
 {
 Container c = //allocated using allocator, however that works
 r = c[];
 }
 //Container may or may not exist in memory, depending on the allocator,
 //but the range does exist and may or may not be valid.
}

How is this different from an iterator or range being invalidated after a 
function is called on the container which alters its state? You could 
theoretically add plumbing to the range to keep track of whether it's valid or 
not, but we're not doing that or planning to do that with std.container are 
we? And if we're not doing that, why would we go out of our way to do so in 
the case where a custom allocator causes a container to exist for a shorter 
lifetime than it would normally?

- Jonathan M Davis