Abstract Projection

Aug 2024

Concrete projection

Swift member access has projection semantics. Consider this Project wrapper, which stores its wrapped value inline as a stored property.

struct Project<T: ~Copyable>: ~Copyable {
  let value: T
}

Now consider wrapping a value of Inner that can produce a lifetime-dependent value of NE:

struct NE: ~Escapable {}

struct Inner: ~Copyable {
  borrowing func ne() -> NE {
    NE()
  }
}

let project: Project<Inner>

The composition:

let ne = project.value.ne()

correctly generates the dependency: project -> ne because the compiler understands that project -> value is a projection of projects lifetime. We can think of project.value implicitly borrows 'project' over its use.

Lifetime abstraction over a property

Concrete projection does not allow for resilience or property abstraction, as shown here:

struct Wrap<T: ~Copyable>: ~Copyable {
  let _t: T
  let value: T { consuming get { _t } }
}

let wrapper: Wrap<Inner>
let ne = wrapper.value.ne() // ERROR: 'ne' escapes its scope

let ne = wrapper.value.ne() consumes 'wrapper' and generates the dependency value -> ne.

Reference projection in Rust

For comparison, consider a Rust wrapper that projects a an abstract value:

struct Wrap<T> {
  _t: T
}

impl<T> Wrap<T> {
  fn get_value<'a>(&'a self) -> &'a T { &self._t }
}

To project a value out of Wrap we need to explicitly force a shared reference to self and return a shared reference to its value with the same lifetime. We can reformulate the problem above in Rust:

struct NE<'a> {
  x: PhantomData<&'a bool>
}

struct Inner {}

impl Inner {
  fn ne<'a>(&'a self) -> NE<'a> {
    NE {x: PhantomData}
  }
}

let wrapper: Wrap<Inner>
let ne = wrapper.value.ne() // OK: 'ne' is used with the scope of wrapper'

Projection via coroutine

Swift can express a borrow scope, similar to what Rust does above, with a _read accessor.

struct Wrap<T: ~Copyable>: ~Copyable {
  let _t: T
  let value: T { _read { _t } }
}

let wrapper: Wrap<Inner>
let ne = wrapper.value.ne() // OK: 'ne' us used with the scope of 'wrapper'.

But coroutines are limiting. Although they can be nested, a yielded valid can only be used within the scope of the outermost coroutine. No functions or closures can be invoked on that stack without forcing a new local scope. Here, the getNE function forces an unnecessary local scope:

func getNE(_ wrapper: Wrap) -> NE {
  return wrapper.value.ne() // ERROR: 'ne' escapes the local access of 'wrapper'
}

In fact, coroutines are generally the wrong shape to model projection which does not require execution of "cleanup code" after the projection's last use.

Projection via Borrow

With ~Escapable types, Swift will be able to provide an abstraction over borrowed values independent from coroutines. Borrow<T> is copyable type that can refer to a borrow of a noncopyable value.

struct Borrow<T: ~Copyable>: Copyable, ~Escapable {
  unowned(unsafe) value: T // theoretical construct
}

Borrow<T> is fully general over the borrowed type. Unlike a "safe pointer" type, it supports values that may not have a stable address. As such, Borrow<T> needs compiler support for a polymorphic representation of its value. If it's concrete type is address-only, then the borrowed value is a pointer. Otherwise, value is a bitwise-borrow. Swift cannot always represent a borrow as a pointer, because some values, notably tuples and function types, require reabstraction at generic function boundaries. It is also highly desirable to avoid extra indirection when performance matters.

Borrow<T> can be used to implement abstract projections in aribtrary wrapper types:

struct Wrap<T: ~Copyable>: ~Copyable {
  let _t: T
  let borrowedValue: Borrow<T> { borrowing get { _t } }
}

Accessing borrowedValue returns a Borrow<T> that depends on the borrow of self. Crucially, if self is already borrowed, the returned value depends on the existing borrow scope. No new borrow scope is created, because, unlike a coroutine, no local cleanup is needed. Now we have something with the semantics of a regular projection, albeit with cumbersome syntax:

let wrapper: Wrap<Inner>
let ne = wrapper.borrowedValue.value.ne()

This correctly generates the dependency: wrapper -> ne

Note borrowedValue.value is handled just like a regular member projection. So the compiler will follow a chain of nested borrows back to its root, the first access on wrapper.

Projection via dependent copies

Returning a Borrow<T> from a getter (or any method) extends the lifetime of self over all uses of the returned value because it is declared to be unconditionally ~Escapable. In general, returning a ~Escapable value always extends the lifetime of some parameter. Removing escapability from the static type forces the compiler to track its lifetime dependencies, even if the value is conditionally escapable.

So, the only additional capability that Borrow<T> give us is copybility. If the returned value is already Copyable, then Borrow<T> is never required. We can achieve the same behavior using a conditionally escapable static type:

struct Wrap<T: ~Copyable & ~Escapable>: Copyable & ~Escapable {
  let _t: T
  let borrowedValue: T { borrowing get { _t } }
}

let wrapper: Wrap<Inner>
let ne = wrapper.borrowedValue.ne()

As with Borrow<T>, this correctly generates the dependency: wrapper -> ne without requiring an intermediate wrapper type.

Lifetime abstraction over a pointer

A unique pointer that provides its value via an internal pointer should have the same dependency semantics on its unwrapped value as if it were a member of a struct.

unsafeAddress does not yet support lifetime dependence

struct Box<T: ~Copyable>: ~Copyable {
  let pointer: UnsafePointer<T>

  var value: T {
    unsafeAddress {
      pointer
    }
  }
}

let box: Box<Inner>

let ne = box.value.ne() currently escapes 'ne'.

unsafeAddress is not a feature we want to expose. It's only for bootstrapping the implementation of UnsafePointer.

unsafeAddress does not generalize to non-addressable value, so it will never be a complete, generic solution. Nonetheless, it might be useful as a stop-gap. Adding support for ~Copyable would take SILGen work though.

addressible read

We could introduce a new kind of addressable access, similar to unsafeAddress that has projection semantics.

struct Box<T: ~Copyable>: ~Copyable {
  let pointer: UnsafePointer<T>

   var value: T {
    @addressable _read {
      yield pointer
    }
  }
}

This also won't generalize to non-addressable types. And forcing a coroutine to achieve projection semantics doesn't make much sense since the whole point is that we want a value that does not require a locally scoped cleanup.

Borrow

Borrow<T> is a general answer to both abstraction over properties and pointers. It was defined above as:

struct Borrow<T: ~Copyable & ~Escapable>: Copyable, ~Escapable {
  unowned(unsafe) value: T // theoretical construct
}

Box can return a Borrow<T> that depends on its own lifetime rather than on the scope of a local access to its pointee:

struct Box<T: ~Copyable>: ~Copyable {
  let pointer: UnsafePointer<T>

  var borrowedValue: Borrow<T> {
    get {
      Borrow(pointer.pointee)
    }
  }
}

let box: Box<Inner>

The returned Borrow<T> will depend on the borrow of self, not on the access of value:

let ne = box.borrowedValue.value.ne()

Correctly generates the dependency: box -> ne

This works because extracting an escapable value from Borrow<T> behaves like a regular concrete projection. Even though the value projected from borrowedValue.value is itself escapable, the compiler to tracks its lifetime as derived from the lifetime of borrowedValue.

Parallel with Rust

Let's look at how Rust solves the the problem above. Here's the original problem in Swift:

struct NE: ~Escapable {}

struct Inner: ~Copyable {
  borrowing func ne() -> NE {
    NE()
  }
}

struct Box<T: ~Copyable>: ~Copyable {
  let pointer: UnsafePointer<T>
}

And the equivalent implementation in Rust:

struct NE<'a> {
  x: PhantomData<&'a bool>
}

struct Inner {}

impl Inner {
  fn ne<'a>(&'a self) -> NE<'a> {
    NE {x: PhantomData}
  }
}

let box: Box<Inner>

Rust explicitly requires the caller to create a reference to Inner before calling ne(). Swift similarly forces the caller to borrow Inner with exclusivity semantics.

Rust let's you directly access Box<Inner> as such:

box.ne()

Let's spell that out for comparison:

box.deref().ne()

In Rust, calling box.deref forces a borrow scope over box:

fn deref(&self) -> &T

Swift equivalent to a reference is a ~Escapable type. That's why, to force a borrow of Box when unwrapping it, we needed to introduce a Borrow:

struct Box<T: ~Copyable>: ~Copyable {
  var value: Borrow<T>

borrowed return value

So far, none of our use cases for Borrow<T> have required any variable declaration of type Borrrow<T>.

struct Box<T: ~Copyable>: ~Copyable {
  let pointer: UnsafePointer<T>

  var borrowedValue: borrow T {
    get {
      pointer.pointee
    }
  }
}

TODO: update the sections below to use borrowed returns

Optional

With Borrow<T>, we can at last write Optional.borrowingMap that propagates dependencies across the Optional:

extension Optional where Wrapped: ~Copyable & ~Escapable {
  @lifetime(self, body)
  borrowing func borrowingMap<E: Error, U: ~Copyable & ~Escapable>(
    _ body: @lifetime(capture, wrapped) (_ wrapped: borrowing Wrapped) throws(E) -> Borrow<U>
  ) throws(E) -> Borrow<U>?
}

Array iteration

To understand the utility of Borrow<T> in designing ~Copyable APIs, consider this example of an array that is backed by noncopyable (uniquely referenced) storage.

class CopyOnWriteContainer<Element: ~Copyable> {
  var _storage: UniqueStorage

  var iterator: UniqueStorageIterator {
    get { storage.iterator }
  }

  var storage: Borrow<UniqueStorage> { get { Borrow(_storage) } }
}

struct UniqueStorageIterator: ~Escapable { ... }

struct UniqueStorage: ~Copyable {
  var iterator: { get { ... }  }
}

let container: CopyOnWriteContainer= ...
let iterator = container.iterator
_ = iterator // OK

Without being able to make a copy of its borrowed unqiue storage via Borrow<T>, container` would not be able to return an iterator.

Acknowledgement

This explanation of abstract projection is based on examples provided by Karoy Lorenty and Alejandro Alonso and on Joe Groff's vision.

atrick/2024-08-abstract-projection.md