//===--- ExistentialCollection.swift.gyb ----------------------*- swift -*-===//
//
// This source file is part of the Swift.org open source project
//
// Copyright (c) 2014 - 2017 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See https://swift.org/LICENSE.txt for license information
// See https://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
//
//===----------------------------------------------------------------------===//

%{

from gyb_stdlib_support import (
    TRAVERSALS,
    collectionForTraversal
)

}%

// TODO: swift-3-indexing-model: perform type erasure on the associated
// `Indices` type.

import SwiftShims

@_inlineable // FIXME(sil-serialize-all)
@_versioned
@inline(never)
internal func _abstract(
  file: StaticString = #file,
  line: UInt = #line
) -> Never {
  fatalError("Method must be overridden", file: file, line: line)
}

//===--- Iterator ---------------------------------------------------------===//
//===----------------------------------------------------------------------===//

/// A type-erased iterator of `Element`.
///
/// This iterator forwards its `next()` method to an arbitrary underlying
/// iterator having the same `Element` type, hiding the specifics of the
/// underlying `IteratorProtocol`.
@_fixed_layout
public struct AnyIterator<Element> : IteratorProtocol {
  /// Creates an iterator that wraps a base iterator but whose type depends
  /// only on the base iterator's element type.
  ///
  /// You can use `AnyIterator` to hide the type signature of a more complex
  /// iterator. For example, the `digits()` function in the following example
  /// creates an iterator over a collection that lazily maps the elements of a
  /// `CountableRange<Int>` instance to strings. Instead of returning an
  /// iterator with a type that encapsulates the implementation of the
  /// collection, the `digits()` function first wraps the iterator in an
  /// `AnyIterator` instance.
  ///
  ///     func digits() -> AnyIterator<String> {
  ///         let lazyStrings = (0..<10).lazy.map { String($0) }
  ///         let iterator:
  ///             LazyMapIterator<IndexingIterator<CountableRange<Int>>, String>
  ///             = lazyStrings.makeIterator()
  ///
  ///         return AnyIterator(iterator)
  ///     }
  ///
  /// - Parameter base: An iterator to type-erase.
  @_inlineable
  public init<I : IteratorProtocol>(_ base: I) where I.Element == Element {
    self._box = _IteratorBox(base)
  }

  /// Creates an iterator that wraps the given closure in its `next()` method.
  ///
  /// The following example creates an iterator that counts up from the initial
  /// value of an integer `x` to 15:
  ///
  ///     var x = 7
  ///     let iterator: AnyIterator<Int> = AnyIterator {
  ///         defer { x += 1 }
  ///         return x < 15 ? x : nil
  ///     }
  ///     let a = Array(iterator)
  ///     // a == [7, 8, 9, 10, 11, 12, 13, 14]
  ///
  /// - Parameter body: A closure that returns an optional element. `body` is
  ///   executed each time the `next()` method is called on the resulting
  ///   iterator.
  @_inlineable
  public init(_ body: @escaping () -> Element?) {
    self._box = _IteratorBox(_ClosureBasedIterator(body))
  }

  @_inlineable
  @_versioned
  internal init(_box: _AnyIteratorBoxBase<Element>) {
    self._box = _box
  }

  /// Advances to the next element and returns it, or `nil` if no next element
  /// exists.
  ///
  /// Once `nil` has been returned, all subsequent calls return `nil`.
  @_inlineable
  public func next() -> Element? {
    return _box.next()
  }

  @_versioned
  internal let _box: _AnyIteratorBoxBase<Element>
}

/// Every `IteratorProtocol` can also be a `Sequence`.  Note that
/// traversing the sequence consumes the iterator.
extension AnyIterator : Sequence {}

@_versioned
@_fixed_layout
internal struct _ClosureBasedIterator<Element> : IteratorProtocol {
  @_inlineable
  @_versioned
  internal init(_ body: @escaping () -> Element?) {
    self._body = body
  }
  @_inlineable
  @_versioned
  internal func next() -> Element? { return _body() }
  @_versioned
  internal let _body: () -> Element?
}

@_fixed_layout
@_versioned
internal class _AnyIteratorBoxBase<Element> : IteratorProtocol {
  @_inlineable // FIXME(sil-serialize-all)
  @_versioned // FIXME(sil-serialize-all)
  internal init() {}

  @_inlineable // FIXME(sil-serialize-all)
  @_versioned // FIXME(sil-serialize-all)
  deinit {}
  /// Advances to the next element and returns it, or `nil` if no next element
  /// exists.
  ///
  /// Once `nil` has been returned, all subsequent calls return `nil`.
  ///
  /// - Note: Subclasses must override this method.
  @_inlineable // FIXME(sil-serialize-all)
  @_versioned
  internal func next() -> Element? { _abstract() }
}

@_fixed_layout
@_versioned
internal final class _IteratorBox<
  Base : IteratorProtocol
> : _AnyIteratorBoxBase<Base.Element> {
  @_inlineable
  @_versioned
  internal init(_ base: Base) { self._base = base }
  @_inlineable // FIXME(sil-serialize-all)
  @_versioned // FIXME(sil-serialize-all)
  deinit {}
  @_inlineable
  @_versioned
  internal override func next() -> Base.Element? { return _base.next() }
  @_versioned
  internal var _base: Base
}

//===--- Sequence ---------------------------------------------------------===//
//===----------------------------------------------------------------------===//

% for Kind in ['Sequence', 'Collection', 'BidirectionalCollection', 'RandomAccessCollection']:

@_fixed_layout
@_versioned
%   if Kind == 'Sequence':
internal class _AnySequenceBox<Element>
%   elif Kind == 'Collection':
internal class _AnyCollectionBox<Element> : _AnySequenceBox<Element>
%   elif Kind == 'BidirectionalCollection':
internal class _AnyBidirectionalCollectionBox<Element>
  : _AnyCollectionBox<Element>
%   elif Kind == 'RandomAccessCollection':
internal class _AnyRandomAccessCollectionBox<Element>
  : _AnyBidirectionalCollectionBox<Element>
%   else:
%     assert False, 'Unknown kind'
%   end
{

%   if Kind == 'Sequence':
  @_inlineable // FIXME(sil-serialize-all)
  @_versioned // FIXME(sil-serialize-all)
  internal init() { }

  @_versioned
  @_inlineable
  internal func _makeIterator() -> AnyIterator<Element> { _abstract() }

  @_versioned
  @_inlineable
  internal var _underestimatedCount: Int { _abstract() }

  @_versioned
  @_inlineable
  internal func _map<T>(
    _ transform: (Element) throws -> T
  ) rethrows -> [T] {
    _abstract()
  }

  @_versioned
  @_inlineable
  internal func _filter(
    _ isIncluded: (Element) throws -> Bool
  ) rethrows -> [Element] {
    _abstract()
  }

  @_versioned
  @_inlineable
  internal func _forEach(
    _ body: (Element) throws -> Void
  ) rethrows {
    _abstract()
  }

  @_versioned
  @_inlineable
  internal func __customContainsEquatableElement(
    _ element: Element
  ) -> Bool? {
    _abstract()
  }

  @_versioned
  @_inlineable
  internal func __preprocessingPass<R>(
    _ preprocess: () throws -> R
  ) rethrows -> R? {
    _abstract()
  }

  @_versioned
  @_inlineable
  internal func __copyToContiguousArray() -> ContiguousArray<Element> {
    _abstract()
  }

  @_versioned
  @_inlineable
  internal func __copyContents(initializing buf: UnsafeMutableBufferPointer<Element>)
    -> (AnyIterator<Element>,UnsafeMutableBufferPointer<Element>.Index) {
    _abstract()
  }

%   end

% # This deinit has to be present on all the types
  @_inlineable // FIXME(sil-serialize-all)
  @_versioned // FIXME(sil-serialize-all)
  deinit {}

%   override = 'override' if Kind != 'Sequence' else ''
  @_versioned
  @_inlineable
  internal ${override} func _drop(
    while predicate: (Element) throws -> Bool
  ) rethrows -> _Any${Kind}Box<Element> {
    _abstract()
  }

  @_versioned
  @_inlineable
  internal ${override} func _dropFirst(_ n: Int) -> _Any${Kind}Box<Element> {
    _abstract()
  }

  @_versioned
  @_inlineable
  internal ${override} func _dropLast(_ n: Int) -> _Any${Kind}Box<Element> {
    _abstract()
  }

  @_versioned
  @_inlineable
  internal ${override} func _prefix(_ maxLength: Int) -> _Any${Kind}Box<Element> {
    _abstract()
  }

  @_versioned
  @_inlineable
  internal ${override} func _prefix(
    while predicate: (Element) throws -> Bool
  ) rethrows -> _Any${Kind}Box<Element> {
    _abstract()
  }

  @_versioned
  @_inlineable
  internal ${override} func _suffix(_ maxLength: Int) -> _Any${Kind}Box<Element> {
    _abstract()
  }

  @_versioned
  @_inlineable
  internal func _split(
    maxSplits: Int, omittingEmptySubsequences: Bool,
    whereSeparator isSeparator: (Element) throws -> Bool
  ) rethrows -> [Any${Kind}<Element>] {
    _abstract()
  }

%   if Kind == 'Collection':
  @_versioned
  @_inlineable
  internal subscript(i: _AnyIndexBox) -> Element { _abstract() }

  @_versioned
  @_inlineable
  internal func _index(after i: _AnyIndexBox) -> _AnyIndexBox { _abstract() }

  @_versioned
  @_inlineable
  internal func _formIndex(after i: _AnyIndexBox) { _abstract() }

  @_versioned
  @_inlineable
  internal func _index(
    _ i: _AnyIndexBox, offsetBy n: Int64
  ) -> _AnyIndexBox {
    _abstract()
  }

  @_versioned
  @_inlineable
  internal func _index(
    _ i: _AnyIndexBox, offsetBy n: Int64, limitedBy limit: _AnyIndexBox
  ) -> _AnyIndexBox? {
    _abstract()
  }

  @_versioned
  @_inlineable
  internal func _formIndex(_ i: inout _AnyIndexBox, offsetBy n: Int64) {
    _abstract()
  }

  @_versioned
  @_inlineable
  internal func _formIndex(
    _ i: inout _AnyIndexBox, offsetBy n: Int64, limitedBy limit: _AnyIndexBox
  ) -> Bool {
    _abstract()
  }

  @_versioned
  @_inlineable
  internal func _distance(
    from start: _AnyIndexBox, to end: _AnyIndexBox
  ) -> Int64 {
    _abstract()
  }

  // TODO: swift-3-indexing-model: forward the following methods.
  /*
  var _indices: Indices

  func prefix(upTo end: Index) -> SubSequence

  func suffix(from start: Index) -> SubSequence

  func prefix(through position: Index) -> SubSequence

  var isEmpty: Bool { get }
  */

  @_inlineable // FIXME(sil-serialize-all)
  @_versioned
  internal var _count: Int64 { _abstract() }

  // TODO: swift-3-indexing-model: forward the following methods.
  /*
  func _customIndexOfEquatableElement(element: Element) -> Index??
  */

  @_inlineable // FIXME(sil-serialize-all)
  @_versioned
  internal var _first: Element? { _abstract() }

  @_versioned
  @_inlineable
  internal init(
    _startIndex: _AnyIndexBox,
    endIndex: _AnyIndexBox
  ) {
    self._startIndex = _startIndex
    self._endIndex = endIndex
  }

  @_versioned
  internal let _startIndex: _AnyIndexBox

  @_versioned
  internal let _endIndex: _AnyIndexBox
%   end

%   if Kind in ['Collection', 'BidirectionalCollection', 'RandomAccessCollection']:
%     override = 'override' if Kind != 'Collection' else ''
  @_versioned
  @_inlineable
  internal ${override} subscript(
    start start: _AnyIndexBox,
    end end: _AnyIndexBox
  ) -> _Any${Kind}Box<Element> { _abstract() }
%   end

%   if Kind == 'BidirectionalCollection':
  @_versioned
  @_inlineable
  internal func _index(before i: _AnyIndexBox) -> _AnyIndexBox { _abstract() }
  @_versioned
  @_inlineable
  internal func _formIndex(before i: _AnyIndexBox) { _abstract() }
  @_versioned
  @_inlineable
  internal var _last: Element? { _abstract() }
%   end
}

% end

% for Kind in ['Sequence', 'Collection', 'BidirectionalCollection', 'RandomAccessCollection']:
%   if Kind == 'Sequence':
%     EqualAndWeakerKinds = ['Sequence']
%   elif Kind == 'Collection':
%     EqualAndWeakerKinds = ['Sequence', 'Collection']
%   elif Kind == 'BidirectionalCollection':
%     EqualAndWeakerKinds = ['Sequence', 'Collection', 'BidirectionalCollection']
%   elif Kind == 'RandomAccessCollection':
%     EqualAndWeakerKinds = ['Sequence', 'Collection', 'BidirectionalCollection', 'RandomAccessCollection']
%   else:
%     assert False, 'Unknown kind'
%   end


@_fixed_layout
@_versioned
internal final class _${Kind}Box<S : ${Kind}> : _Any${Kind}Box<S.Iterator.Element>
{
  internal typealias Element = S.Element

  @_versioned
  @_inlineable
  internal override func _makeIterator() -> AnyIterator<Element> {
    return AnyIterator(_base.makeIterator())
  }
  @_versioned
  @_inlineable
  internal override var _underestimatedCount: Int {
    return _base.underestimatedCount
  }
  @_versioned
  @_inlineable
  internal override func _map<T>(
    _ transform: (Element) throws -> T
  ) rethrows -> [T] {
    return try _base.map(transform)
  }
  @_versioned
  @_inlineable
  internal override func _filter(
    _ isIncluded: (Element) throws -> Bool
  ) rethrows -> [Element] {
    return try _base.filter(isIncluded)
  }
  @_versioned
  @_inlineable
  internal override func _forEach(
    _ body: (Element) throws -> Void
  ) rethrows {
    return try _base.forEach(body)
  }
  @_versioned
  @_inlineable
  internal override func __customContainsEquatableElement(
    _ element: Element
  ) -> Bool? {
    return _base._customContainsEquatableElement(element)
  }
  @_versioned
  @_inlineable
  internal override func __preprocessingPass<R>(
    _ preprocess: () throws -> R
  ) rethrows -> R? {
    return try _base._preprocessingPass(preprocess)
  }
  @_versioned
  @_inlineable
  internal override func __copyToContiguousArray() -> ContiguousArray<Element> {
    return _base._copyToContiguousArray()
  }
  @_versioned
  @_inlineable
  internal override func __copyContents(initializing buf: UnsafeMutableBufferPointer<Element>)
    -> (AnyIterator<Element>,UnsafeMutableBufferPointer<Element>.Index) {
    let (it,idx) = _base._copyContents(initializing: buf)
    return (AnyIterator(it),idx)
  }
  @_versioned
  @_inlineable
  internal override func _drop(
    while predicate: (Element) throws -> Bool
  ) rethrows -> _Any${Kind}Box<Element> {
    return try _${Kind}Box<S.SubSequence>(_base: _base.drop(while: predicate))
  }
  @_versioned
  @_inlineable
  internal override func _dropFirst(_ n: Int) -> _Any${Kind}Box<Element> {
    return _${Kind}Box<S.SubSequence>(_base: _base.dropFirst(n))
  }
  @_versioned
  @_inlineable
  internal override func _dropLast(_ n: Int) -> _Any${Kind}Box<Element> {
    return _${Kind}Box<S.SubSequence>(_base: _base.dropLast(n))
  }
  @_versioned
  @_inlineable
  internal override func _prefix(
    while predicate: (Element) throws -> Bool
  ) rethrows -> _Any${Kind}Box<Element> {
    return try _${Kind}Box<S.SubSequence>(_base: _base.prefix(while: predicate))
  }
  @_versioned
  @_inlineable
  internal override func _prefix(_ maxLength: Int) -> _Any${Kind}Box<Element> {
    return _${Kind}Box<S.SubSequence>(_base: _base.prefix(maxLength))
  }
  @_versioned
  @_inlineable
  internal override func _suffix(_ maxLength: Int) -> _Any${Kind}Box<Element> {
    return _${Kind}Box<S.SubSequence>(_base: _base.suffix(maxLength))
  }
%   for ResultKind in EqualAndWeakerKinds:
  @_versioned
  @_inlineable
  internal override func _split(
    maxSplits: Int, omittingEmptySubsequences: Bool,
    whereSeparator isSeparator: (Element) throws -> Bool
  ) rethrows -> [Any${ResultKind}<Element>] {
    return try _base.split(
      maxSplits: maxSplits,
      omittingEmptySubsequences: omittingEmptySubsequences,
      whereSeparator: isSeparator)
      .map {
        Any${ResultKind}(_box: _${Kind}Box<S.SubSequence>(_base: $0))
      }
  }
%   end

  @_inlineable // FIXME(sil-serialize-all)
  @_versioned // FIXME(sil-serialize-all)
  deinit {}

%   if Kind == 'Sequence':
  @_versioned
  @_inlineable
  internal init(_base: S) {
    self._base = _base
  }
%   else:
  @_inlineable
  @_versioned
  internal init(_base: S) {
    self._base = _base
    super.init(
      _startIndex: _IndexBox(_base: _base.startIndex),
      endIndex: _IndexBox(_base: _base.endIndex))
  }

  @_versioned
  @_inlineable
  internal func _unbox(
    _ position: _AnyIndexBox, file: StaticString = #file, line: UInt = #line
  ) -> S.Index {
    if let i = position._unbox() as S.Index? {
      return i
    }
    fatalError("Index type mismatch!", file: file, line: line)
  }

  @_versioned
  @_inlineable
  internal override subscript(position: _AnyIndexBox) -> Element {
    return _base[_unbox(position)]
  }

  @_versioned
  @_inlineable
  internal override subscript(start start: _AnyIndexBox, end end: _AnyIndexBox)
    -> _Any${Kind}Box<Element>
  {
    return _${Kind}Box<S.SubSequence>(_base:
      _base[_unbox(start)..<_unbox(end)]
    )
  }

  @_versioned
  @_inlineable
  internal override func _index(after position: _AnyIndexBox) -> _AnyIndexBox {
    return _IndexBox(_base: _base.index(after: _unbox(position)))
  }

  @_versioned
  @_inlineable
  internal override func _formIndex(after position: _AnyIndexBox) {
    if let p = position as? _IndexBox<S.Index> {
      return _base.formIndex(after: &p._base)
    }
    fatalError("Index type mismatch!")
  }

  @_versioned
  @_inlineable
  internal override func _index(
    _ i: _AnyIndexBox, offsetBy n: Int64
  ) -> _AnyIndexBox {
    return _IndexBox(_base: _base.index(_unbox(i), offsetBy: numericCast(n)))
  }

  @_versioned
  @_inlineable
  internal override func _index(
    _ i: _AnyIndexBox,
    offsetBy n: Int64,
    limitedBy limit: _AnyIndexBox
  ) -> _AnyIndexBox? {
    return _base.index(
        _unbox(i),
        offsetBy: numericCast(n),
        limitedBy: _unbox(limit))
      .map { _IndexBox(_base: $0) }
  }

  @_versioned
  @_inlineable
  internal override func _formIndex(
    _ i: inout _AnyIndexBox, offsetBy n: Int64
  ) {
    if let box = i as? _IndexBox<S.Index> {
      return _base.formIndex(&box._base, offsetBy: numericCast(n))
    }
    fatalError("Index type mismatch!")
  }

  @_versioned
  @_inlineable
  internal override func _formIndex(
    _ i: inout _AnyIndexBox, offsetBy n: Int64, limitedBy limit: _AnyIndexBox
  ) -> Bool {
    if let box = i as? _IndexBox<S.Index> {
      return _base.formIndex(
        &box._base,
        offsetBy: numericCast(n),
        limitedBy: _unbox(limit))
    }
    fatalError("Index type mismatch!")
  }

  @_versioned
  @_inlineable
  internal override func _distance(
    from start: _AnyIndexBox,
    to end: _AnyIndexBox
  ) -> Int64 {
    return numericCast(_base.distance(from: _unbox(start), to: _unbox(end)))
  }

  @_versioned
  @_inlineable
  internal override var _count: Int64 {
    return numericCast(_base.count)
  }

  @_versioned
  @_inlineable
  internal override var _first: Element? {
    return _base.first
  }

%     if Kind in ['BidirectionalCollection', 'RandomAccessCollection']:
  @_versioned
  @_inlineable
  internal override func _index(before position: _AnyIndexBox) -> _AnyIndexBox {
    return _IndexBox(_base: _base.index(before: _unbox(position)))
  }

  @_versioned
  @_inlineable
  internal override func _formIndex(before position: _AnyIndexBox) {
    if let p = position as? _IndexBox<S.Index> {
      return _base.formIndex(before: &p._base)
    }
    fatalError("Index type mismatch!")
  }

  @_versioned
  @_inlineable
  internal override var _last: Element? {
    return _base.last
  }
%     end

%   end
  @_versioned
  internal var _base: S
}
% end

@_versioned
@_fixed_layout
internal struct _ClosureBasedSequence<Iterator : IteratorProtocol>
  : Sequence {

  @_versioned
  @_inlineable
  internal init(_ makeUnderlyingIterator: @escaping () -> Iterator) {
    self._makeUnderlyingIterator = makeUnderlyingIterator
  }

  @_versioned
  @_inlineable
  internal func makeIterator() -> Iterator {
    return _makeUnderlyingIterator()
  }

  @_versioned
  internal var _makeUnderlyingIterator: () -> Iterator
}

/// A type-erased sequence.
///
/// An instance of `AnySequence` forwards its operations to an underlying base
/// sequence having the same `Element` type, hiding the specifics of the
/// underlying sequence.
//@_versioned
@_fixed_layout
public struct AnySequence<Element> : Sequence {
  /// Creates a new sequence that wraps and forwards operations to `base`.
  @_inlineable
  public init<S : Sequence>(_ base: S)
    where
    S.Element == Element {
    self._box = _SequenceBox(_base: base)
  }

  /// Creates a sequence whose `makeIterator()` method forwards to
  /// `makeUnderlyingIterator`.
  @_inlineable
  public init<I : IteratorProtocol>(
    _ makeUnderlyingIterator: @escaping () -> I
  ) where I.Element == Element {
    self.init(_ClosureBasedSequence(makeUnderlyingIterator))
  }

  public typealias Iterator = AnyIterator<Element>

  @_versioned
  @_inlineable
  internal init(_box: _AnySequenceBox<Element>) {
    self._box = _box
  }

  @_versioned
  internal let _box: _AnySequenceBox<Element>
}

% for Kind in ['Sequence', 'Collection', 'BidirectionalCollection', 'RandomAccessCollection']:
extension Any${Kind} {
%   if Kind == 'Sequence':
  /// Returns an iterator over the elements of this sequence.
%   else:
  /// Returns an iterator over the elements of this collection.
%   end
  @_inlineable
  public func makeIterator() -> Iterator {
    return _box._makeIterator()
  }

  @_inlineable
  public var underestimatedCount: Int {
    return _box._underestimatedCount
  }

  @_inlineable
  public func map<T>(
    _ transform: (Element) throws -> T
  ) rethrows -> [T] {
    return try _box._map(transform)
  }

  @_inlineable
  public func filter(
    _ isIncluded: (Element) throws -> Bool
  ) rethrows -> [Element] {
    return try _box._filter(isIncluded)
  }

  @_inlineable
  public func forEach(
    _ body: (Element) throws -> Void
  ) rethrows {
    return try _box._forEach(body)
  }

  @_inlineable
  public func drop(
    while predicate: (Element) throws -> Bool
  ) rethrows -> Any${Kind}<Element> {
    return try Any${Kind}(_box: _box._drop(while: predicate))
  }

  @_inlineable
  public func dropFirst(_ n: Int) -> Any${Kind}<Element> {
    return Any${Kind}(_box: _box._dropFirst(n))
  }

  @_inlineable
  public func dropLast(_ n: Int) -> Any${Kind}<Element> {
    return Any${Kind}(_box: _box._dropLast(n))
  }

  @_inlineable
  public func prefix(
    while predicate: (Element) throws -> Bool
  ) rethrows -> Any${Kind}<Element> {
    return try Any${Kind}(_box: _box._prefix(while: predicate))
  }

  @_inlineable
  public func prefix(_ maxLength: Int) -> Any${Kind}<Element> {
    return Any${Kind}(_box: _box._prefix(maxLength))
  }

  @_inlineable
  public func suffix(_ maxLength: Int) -> Any${Kind}<Element> {
    return Any${Kind}(_box: _box._suffix(maxLength))
  }

  @_inlineable
  public func split(
    maxSplits: Int = Int.max,
    omittingEmptySubsequences: Bool = true,
    whereSeparator isSeparator: (Element) throws -> Bool
  ) rethrows -> [Any${Kind}<Element>] {
    return try _box._split(
      maxSplits: maxSplits,
      omittingEmptySubsequences: omittingEmptySubsequences,
      whereSeparator: isSeparator)
  }

  @_inlineable
  public func _customContainsEquatableElement(
    _ element: Element
  ) -> Bool? {
    return _box.__customContainsEquatableElement(element)
  }

  @_inlineable
  public func _preprocessingPass<R>(
    _ preprocess: () throws -> R
  ) rethrows -> R? {
    return try _box.__preprocessingPass(preprocess)
  }

  @_inlineable
  public func _copyToContiguousArray() -> ContiguousArray<Element> {
    return self._box.__copyToContiguousArray()
  }

  @_inlineable
  public func _copyContents(initializing buf: UnsafeMutableBufferPointer<Element>)
  -> (AnyIterator<Element>,UnsafeMutableBufferPointer<Element>.Index) {
    let (it,idx) = _box.__copyContents(initializing: buf)
    return (AnyIterator(it),idx)
  }
}
% end

//===--- Index ------------------------------------------------------------===//
//===----------------------------------------------------------------------===//

@_versioned
internal protocol _AnyIndexBox : class {
  var _typeID: ObjectIdentifier { get }

  func _unbox<T : Comparable>() -> T?

  func _isEqual(to rhs: _AnyIndexBox) -> Bool

  func _isLess(than rhs: _AnyIndexBox) -> Bool
}

@_fixed_layout
@_versioned
internal final class _IndexBox<
  BaseIndex : Comparable
> : _AnyIndexBox {
  @_versioned
  internal var _base: BaseIndex

  @_versioned
  @_inlineable
  internal init(_base: BaseIndex) {
    self._base = _base
  }

  @_versioned
  @_inlineable
  internal func _unsafeUnbox(_ other: _AnyIndexBox) -> BaseIndex {
    return unsafeDowncast(other, to: _IndexBox.self)._base
  }

  @_versioned
  @_inlineable
  internal var _typeID: ObjectIdentifier {
    return ObjectIdentifier(type(of: self))
  }

  @_versioned
  @_inlineable
  internal func _unbox<T : Comparable>() -> T? {
    return (self as _AnyIndexBox as? _IndexBox<T>)?._base
  }

  @_versioned
  @_inlineable
  internal func _isEqual(to rhs: _AnyIndexBox) -> Bool {
    return _base == _unsafeUnbox(rhs)
  }

  @_versioned
  @_inlineable
  internal func _isLess(than rhs: _AnyIndexBox) -> Bool {
    return _base < _unsafeUnbox(rhs)
  }
}

/// A wrapper over an underlying index that hides the specific underlying type.
@_fixed_layout
public struct AnyIndex {
  /// Creates a new index wrapping `base`.
  @_inlineable
  public init<BaseIndex : Comparable>(_ base: BaseIndex) {
    self._box = _IndexBox(_base: base)
  }

  @_versioned
  @_inlineable
  internal init(_box: _AnyIndexBox) {
    self._box = _box
  }

  @_versioned
  @_inlineable
  internal var _typeID: ObjectIdentifier {
    return _box._typeID
  }

  @_versioned
  internal var _box: _AnyIndexBox
}

extension AnyIndex : Comparable {
  /// Returns a Boolean value indicating whether two indices wrap equal
  /// underlying indices.
  ///
  /// The types of the two underlying indices must be identical.
  ///
  /// - Parameters:
  ///   - lhs: An index to compare.
  ///   - rhs: Another index to compare.
  @_inlineable
  public static func == (lhs: AnyIndex, rhs: AnyIndex) -> Bool {
    _precondition(lhs._typeID == rhs._typeID, "Base index types differ")
    return lhs._box._isEqual(to: rhs._box)
  }

  /// Returns a Boolean value indicating whether the first argument represents a
  /// position before the second argument.
  ///
  /// The types of the two underlying indices must be identical.
  ///
  /// - Parameters:
  ///   - lhs: An index to compare.
  ///   - rhs: Another index to compare.
  @_inlineable
  public static func < (lhs: AnyIndex, rhs: AnyIndex) -> Bool {
    _precondition(lhs._typeID == rhs._typeID, "Base index types differ")
    return lhs._box._isLess(than: rhs._box)
  }
}

//===--- Collections ------------------------------------------------------===//
//===----------------------------------------------------------------------===//

public // @testable
protocol _AnyCollectionProtocol : Collection {
  /// Identifies the underlying collection stored by `self`. Instances
  /// copied or upgraded/downgraded from one another have the same `_boxID`.
  var _boxID: ObjectIdentifier { get }
}

% for (ti, Traversal) in enumerate(TRAVERSALS):
%   SelfProtocol = collectionForTraversal(Traversal)
%   Self = 'Any' + SelfProtocol
/// A type-erased wrapper over any collection with indices that
/// support ${Traversal.lower().replace('omacc', 'om acc')} traversal.
///
/// An `${Self}` instance forwards its operations to a base collection having the
/// same `Element` type, hiding the specifics of the underlying
/// collection.
@_fixed_layout
public struct ${Self}<Element>
  : _AnyCollectionProtocol, ${SelfProtocol} {

  public typealias Indices
    = Default${Traversal.replace('Forward', '')}Indices<${Self}>

  public typealias Iterator = AnyIterator<Element>

  @_versioned
  @_inlineable
  internal init(_box: _${Self}Box<Element>) {
    self._box = _box
  }

%   for SubTraversal in TRAVERSALS[ti:]:
%     SubProtocol = collectionForTraversal(SubTraversal)
  /// Creates a type-erased collection that wraps the given collection.
  ///
  /// - Parameter base: The collection to wrap.
  ///
  /// - Complexity: O(1).
  @_inlineable
  public init<C : ${SubProtocol}>(_ base: C)
  where
    C.Element == Element
     {
    // Traversal: ${Traversal}
    // SubTraversal: ${SubTraversal}
    self._box = _${SubProtocol}Box<C>(
      _base: base)
  }

  /// Creates an `${Self}` having the same underlying collection as `other`.
  ///
  /// - Complexity: O(1)
  @_inlineable
  public init(
    _ other: Any${SubProtocol}<Element>
  ) {
    self._box = other._box
  }
%   end

%   for SuperTraversal in TRAVERSALS[:ti]:
  /// Creates an `${Self}` having the same underlying collection as `other`.
  ///
  /// If the underlying collection stored by `other` does not satisfy
  /// `${SelfProtocol}`, the result is `nil`.
  ///
  /// - Complexity: O(1)
  @_inlineable
  public init?(
    _ other: Any${collectionForTraversal(SuperTraversal)}<Element>
  ) {
    guard let box =
      other._box as? _${Self}Box<Element> else {
      return nil
    }
    self._box = box
  }
%   end

  public typealias Index = AnyIndex
  public typealias IndexDistance = Int64

  /// The position of the first element in a non-empty collection.
  ///
  /// In an empty collection, `startIndex == endIndex`.
  @_inlineable
  public var startIndex: AnyIndex {
    return AnyIndex(_box: _box._startIndex)
  }

  /// The collection's "past the end" position---that is, the position one
  /// greater than the last valid subscript argument.
  ///
  /// `endIndex` is always reachable from `startIndex` by zero or more
  /// applications of `index(after:)`.
  @_inlineable
  public var endIndex: AnyIndex {
    return AnyIndex(_box: _box._endIndex)
  }

  /// Accesses the element indicated by `position`.
  ///
  /// - Precondition: `position` indicates a valid position in `self` and
  ///   `position != endIndex`.
  @_inlineable
  public subscript(position: AnyIndex) -> Element {
    return _box[position._box]
  }

  @_inlineable
  public subscript(bounds: Range<AnyIndex>) -> ${Self}<Element> {
    return ${Self}(_box:
      _box[start: bounds.lowerBound._box, end: bounds.upperBound._box])
  }

  @_inlineable
  public func _failEarlyRangeCheck(_ index: AnyIndex, bounds: Range<AnyIndex>) {
    // Do nothing.  Doing a range check would involve unboxing indices,
    // performing dynamic dispatch etc.  This seems to be too costly for a fast
    // range check for QoI purposes.
  }

  @_inlineable
  public func _failEarlyRangeCheck(_ range: Range<Index>, bounds: Range<Index>) {
    // Do nothing.  Doing a range check would involve unboxing indices,
    // performing dynamic dispatch etc.  This seems to be too costly for a fast
    // range check for QoI purposes.
  }

  @_inlineable
  public func index(after i: AnyIndex) -> AnyIndex {
    return AnyIndex(_box: _box._index(after: i._box))
  }

  @_inlineable
  public func formIndex(after i: inout AnyIndex) {
    if _isUnique(&i._box) {
      _box._formIndex(after: i._box)
    }
    else {
      i = index(after: i)
    }
  }

  @_inlineable
  public func index(_ i: AnyIndex, offsetBy n: Int64) -> AnyIndex {
    return AnyIndex(_box: _box._index(i._box, offsetBy: n))
  }

  @_inlineable
  public func index(
    _ i: AnyIndex,
    offsetBy n: Int64,
    limitedBy limit: AnyIndex
  ) -> AnyIndex? {
    return _box._index(i._box, offsetBy: n, limitedBy: limit._box)
      .map { AnyIndex(_box:$0) }
  }

  @_inlineable
  public func formIndex(_ i: inout AnyIndex, offsetBy n: Int64) {
    if _isUnique(&i._box) {
      return _box._formIndex(&i._box, offsetBy: n)
    } else {
      i = index(i, offsetBy: n)
    }
  }

  @_inlineable
  public func formIndex(
    _ i: inout AnyIndex,
    offsetBy n: Int64,
    limitedBy limit: AnyIndex
  ) -> Bool {
    if _isUnique(&i._box) {
      return _box._formIndex(&i._box, offsetBy: n, limitedBy: limit._box)
    }
    if let advanced = index(i, offsetBy: n, limitedBy: limit) {
      i = advanced
      return true
    }
    i = limit
    return false
  }

  @_inlineable
  public func distance(from start: AnyIndex, to end: AnyIndex) -> Int64 {
    return _box._distance(from: start._box, to: end._box)
  }

  /// The number of elements.
  ///
% if Traversal != 'RandomAccess':
  /// To check whether a collection is empty, use its `isEmpty` property
  /// instead of comparing `count` to zero. Calculating `count` can be an O(*n*)
  /// operation.
  ///
% end
  /// - Complexity: ${'O(1)' if Traversal == 'RandomAccess' else 'O(*n*)'}
  @_inlineable
  public var count: Int64 {
    return _box._count
  }

  @_inlineable
  public var first: Element? {
    return _box._first
  }

%   if Traversal == 'Bidirectional' or Traversal == 'RandomAccess':
  @_inlineable
  public func index(before i: AnyIndex) -> AnyIndex {
    return AnyIndex(_box: _box._index(before: i._box))
  }

  @_inlineable
  public func formIndex(before i: inout AnyIndex) {
    if _isUnique(&i._box) {
      _box._formIndex(before: i._box)
    }
    else {
      i = index(before: i)
    }
  }

  @_inlineable
  public var last: Element? {
    return _box._last
  }
%   end

  /// Uniquely identifies the stored underlying collection.
  @_inlineable
  public // Due to language limitations only
  var _boxID: ObjectIdentifier {
    return ObjectIdentifier(_box)
  }

  @_versioned
  internal let _box: _${Self}Box<Element>
}
% end