(https://bugs.swift.org/browse/SR-12692) Demonstrates that the current model for protocol extensions and conditional conformances is… unreasonable.

ASimplerExample.swift

extension Sequence {
  var array: Array<Element> {
    print("preallocating", self.underestimatedCount)
    return Array(self)
  }
}

_ = Array(0..<1000).reversed().array                 // preallocating 1000
_ = repeatElement(1..<10, count: 200).joined().array // preallocating 0

ConditionalConformanceOfGenerics.swift

/// The total number of single-hop index steps made in our test collections.
var totalSteps = 0

/// A collection that tracks the number of single-hop index steps executed.
struct CountSteps0 : RandomAccessCollection {
  init(count: Int) { self.count = count }
  var count: Int

  var startIndex: Int { 0 }
  var endIndex: Int { count }
  func index(after i: Int) -> Int { 
    totalSteps += 1
    return i + 1
  }
  func index(before i: Int) -> Int { 
    totalSteps += 1
    return i - 1
  }
  subscript(i: Int) -> Int { return i }
}

/// A collection that is conditionally Random Access 
struct CountSteps1<T: Collection> : Collection {
  init(count: Int) { self.count = count }
  var count: Int

  var startIndex: Int { 0 }
  var endIndex: Int { count }
  func index(after i: Int) -> Int { 
    totalSteps += 1
    return i + 1
  }
  subscript(i: Int) -> Int { return i }
}

extension CountSteps1
  : RandomAccessCollection, BidirectionalCollection 
     where T : RandomAccessCollection 
{
  func index(before i: Int) -> Int { 
    totalSteps += 1
    return i - 1
  }
  // Even if you don't take advantage of the easy defaults where Index == Int,
  // which you typically won't get because your Index will be based on T's index
  // type, it's broken.  You can see this by uncommenting the two other
  // requirements you're supposed to implement if your collection is random
  // access.
  /*
  func index(_ i: Int, offsetBy d: Int) -> Int {
    return i + d
  }
  func distance(from i: Int, to j: Int) -> Int {
    return j - i
  }
  */
}

extension Collection {
  /// Returns the 500th index position if it exists, or `nil` otherwise.
  ///
  /// Complexity: O(1) if `Self` conforms to `RandomAccessCollection`, O(N)
  /// otherwise.
  func midPoint() -> Index { 
    index(startIndex, offsetBy: count / 2, limitedBy: endIndex)!
  }
}

// CountSteps0 picks up a number of defaults designed to make it easy to create
// `RandomAccessCollection`s.
let x0 = CountSteps0(count: 900)
_ = x0.midPoint()
print("steps:", totalSteps) // 0

/// CountSteps1 doesn't pick up any RandomAccessCollection default
/// implementations, so the complexity guarantee of the `midPoint()` algorithm
/// is broken.  This is the case even if we fill in all the requirements you're
/// supposed to have to include in a model of `RandomAccessCollection`
/// (uncomment above).
let x1 = CountSteps1<Range<Int>>(count: 900)
_ = x1.midPoint()
print("steps:", totalSteps) // 450

// Prove that x1 really is a RandomAccessCollection
extension RandomAccessCollection {
  var isRandomAccess: Bool { true }
}

extension Collection {
  /// Returns `endIndex` offset by `n` positions.
  ///
  /// - Requires: if `Self` does not conform to `BidirectionalCollection`, `n ==
  ///   0`.
  func offsetEnd(by n: Int) -> Index {
    index(endIndex, offsetBy: n)
  }
}
print(x1.isRandomAccess)
_ = x1.offsetEnd(by: -1) // TRAP

Shouldn't it be _ = x0.midPoint() in line 72? But that doesn't change the fact that conditional conformances indeed appear broken for generic algorithms...

Yes, thanks! Good thing I was reviewing this because GitHub doesn't send out notifications for gist comments <- Apparently they fixed that!

In ConditionalConformanceOfGenerics, can the problem be fixed by adding the following extension in RandomAccessCollection to shadow the extension in Collection?

extension RandomAccessCollection {
  func midPoint() -> Index {
    index(startIndex, offsetBy: count / 2, limitedBy: endIndex)!
  }
} 

Is that correct? And, does it adequately address the underlying issue that this example seeks to model?

@mattrips, Not sure what you had in mind with that, but it changes neither the trap nor the taking of too many steps.

Just to see if I'm getting the point of the ConditionalConformanceOfGenerics.swift example.

So, while this example can be "fixed", ie fixed as in getting it to print:

steps: 0
steps: 0
true

by making some seemingly relevant modifications to the code, eg:

1. Uncomment:

  func index(_ i: Int, offsetBy d: Int) -> Int {
    return i + d
  }
  func distance(from i: Int, to j: Int) -> Int {
    return j - i
  }

2. Add:

extension RandomAccessCollection {
  func midPoint() -> Index {
    index(startIndex, offsetBy: count / 2, limitedBy: endIndex)!
  }
  func offsetEnd(by n: Int) -> Index { return index(endIndex, offsetBy: n) }
}

3. Run, tadaa!

this is not fixing the underlying/general problem.

This "solution" is just treating some particular symptoms exposed by this specific example, and it does so by repeating code (ie giving up code reuse / the point of generic programming).

Right?

@jens-bc right.