Witnesses.swift

//
// Un-lowered Hylo definitions, mapped to Swift.  These are here to
// to help explain the lowered forms that follow.
//

/// All types
protocol _Type {
  static var size: Int { get }
  static var alignment: Int { get }
}

extension _Type {
  static var size: Int { MemoryLayout<Self>.size }
  static var alignment: Int { MemoryLayout<Self>.alignment }
}

/// Types that can be destroyed.
protocol Deinitializable: _Type {
  static func deinitialize(_: consuming Self)
}

extension Deinitializable {
  static func deinitialize(_: consuming Self) {}
}

/// Types that can be constructed without arguments
protocol New: _Type {
  static func new() -> Self
}

/// Types that can be moved in memory.
protocol Movable: _Type {
  static func move(_ x: consuming Self) -> Self
}

extension Movable {
  static func move(_ x: consuming Self) -> Self { x }
}

/// Types having an infinite chain of associated types, that can produce
/// an instance of the next type in the chain.
protocol P: Movable, New {
  associatedtype A: P
  func f() -> A
}

/// A generic P that stores an instance of its type parameter.
struct X<T: New&Movable&Deinitializable>: P, Deinitializable {
  typealias A = X<Self>
  let magic = 12345
  let t: T

  static func new() -> Self { .init(t: T.new()) }
  func f() -> A {
    assert(magic == 12345)
    return A.new() 
  }
}

/// A generic P whose associated A type is its type parameter.
struct Y<U: P>: P, Deinitializable {
  let magic = 54321
  typealias A = U
  static func new() -> Self { .init() }
  func f() -> A {
    assert(magic == 54321)
    return A.new() 
  }
}

//
// Note: Non-requirement-satisfying operations on generic types are
// not shown because they can always be mapped to generic functions.
//

/// Demo generic function 1.
func g<V: Movable&New&Deinitializable>(_: V) {
  let a = X<V>.new()
  defer { type(of: a).deinitialize(a) }
  let b = h(a)
  let ignored = h(b)
  type(of: b).deinitialize(b)
  type(of: ignored).deinitialize(ignored)
}

/// Demo generic function 2.
func h<S: P>(_ b: S) -> S {
  let c = Y<S>.new()
  defer { type(of: c).deinitialize(c) }
  let r = c.f()
  return type(of:r).move(r)
}

//
// Utilities for expressing lowerings
//

typealias _Let = UnsafeRawPointer
typealias _Inout = UnsafeMutableRawPointer
typealias _Set = UnsafeMutableRawPointer
typealias _Sink = UnsafeMutableRawPointer

/// Converts a let to a sink when its lifetime has ended.
func sink(_ p: _Let) -> _Sink { .init(mutating: p) }

/// Temporarily allocates memory with the given `size` and
/// `alignment`, and invokes `body` on that memory, returning the
/// result.
func alloca<R>(size: Int, alignment: Int, body: (UnsafeMutableRawPointer)->R) -> R {
  var storage = [UInt8](repeating: 0, count: size + alignment)
  return storage.withUnsafeMutableBufferPointer {
    let offset = alignment - Int((UInt(bitPattern: $0.baseAddress)) % UInt(alignment))
    return body($0.baseAddress! + offset)
  }
}

//
// Metadata
//
// The key to avoiding the need for a distinct witness table for every
// generic type is to pass a bundle of witnesses—the conformances of
// generic parameters and *their* corresponding metadata—to the
// lowerings of all protocol requirements. For concision, and to allow
// for future expansion, we call these bundles metadata.
//
// In concrete type conformances this metadata can be empty.
//

/// Type erasure for metadata
///
/// Metadata never escapes and downcasts are always forced so we could
/// equally use unsafe pointers.
protocol AnyMetadata {}

//
// Lowerings
//

// Witness tables are expressed here as existential containers of
// types that have no storage.  Thus, every conformance corresponds to
// a *singleton* witness table type.  They never escape so they could
// equally well be unsafe pointers.

/// Witnesss table for the _Type trait.
protocol _TypeWitness {
  /// The metadata format for the conforming (possibly generic) type.
  associatedtype Metadata: AnyMetadata

  // Non-type-erased entry points. We implement these for specific conformances.

  // For convenience and without loss of generality, we have size and
  // alignment return Int directly rather than via _Set parameters.
  func size(metadata: Metadata)->Int
  func alignment(metadata: Metadata)->Int

  // Type-erased entry points. Default implementations below
  // force-downcast and dispatch to the non-type-erased entry points
  // above.  This scheme is merely here to help me write witnesses
  // correctly manually.
  func _size(metadata: AnyMetadata)->Int
  func _alignment(metadata: AnyMetadata)->Int
}

/// Forwarding for type-erasure
extension _TypeWitness {
  func _size(metadata: AnyMetadata)->Int { size(metadata: metadata as! Metadata) }
  func _alignment(metadata: AnyMetadata)->Int  { alignment(metadata: metadata as! Metadata) }
}

protocol DeinitializableWitness: _TypeWitness {
  func deinitialize(metadata: Metadata, sinking _: _Sink)

  func _deinitialize(metadata: AnyMetadata, sinking _: _Sink)
}

extension DeinitializableWitness {
  func _deinitialize(metadata: AnyMetadata, sinking x: _Sink) {
    deinitialize(metadata: metadata as! Metadata, sinking: x)
  }
}

protocol MovableWitness: _TypeWitness {
  func move(metadata: Metadata, from source: _Sink, to target: _Set)
  func _move(metadata: AnyMetadata, from source: _Sink, to target: _Set)
}

extension MovableWitness {
  func _move(metadata: AnyMetadata, from source: _Sink, to target: _Set) {
    move(metadata: metadata as! Metadata, from: source, to: target)
  }

  // For this witness we have a default implementation for the
  // non-type-erased implementation.
  func move(metadata: Metadata, from source: _Sink, to target: _Set) {
    target.copyMemory(from: source, byteCount: size(metadata: metadata))
  }
}

protocol NewWitness: _TypeWitness {
  func new(metadata: Metadata, into target: _Set)
  func _new(metadata: AnyMetadata, into target: _Set)
}

extension NewWitness {
  func _new(metadata: AnyMetadata, into target: _Set) {
    new(metadata: metadata as! Metadata, into: target)
  }
}

protocol PWitness: MovableWitness, NewWitness {
  func f(metadata: Metadata, _self: _Let, result: _Set)
  func _f(metadata: AnyMetadata, _self: _Let, result: _Set)
}

extension PWitness {
  func _f(metadata: AnyMetadata, _self: _Let, result: _Set) {
    f(metadata: metadata as! Metadata, _self: _self, result: result)
  }
}

//
// Technically, we should have distinct witnesses for Deinitializable
// and P.  We could achieve it by factoring _TypeWitness conformance
// into a X_is_Type protocol with default implementations, then have
// X_is_P and X_is_Deinitializable conform to that. Taking a shortcut,
// though, and bundling these conformances into X_is_P.
//

/// Singleton witness type for all Xs.
struct X_is_P: _TypeWitness {
  // We have just one generic parameter; We use a tuple with an empty
  // 2nd element just so we can get labeled member access.
  struct Metadata: AnyMetadata {
    let wt: any NewWitness&MovableWitness&DeinitializableWitness
    let mt: any AnyMetadata
  }

  func size(metadata: Metadata)->Int {
    metadata.wt._size(metadata: metadata.mt) + MemoryLayout<Int>.size
  }

  func alignment(metadata: Metadata)->Int {
    max(metadata.wt._alignment(metadata: metadata.mt), MemoryLayout<Int>.alignment)
  }
}

extension X_is_P: DeinitializableWitness {
  func deinitialize(metadata: Metadata, sinking x: _Sink) {
    assert(x.assumingMemoryBound(to: Int.self).pointee == 12345)
    metadata.wt._deinitialize(metadata: metadata.mt, sinking: x.advanced(by: MemoryLayout<Int>.size))
  }
}

extension X_is_P: MovableWitness {
  func move(metadata: Metadata, from source: _Sink, to target: _Set) {
    assert(source.assumingMemoryBound(to: Int.self).pointee == 12345)
    // move the initial Int.
    target.assumingMemoryBound(to: Int.self).moveInitialize(from: source.assumingMemoryBound(to: Int.self), count: 1)
    metadata.wt._move(metadata: metadata.mt, from: source.advanced(by: MemoryLayout<Int>.size), to: target.advanced(by: MemoryLayout<Int>.size))
  }
}

extension X_is_P: NewWitness {
  func new(metadata: Metadata, into target: _Set) {
    target.assumingMemoryBound(to: Int.self).initialize(to: 12345)
    metadata.wt._new(metadata: metadata.mt, into: target.advanced(by: MemoryLayout<Int>.size))
    assert(target.assumingMemoryBound(to: Int.self).pointee == 12345)
  }
}

extension X_is_P : PWitness {
  func f(metadata: Metadata, _self: _Let, result: _Set) {
    assert(_self.assumingMemoryBound(to: Int.self).pointee == 12345)
    metadata.wt._new(metadata: metadata.mt, into: result)
  }
}

struct Y_is_P: _TypeWitness {
  struct Metadata: AnyMetadata {
    let wu: any PWitness
    let mu: any AnyMetadata
  }

  func size(metadata: Metadata)->Int { MemoryLayout<Int>.size }

  func alignment(metadata: Metadata)->Int { MemoryLayout<Int>.alignment }
}

extension Y_is_P: DeinitializableWitness {
  func deinitialize(metadata: Metadata, sinking x: _Sink) {
    assert(x.assumingMemoryBound(to: Int.self).pointee == 54321)
  }
}

extension Y_is_P: MovableWitness {
  func move(metadata: Metadata, from source: _Sink, to target: _Set) {
    assert(source.assumingMemoryBound(to: Int.self).pointee == 54321)
    target.assumingMemoryBound(to: Int.self).moveInitialize(from: source.assumingMemoryBound(to: Int.self), count: 1)    
  }
}

extension Y_is_P: NewWitness {
  func new(metadata: Metadata, into target: _Set) {
    target.assumingMemoryBound(to: Int.self).initialize(to: 54321)
  }
}

extension Y_is_P : PWitness {
  func f(metadata: Metadata, _self: _Let, result: _Set) {
    assert(_self.assumingMemoryBound(to: Int.self).pointee == 54321)
    metadata.wu._new(metadata: metadata.mu, into: result)
  }
}

func gLowered(wv: any MovableWitness&NewWitness&DeinitializableWitness, mv: AnyMetadata, _: _Let) {
  let mx = X_is_P.Metadata(wt: wv, mt: mv)
  let wx = X_is_P()
  alloca(size: wx.size(metadata: mx), alignment: wx.alignment(metadata: mx)) { a in
    wx.new(metadata: mx, into: a)
    alloca(size: wx.size(metadata: mx), alignment: wx.alignment(metadata: mx)) { b in
      hLowered(ws: wx, ms: mx, b: a, result: b)
      let wxx = X_is_P()
      let mxx = X_is_P.Metadata(wt: wx, mt: mx)
      alloca(size: wxx.size(metadata: mxx), alignment: wxx.alignment(metadata: mxx)) { ignored in
        hLowered(ws: wxx, ms: mxx, b: b, result: ignored)
        wxx.deinitialize(metadata: mxx, sinking: ignored)
      }
      wx.deinitialize(metadata: mx, sinking: b)
    }
    wx.deinitialize(metadata: mx, sinking: a)
  }
}

func hLowered(ws: any PWitness, ms: AnyMetadata, b: _Let, result: _Set) {
  let my = Y_is_P.Metadata(wu: ws, mu: ms)
  let wy = Y_is_P()
  alloca(size: wy.size(metadata: my), alignment: wy.alignment(metadata: my)) { c in
    wy.new(metadata: my, into: c)
    // We'd actually return directly into our result, but for
    // illustration purposes, we'll use a move
    //
    // wy.f(metadata: my, _self: c, result: result)
    alloca(size: ws._size(metadata: ms), alignment: ws._alignment(metadata: ms)) { r in
      wy.f(metadata: my, _self: c, result: r)
      ws._move(metadata: ms, from: r, to: result)
    }
    wy.deinitialize(metadata: my, sinking: c)
  }
}

//---------- Demo --------

var trackedCount = 0

final class Tracked: Movable, New, Deinitializable {
  let magic = 0xBADF00D
  let id: Int

  init() {
    id = trackedCount
    trackedCount += 1
    print("Tracked.init, \(id)")
  }

  deinit {
    assert(magic == 0xBADF00D)
    print("Tracked.deinit, \(id)")
  }

  static func new() -> Self { .init() }

  static func move(_ x: consuming Tracked) -> Tracked {
    assert(x.magic == 0xBADF00D)
    print("Tracked.move, \(x.id)")
    return x
  }
}

struct TrackedWitness: MovableWitness, NewWitness, DeinitializableWitness {
  struct Metadata: AnyMetadata {}

  func new(metadata: Metadata, into target: _Set) {
    target.withMemoryRebound(to: Tracked.self, capacity: 1) { $0.initialize(to: .init())}
  }

  func deinitialize(metadata: Metadata, sinking target: _Sink) {
    _ = target.withMemoryRebound(to: Tracked.self, capacity: 1) { $0.deinitialize(count: 1) }
  }

  func size(metadata: Metadata) -> Int {
    MemoryLayout<Tracked>.size
  }

  func alignment(metadata: Metadata) -> Int {
    MemoryLayout<Tracked>.alignment
  }

  func move(metadata: Metadata, from source: _Sink, to target: _Set) {
    assert(source.assumingMemoryBound(to: Tracked.self).pointee.magic == 0xBADF00D)
    print("Tracked move, \(source.assumingMemoryBound(to: Tracked.self).pointee.id)")
    target.assumingMemoryBound(to: Tracked.self).moveInitialize(from: source.assumingMemoryBound(to: Tracked.self), count: 1)
  }

}

func test() {
  let t = Tracked()
  g(t)

  withUnsafePointer(to: t) {
    gLowered(wv: TrackedWitness(), mv: TrackedWitness.Metadata(), $0)
  }
}

test()