Escape analysis (full scope analysis proposal)

[Michel Fortin]

On 2008-11-02 10:12:46 -0500, Andrei Alexandrescu 
<SeeWebsiteForEmail at erdani.org> said:

> It looks like things will move that way. Bartosz, Walter and I talked a 
> lot yesterday about it - a lot of crazy things were on the table! The 
> next step is to make this a reference, which is highly related to 
> escape analysis. At the risk of anticipating a bit an unfinalized 
> design, here's what's on the table:
> 
> * Continue an "anything goes" policy for *explicit* pointers, i.e. 
> those written explicitly by user code with stars and stuff.

That's a little disapointing. I was hoping for something to fix all 
holes. I know it isn't easy to design and implement, but once done I 
firmly believe it would have the potential to completely eliminate the 
need for explicit memory allocation. For the programmer, it's a good 
trade: less worrying about what needs to be dynamically allocated and 
better documented function signatures.

Perhaps that would be too much of a departure from C and C++ though.


> * Disallow pointers in SafeD.

Again a consequence of not having a full scoping solution.

Couldn't you allow pointers in SafeD, while disallowing taking the 
address of local variables? This would limit pointers to heap-allocated 
variables. And disallow pointer arithmetic too.


> * Make all ref parameters scoped by default. There will be impossible 
> for a function to escape the address of a ref parameter without a cast. 
> I haven't proved it to myself yet, but I believe that if pointers are 
> not used and with the amendments below regarding arrays and delegates, 
> this makes things entirely safe. In Walter's words, "it buttons things 
> pretty tight".

If this means you can't implement a swap function for this struct, then 
I think you're right that it's safe:

	struct A
	{
		ref A a;
	}

	void swap(ref A a0, ref A a1);

On the other side, if you can implement the swap function, then calling 
it is unsafe since you can rebind a reference to another without being 
able to check that their scopes are compatible.

So basically, references must always be initialized at construction and 
should be non-rebindable, just like in C++. (Hum, and I should mention 
I don't like too much references in C++.)


> * Make this a reference so that it obeys what references obey.

Ah, so that's why Walter wanted to change that suddenly. This is a good 
thing by itself, even without correct scoping.


> * If people want to implement e.g. linked lists, they should do it with 
> classes. Implementing them with structs will require casts to obtain 
> and escape &this. That also means they'd be using pointers, so anything 
> goes - pointers are not restricted from escaping.
> 
> * There are two cases in which things escape without the user 
> explicitly using pointers: delegates and dynamic arrays initialized 
> from stack-allocated arrays.
> 
> * For delegates require the scope keyword in the signature of the 
> callee. A scoped delegate cannot be stored, only called or passed down 
> to another function that in turn takes a scoped delegate. This makes 
> scope delegates entirely safe. Non-scoped delegates use dynamic 
> allocation.

Again, I'd say that if you can implement a swap function with those 
scope delegates, it's unsafe. Case in point:

	void f1(ref scope void delegate() arg)
	{
		int i;
		scope void f2()
		{
			++i;
		}

		scope void delegate() inner = &f2;
		swap(arg, inner); // this should be an error.
		arg = inner; // this too should be an error.
	}

If you can't rebind a the value of a scope delegate pointer, then all is fine.


> * We don't have an idea for dynamic arrays initialized from 
> stack-allocated arrays.

Either disallow it, either keep it as unsafe as pointers (bad for SafeD 
I expect), or implement a complete scope-checking system (if you do it 
for arrays, you'll have done it for pointers too). You don't have much 
choice there, as arrays are pretty much the same thing as pointers.


> Thoughts? Ideas?

I'm under the impression that scope classes could be dangerous in this 
system: an object reference is not necessarly on the heap.

Personally, I'd have liked to have a language where you can be 
completely scope safe, where you could document interfaces so they know 
the scope they're evolving in. This concept of something in between is 
a nice attempt at a compromize, but I find it somewhat limitting.


-- 
Michel Fortin
michel.fortin at michelf.com
http://michelf.com/