Avoiding Recursive Constraints

NoRecursiveConstraint.swift

// Everything but the slicing-related requirements of Collection
protocol CollectionCore {

  associatedtype Element
  associatedtype Index

  func startIndex() -> Index
  func endIndex() -> Index
  func index(after i: Index) -> Index

  subscript(_ i: Index) -> Element { get }

  // A type that is wrapped to get the result of slicing
  associatedtype SliceCore
    = DefaultSliceCore<Self> // Default makes new Collections easier to define.

  // Not for user consumption; provides the implementation of slicing
  subscript(sliceCore start: Index, _ end: Index) -> SliceCore { get }
}

// Adds slicing support requirements to CollectionCore.
protocol Collection: CollectionCore
  where SliceCore: CollectionCore,
        SliceCore.SliceCore == SliceCore,
        SliceCore.Element == Self.Element,
        SliceCore.Index == Self.Index
{}

// Provide the user-consumed slicing operation.
extension Collection {

  typealias SubSequence = Slice<SliceCore>

  subscript(_ start: Index, _ end: Index) -> SubSequence {
    _read {
      yield SubSequence(core: self[sliceCore: start, end])
    }
  }

}

// Turns Base's SliceCore into a full Collection.
struct Slice<Core: CollectionCore>: Collection
  where Core.SliceCore == Core
{

  var core: Core

  // Prevents buildup of Slice<...> nesting.
  typealias SliceCore = Core

  // Forward CollectionCore requirements to core
  typealias Element = SliceCore.Element
  typealias Index = SliceCore.Index
  func startIndex() -> Index { core.startIndex() }
  func endIndex() -> Index { core.endIndex() }
  func index(after i: Index) -> Index {  core.index(after: i) }
  subscript(_ i: Index) -> Element { _read { yield core[i] } }

  subscript(sliceCore start: Index, _ end: Index) -> SliceCore {
    _read { yield core[sliceCore: start, end] }
  }

}

extension Slice: Equatable where Core: Equatable {}

//
// Conveniences so new Collections don't need to define their own slicing support.
//

extension Collection where SliceCore == DefaultSliceCore<Self> {

  subscript(sliceCore start: Index, _ end: Index) -> SliceCore {
    _read {
      yield DefaultSliceCore(base: self, start: start, end: end)
    }
  }

}

struct DefaultSliceCore<Base: CollectionCore>: CollectionCore  {

  let base: Base
  var start: Index
  var end: Index

  typealias Element = Base.Element
  typealias Index = Base.Index

  func startIndex() -> Index { start }
  func endIndex() -> Index { end }
  func index(after i: Index) -> Index { base.index(after: i) }

  subscript(_ i: Index) -> Element { _read { yield base[i] } }

  subscript(sliceCore start: Index, _ end: Index) -> Self {
    _read { yield Self(base: self.base, start: start, end: end) }
  }

}

extension DefaultSliceCore: Equatable where Base: Equatable, Index: Equatable {}

// ========= Demonstrations ============

// A simple collection using default slicing
struct Basic: Collection, Equatable {

  typealias Element = String
  typealias Index = Int

  func startIndex() -> Index { 0 }
  func endIndex() -> Index { 10 }
  func index(after i: Index) -> Index { i + 1 }

  subscript(_ i: Index) -> Element { String(i) }

}

let basic = Basic()

assert(
  basic[3, 5] ==
    Basic.SubSequence(
      core: DefaultSliceCore(base: basic, start: 3, end: 5)))

assert(basic[3, 5][3, 5] == basic[3, 5])

// A collection with a custom slice representation.
struct CustomSliced: Collection, Equatable {

  typealias Element = UInt8
  typealias Index = Int

  func startIndex() -> Index { 0 }
  func endIndex() -> Index { 10 }
  func index(after i: Index) -> Index { i + 1 }

  subscript(_ i: Index) -> Element { UInt8(i) }
  subscript(sliceCore start: Index, _ end: Index) -> SliceCore {
    SliceCore(start: start, end: end)
  }

  struct SliceCore: Collection, Equatable {

    typealias SliceCore = Self
    typealias Element = UInt8
    typealias Index = Int

    var start, end: Int

    func startIndex() -> Index { start }
    func endIndex() -> Index { end }
    func index(after i: Index) -> Index { i + 1 }

    subscript(_ i: Index) -> Element { UInt8(i) }

    subscript(sliceCore start: Index, _ end: Index) -> SliceCore {
      Self(start: start, end: end)
    }
  }

}

let customSliced = CustomSliced()

assert(
  customSliced[3, 5] ==
    CustomSliced.SubSequence(core: .init(start: 3, end: 5)))

assert(customSliced[3, 5][3, 5] == customSliced[3, 5])

NoRecursiveConstraints2.swift

// Very similar to the above, but in that version, `Slice<T>` was parameterized on some
// `SliceCore` type which would often be something like `DefaultSliceCore<SomeCollection>`, so
// slicing an `Array<Int>` would  give you `Slice<DefaultSliceCore<Array<Int>>>`.  In this
// version we get `Slice<Array<Int>>` which is more manageable for users.

// Everything but the slicing-related requirements of Collection
protocol CollectionCore {

  associatedtype Element
  associatedtype Index

  func startIndex() -> Index
  func endIndex() -> Index
  func index(after i: Index) -> Index

  subscript(_ i: Index) -> Element { get }

  // A type that is wrapped to get the result of slicing
  associatedtype SliceCore
    = DefaultSliceCore<Self> // Default makes new Collections easier to define.

  // Not for user consumption; provides the implementation of slicing
  subscript(sliceCore start: Index, _ end: Index) -> SliceCore { get }
}

// Adds slicing support requirements to CollectionCore.
protocol Collection: CollectionCore
  where SliceCore: CollectionCore,
        SliceCore.SliceCore == SliceCore
{

  // `Whole`: `Self == `Slice<W> ? W : Self`
  associatedtype Whole: CollectionCore = Self
    where Whole.SliceCore == SliceCore,
          Whole.Element == SliceCore.Element,
          Whole.Index == SliceCore.Index

}

// Provide the user-consumed slicing operation.
extension Collection {

  subscript(_ start: Index, _ end: Index) -> Slice<Whole> {
    _read {
      yield Slice(core: self[sliceCore: start, end])
    }
  }

}

// Wraps W's SliceCore into as a full Collection.
struct Slice<W: CollectionCore>: Collection
  where W.SliceCore: CollectionCore,
        W.SliceCore.SliceCore == W.SliceCore,
        W.SliceCore.Index == W.Index,
        W.SliceCore.Element == W.Element
{

  typealias Whole = W
  var core: SliceCore

  // Prevents buildup of Slice<...> nesting.
  typealias SliceCore = Whole.SliceCore

  // Forward CollectionCore requirements to core
  typealias Element = SliceCore.Element
  typealias Index = SliceCore.Index
  func startIndex() -> Index { core.startIndex() }
  func endIndex() -> Index { core.endIndex() }
  func index(after i: Index) -> Index {  core.index(after: i) }
  subscript(_ i: Index) -> Element { _read { yield core[i] } }

  subscript(sliceCore start: Index, _ end: Index) -> SliceCore {
    _read { yield core[sliceCore: start, end] }
  }

}

extension Slice: Equatable where Whole.SliceCore: Equatable {}

//
// Conveniences so new Collections don't need to define their own slicing support.
//

extension Collection where SliceCore == DefaultSliceCore<Self> {

  subscript(sliceCore start: Index, _ end: Index) -> SliceCore {
    _read {
      yield DefaultSliceCore(base: self, start: start, end: end)
    }
  }

}

struct DefaultSliceCore<Base: CollectionCore>: CollectionCore  {

  let base: Base
  var start: Index
  var end: Index

  typealias Element = Base.Element
  typealias Index = Base.Index

  func startIndex() -> Index { start }
  func endIndex() -> Index { end }
  func index(after i: Index) -> Index { base.index(after: i) }

  subscript(_ i: Index) -> Element { _read { yield base[i] } }

  subscript(sliceCore start: Index, _ end: Index) -> Self {
    _read { yield Self(base: self.base, start: start, end: end) }
  }

}

extension DefaultSliceCore: Equatable where Base: Equatable, Index: Equatable {}

// ========= Demonstrations ============

// A simple collection using default slicing
struct Basic: Collection, Equatable {

  typealias Element = String
  typealias Index = Int

  func startIndex() -> Index { 0 }
  func endIndex() -> Index { 10 }
  func index(after i: Index) -> Index { i + 1 }

  subscript(_ i: Index) -> Element { String(i) }

}

let basic = Basic()

assert(
  basic[3, 5] ==
    Slice<Basic>(
      core: DefaultSliceCore(base: basic, start: 3, end: 5)))

assert(basic[3, 5][3, 5] == basic[3, 5])

// A collection with a custom slice representation.
struct CustomSliced: Collection, Equatable {

  typealias Element = UInt8
  typealias Index = Int

  func startIndex() -> Index { 0 }
  func endIndex() -> Index { 10 }
  func index(after i: Index) -> Index { i + 1 }

  subscript(_ i: Index) -> Element { UInt8(i) }
  subscript(sliceCore start: Index, _ end: Index) -> SliceCore {
    SliceCore(start: start, end: end)
  }

  struct SliceCore: Collection, Equatable {

    typealias SliceCore = Self
    typealias Element = UInt8
    typealias Index = Int

    var start, end: Int

    func startIndex() -> Index { start }
    func endIndex() -> Index { end }
    func index(after i: Index) -> Index { i + 1 }

    subscript(_ i: Index) -> Element { UInt8(i) }

    subscript(sliceCore start: Index, _ end: Index) -> SliceCore {
      Self(start: start, end: end)
    }
  }

}

let customSliced = CustomSliced()

assert(
  customSliced[3, 5] ==
    Slice<CustomSliced>(core: .init(start: 3, end: 5)))

assert(customSliced[3, 5][3, 5] == customSliced[3, 5])

NoRecursiveConstraints3.swift

// Very similar to the above, but adheres to the rule (not currently
// implemented in Swift) that:
//
//   A typealias satisfying an associated type requirement X is cannot
//   be defined in terms of a type where Self is generically
//   constrained to include an associated type requirement X.
//
// This rule prevents a class of errors where specific instances of
// generic types can have unexpectedly recursive definitions that
// should make them illegal, for example:
//
//     protocol S {
//       associatedtype I
//     }
//     
//     struct I0<S0: S> {
//       var x: S0.I
//     }
//     
//     struct S1: S {
//       typealias I = I0<Self> // I contains a stored property of type I
//     }
//     

// Everything but the slicing-related requirements of Collection
protocol CollectionCoreBase {

  associatedtype Element
  associatedtype Index

  func startIndex() -> Index
  func endIndex() -> Index
  func index(after i: Index) -> Index

  subscript(_ i: Index) -> Element { get }

}

// Everything but the publicly-consumed slicing-related requirements of Collection
protocol CollectionCore: CollectionCoreBase {

  // A type that is wrapped to get the result of slicing
  associatedtype SliceCore
    = DefaultSliceCore<Self> // Default makes new Collections easier to define.

  // Not for user consumption; provides the implementation of slicing
  subscript(sliceCore start: Index, _ end: Index) -> SliceCore { get }
}

// Adds slicing support requirements to CollectionCore.
protocol Collection: CollectionCore
  where SliceCore: CollectionCore,
        SliceCore.SliceCore == SliceCore
{

  // `Whole`: `Self == `Slice<W> ? W : Self`
  associatedtype Whole: CollectionCore = Self
    where Whole.SliceCore == SliceCore,
          Whole.Element == SliceCore.Element,
          Whole.Index == SliceCore.Index

}

// Provide the user-consumed slicing operation.
extension Collection {

  subscript(_ start: Index, _ end: Index) -> Slice<Whole> {
    _read {
      yield Slice(core: self[sliceCore: start, end])
    }
  }

}

// Wraps W's SliceCore into as a full Collection.
struct Slice<W: CollectionCore>: Collection
  where W.SliceCore: CollectionCore,
        W.SliceCore.SliceCore == W.SliceCore,
        W.SliceCore.Index == W.Index,
        W.SliceCore.Element == W.Element
{

  typealias Whole = W
  var core: SliceCore

  // Prevents buildup of Slice<...> nesting.
  typealias SliceCore = Whole.SliceCore

  // Forward CollectionCore requirements to core
  typealias Element = SliceCore.Element
  typealias Index = SliceCore.Index
  func startIndex() -> Index { core.startIndex() }
  func endIndex() -> Index { core.endIndex() }
  func index(after i: Index) -> Index {  core.index(after: i) }
  subscript(_ i: Index) -> Element { _read { yield core[i] } }

  subscript(sliceCore start: Index, _ end: Index) -> SliceCore {
    _read { yield core[sliceCore: start, end] }
  }

}

extension Slice: Equatable where Whole.SliceCore: Equatable {}

//
// Conveniences so new Collections don't need to define their own slicing support.
//

extension Collection where SliceCore == DefaultSliceCore<Self> {

  subscript(sliceCore start: Index, _ end: Index) -> SliceCore {
    _read {
      yield DefaultSliceCore(base: self, start: start, end: end)
    }
  }

}

struct DefaultSliceCore<Base: CollectionCoreBase>: CollectionCore  {

  let base: Base
  var start: Index
  var end: Index

  typealias Element = Base.Element
  typealias Index = Base.Index

  func startIndex() -> Index { start }
  func endIndex() -> Index { end }
  func index(after i: Index) -> Index { base.index(after: i) }

  subscript(_ i: Index) -> Element { _read { yield base[i] } }

  subscript(sliceCore start: Index, _ end: Index) -> Self {
    _read { yield Self(base: self.base, start: start, end: end) }
  }

}

extension DefaultSliceCore: Equatable where Base: Equatable, Index: Equatable {}

// ========= Demonstrations ============

// A simple collection using default slicing
struct Basic: Collection, Equatable {

  typealias Element = String
  typealias Index = Int

  func startIndex() -> Index { 0 }
  func endIndex() -> Index { 10 }
  func index(after i: Index) -> Index { i + 1 }

  subscript(_ i: Index) -> Element { String(i) }

}

let basic = Basic()

assert(
  basic[3, 5] ==
    Slice<Basic>(
      core: DefaultSliceCore(base: basic, start: 3, end: 5)))

assert(basic[3, 5][3, 5] == basic[3, 5])

// A collection with a custom slice representation.
struct CustomSliced: Collection, Equatable {

  typealias Element = UInt8
  typealias Index = Int

  func startIndex() -> Index { 0 }
  func endIndex() -> Index { 10 }
  func index(after i: Index) -> Index { i + 1 }

  subscript(_ i: Index) -> Element { UInt8(i) }
  subscript(sliceCore start: Index, _ end: Index) -> SliceCore {
    SliceCore(start: start, end: end)
  }

  struct SliceCore: Collection, Equatable {

    typealias SliceCore = Self
    typealias Element = UInt8
    typealias Index = Int

    var start, end: Int

    func startIndex() -> Index { start }
    func endIndex() -> Index { end }
    func index(after i: Index) -> Index { i + 1 }

    subscript(_ i: Index) -> Element { UInt8(i) }

    subscript(sliceCore start: Index, _ end: Index) -> SliceCore {
      Self(start: start, end: end)
    }
  }

}

let customSliced = CustomSliced()

assert(
  customSliced[3, 5] ==
    Slice<CustomSliced>(core: .init(start: 3, end: 5)))

assert(customSliced[3, 5][3, 5] == customSliced[3, 5])