Surfacing External References

[mjp41]

Motivation

Strict region ownership makes it impossible to do some efficient representations. Although, regions allow a doubly linked list to be expressed, that is actually insufficient for the common pattern of using a doubly linked list. Typically, you keep a reference to the Node to allow O(1) removal, but due to strict region ownership, that limits the applicability, and does not allow that reference to be across any concurrency boundary, e.g. in different cowns.

The runtime supports a concept of external reference that allows for a safe cross cown reference. The concurrency is safe as promotion back to the original reference requires a reference to the owning region, and thus cannot be promoted unless you already have access to the object's region.

Proposal

Here is a proposed API surface we could use to expose external region references:

class External[T]
{
  // Creates an external reference to an object in a region.
  // We treat the external reference as immutable as it is effectively
  // an immutable token that can be exchanged for access to the original
  // reference.
  get_handle(v: T & mut) : External[T] & imm {...}

  // External references can be promoted to the original reference
  // Returns None if
  // * the provided region is not the one containing this object, or
  // * the object has been collected by this regions allocation strategy
  //   external references may not keep objects live.
  // Otherwise, returns the reference passed to `get_handle` to create
  // the handle.
  promote[U](self: mut, region: U & mut) : (T & mut) | (None & imm) {...}
}

The core motivating example for external references is doubly linked notification lists.

class NotificationNode
{
  next: NotificationNode;
  prev: NotificationNode;
  to_notify: cown[INotify];
}

The client of the notification center does something like:

var n = new NotificationNode;
n.to_notify = ...
var e = ExternalReference.get_handle(n);
// Transfer ownership of the region containing n, to the notification center.
// Internally, this would merge the region containing the node into 
// the region containing the doubly linked list  
when (notification_center) {  notification_center.add(n) }
...
//some time later the external reference can be used to remove the 
//node from the doubly linked list.  It promotes the external reference
//and if successful, can perform the standard DLL pointer surgery on the node.
when (notification_centre) { notification_center.remove(e) }

Alternative

Is it better to surface this as a class with a static and an instance method. Or should this be more primitively exposed in the type system to allow for better flow typing? At the moment, this would require a match on the result, would the following be better:

  // e: External[T]
  if (e is_in r)
  {
     // e: T & mut 
     ...
  }

This is a more complex change. Proposal to stick to exposing as API until we have experience with using?

Pre-requisites.

The raw API can be exposed directly without any additional work.

The full example requires region merge to be exposed in the language as well.

Notes

The run time has a unit test for this functionality.

[plietar]

I like the External class, especially given how little change it needs in the rest of the compiler (probably just some builtins).

I think the signature of promote needs to be a little different:

promote(self: imm, region: mut) : (T & mut) | (None & imm) {...}

Note the imm receiver, and dropping the unnecessary U type parameter.

[mjp41]

I agree with your changes. I had spotted the U bit, but not the imm, when discussing this yesterday with @sylvanc.

@sylvanc proposed giving it a Pony style partial function/exception like type:

promote(self: imm, region: mut) : (T & mut) throws NotIn

Then you could use a Pony-style try block to get flow sensitive typing:

try
{
  var x = e.promote(r);
  ...
}

This naturally leads into the design of exceptions, and how to make interesting DSL like accessors.

[mjp41]

So @sylvanc's actual proposal for the client was

try (var x = e.promote(r)) 
{
   C1
}

Where this doesn't catch exceptions in C1. This seems a little different to Pony.

I think we could surface the External class as I proposed with your corrections very easily, but longer term I think integrating with exceptions/partial functions would make things much nicer.

[plietar]

The full example requires region merge to be exposed in the language as well.

I actually think this can be done with just a builtin:

merge[class T](x: T & iso, into: mut): T & mut
  where return in into