//===----------------------------------------------------------------------===//
//
// This source file is part of the Swift.org open source project
//
// Copyright (c) 2014 - 2020 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
//
//===----------------------------------------------------------------------===//

import StdlibUnittest

public struct CollectionMisuseResiliencyChecks {
  public enum FailureKind {
    case none
    case trap
  }

  public var creatingOutOfBoundsIndicesBehavior: FailureKind = .trap
  public var subscriptOnOutOfBoundsIndicesBehavior: FailureKind = .trap
  public var subscriptRangeOnOutOfBoundsRangesBehavior: FailureKind = .trap

  public static var all: CollectionMisuseResiliencyChecks {
    return CollectionMisuseResiliencyChecks()
  }

  public static var none: CollectionMisuseResiliencyChecks {
    return CollectionMisuseResiliencyChecks(
      creatingOutOfBoundsIndicesBehavior: .none,
      subscriptOnOutOfBoundsIndicesBehavior: .none,
      subscriptRangeOnOutOfBoundsRangesBehavior: .none)
  }
}


/// Test that the elements of `instances` satisfy
/// the semantic
/// requirements of `Collection`, using `equalityOracle` to
/// generate equality expectations from pairs of positions in
/// `instances`.
///
/// - Precondition: `endIndex` is reachable from all
///   elements of `instances`.
public func checkIncrementable<Instances, BaseCollection>(
  _ instances: Instances,
  of baseCollection: BaseCollection,
  equalityOracle: (Instances.Index, Instances.Index) -> Bool,
  endIndex: Instances.Element,
  _ message: @autoclosure () -> String = "",
  stackTrace: SourceLocStack = SourceLocStack(),
  showFrame: Bool = true,
  file: String = #file, line: UInt = #line
) where
  Instances : Collection,
  BaseCollection : Collection,
  Instances.Element == BaseCollection.Index {

  checkEquatable(instances, oracle: equalityOracle, message(),
  stackTrace: stackTrace.pushIf(showFrame, file: file, line: line))
  for i in instances {
    if i != endIndex {
      let next = baseCollection.index(after: i)
      // index(after:) gets us a new index value
      expectNotEqual(i, next, message(),
        stackTrace: stackTrace.pushIf(showFrame, file: file, line: line))

      // Which is the same as if we apply formIndex(after:)
      var j = i
      baseCollection.formIndex(after: &j)
      expectEqual(j, next, message(),
        stackTrace: stackTrace.pushIf(showFrame, file: file, line: line))
    }
  }
}

/// Test that the elements of `instances` satisfy
/// some of the semantic
/// requirements of `BidirectionalCollection`, using `equalityOracle` to
/// generate equality expectations from pairs of positions in
/// `instances`.
///
/// - Precondition: all
///   elements of `instances` are reachable from `startIndex`.
public func checkDecrementable<Instances, BaseCollection>(
  _ instances: Instances,
  of baseCollection: BaseCollection,
  equalityOracle: (Instances.Index, Instances.Index) -> Bool,
  startIndex: Instances.Element,
  _ message: @autoclosure () -> String = "",
  stackTrace: SourceLocStack = SourceLocStack(),
  showFrame: Bool = true,
  file: String = #file, line: UInt = #line
) where
  Instances : Collection,
  BaseCollection : BidirectionalCollection,
  Instances.Element == BaseCollection.Index {

  checkEquatable(instances, oracle: equalityOracle, message(),
    stackTrace: stackTrace.pushIf(showFrame, file: file, line: line))
  for i in instances {
    if i != startIndex {
      let next = baseCollection.index(before: i)
      // index(before:) gets us a new index value
      expectNotEqual(i, next, message(),
        stackTrace: stackTrace.pushIf(showFrame, file: file, line: line))

      // Which is the same as if we apply formIndex(before:)
      var j = i
      baseCollection.formIndex(before: &j)
      expectEqual(j, next, message(),
        stackTrace: stackTrace.pushIf(showFrame, file: file, line: line))
    }
  }
}

internal func _checkIncrementalAdvance<Instances, BaseCollection>(
  _ instances: Instances,
  of baseCollection : BaseCollection,
  equalityOracle: (Instances.Index, Instances.Index) -> Bool,
  limit: Instances.Element,
  sign: Int, // 1 or -1
  next: (Instances.Element) -> Instances.Element,

  _ message: @autoclosure () -> String = "",
  stackTrace: SourceLocStack = SourceLocStack(),
  showFrame: Bool = true,
  file: String = #file, line: UInt = #line
) where
  Instances : Collection,
  BaseCollection : Collection,
  Instances.Element == BaseCollection.Index {
  for i in instances {
    let d: Int = sign > 0 ?
      baseCollection.distance(from: i, to: limit) :
      -baseCollection.distance(from: limit, to: i)

    var offset: Int = 0
    for _ in 0...Int64(d * sign) {
      let j = baseCollection.index(i, offsetBy: offset)
      let k = baseCollection.index(i, offsetBy: offset + sign, limitedBy: limit) ?? limit
      let jAtLimit = offset == d
      if jAtLimit {
        expectEqual(limit, j, message(),
        stackTrace: stackTrace.pushIf(showFrame, file: file, line: line))
      }
      expectEqual(jAtLimit ? j : next(j), k, message(),
        stackTrace: stackTrace.pushIf(showFrame, file: file, line: line))
      offset += sign
    }
  }
}

/// Test that the elements of `instances` satisfy the semantic requirements of
/// index for `Collection`, using `equalityOracle` to generate equality
/// expectations from pairs of positions in `instances`.
///
/// - Precondition: `endIndex` is reachable from all elements of
///   `instances`
public func checkForwardIndex<Instances, BaseCollection>(
  _ instances: Instances,
  of baseCollection: BaseCollection,
  equalityOracle: (Instances.Index, Instances.Index) -> Bool,
  endIndex: Instances.Element,
  _ message: @autoclosure () -> String = "",
  stackTrace: SourceLocStack = SourceLocStack(),
  showFrame: Bool = true,
  file: String = #file, line: UInt = #line
) where
  Instances : Collection,
  BaseCollection : Collection,
  Instances.Element == BaseCollection.Index {

  checkIncrementable(instances, of: baseCollection,
    equalityOracle: equalityOracle, endIndex: endIndex, message(),
    stackTrace: stackTrace.pushIf(showFrame, file: file, line: line))

  _checkIncrementalAdvance(instances, of: baseCollection,
    equalityOracle: equalityOracle, limit: endIndex,
    sign: 1, next: { baseCollection.index(after: $0) }, message(),
    stackTrace: stackTrace.pushIf(showFrame, file: file, line: line))
}

/// Test that the elements of `instances` satisfy the semantic requirements of
/// index for `BidirectionalCollection`, using `equalityOracle` to generate
/// equality expectations from pairs of positions in `instances`.
///
/// - Precondition:
///   - all elements of `instances` are reachable from `startIndex`.
///   - `endIndex` is reachable from all elements of `instances`.
public func checkBidirectionalIndex<Instances, BaseCollection>(
  _ instances: Instances,
  of baseCollection: BaseCollection,
  equalityOracle: (Instances.Index, Instances.Index) -> Bool,
  startIndex: Instances.Element,
  endIndex: Instances.Element,

  _ message: @autoclosure () -> String = "",
  stackTrace: SourceLocStack = SourceLocStack(),
  showFrame: Bool = true,
  file: String = #file, line: UInt = #line
) where
  Instances: Collection,
  BaseCollection : BidirectionalCollection,
  Instances.Element == BaseCollection.Index {

  checkForwardIndex(instances, of: baseCollection,
    equalityOracle: equalityOracle, endIndex: endIndex)

  checkDecrementable(instances, of: baseCollection,
    equalityOracle: equalityOracle, startIndex: startIndex, message(),
    stackTrace: stackTrace.pushIf(showFrame, file: file, line: line))

  _checkIncrementalAdvance(instances, of: baseCollection,
    equalityOracle: equalityOracle, limit: startIndex,
    sign: -1, next: { baseCollection.index(before: $0) }, message(),
    stackTrace: stackTrace.pushIf(showFrame, file: file, line: line))
}

/// Test that the elements of `instances` satisfy the semantic requirements of
/// index for `RandomAccessCollection`, using `advanceOracle` and
/// 'distanceOracle' to generate expectations about the results of
/// `advanced(by:)` and `distance(to:)` from pairs of positions in `instances`
/// and `distances`.
///
/// - Precondition:
///   - all elements of `instances` are reachable from `startIndex`.
///   - `endIndex` is reachable from all elements of `instances`.
public func checkRandomAccessIndex<Instances, Distances, BaseCollection>(
  _ instances: Instances, distances: Distances,
  of baseCollection: BaseCollection,
  distanceOracle:
    (Instances.Index, Instances.Index) -> Distances.Element,
  advanceOracle:
    (Instances.Index, Distances.Index) -> Instances.Element,
  startIndex: Instances.Element,
  endIndex: Instances.Element,

  _ message: @autoclosure () -> String = "",
  stackTrace: SourceLocStack = SourceLocStack(),
  showFrame: Bool = true,
  file: String = #file, line: UInt = #line
) where
  Instances : Collection,
  Distances : Collection,
  BaseCollection : RandomAccessCollection,
  Instances.Element == BaseCollection.Index,
  Distances.Element == Int {

  checkBidirectionalIndex(instances, of: baseCollection,
    equalityOracle: { distanceOracle($0, $1) == 0 },
    startIndex: startIndex, endIndex: endIndex, message(),
    stackTrace: stackTrace.pushIf(showFrame, file: file, line: line))

  checkAdvancesAndDistances(
    instances, distances: distances,
    of: baseCollection,
    distanceOracle: distanceOracle,
    advanceOracle: advanceOracle, message(),
    stackTrace: stackTrace.pushIf(showFrame, file: file, line: line))
}

// Copies what checkStrideable is doing, but instead of calling
// advanced(by:) and distance(to:) on an Strideable's,
// calls corresponding methods on a base collection.
public func checkAdvancesAndDistances<Instances, Distances, BaseCollection>(
  _ instances: Instances, distances: Distances,
  of baseCollection: BaseCollection,
  distanceOracle:
    (Instances.Index, Instances.Index) -> Distances.Element,
  advanceOracle:
    (Instances.Index, Distances.Index) -> Instances.Element,

  _ message: @autoclosure () -> String = "",
  stackTrace: SourceLocStack = SourceLocStack(),
  showFrame: Bool = true,
  file: String = #file, line: UInt = #line
) where
  Instances : Collection,
  Distances : Collection,
  BaseCollection : Collection,
  Instances.Element == BaseCollection.Index,
  Distances.Element == Int {

  checkComparable(
    instances,
    oracle: {
      let d = distanceOracle($1, $0);
      return d < 0 ? .lt : d == 0 ? .eq : .gt
    },
    message(),
    stackTrace: stackTrace.pushIf(showFrame, file: file, line: line))

  for i in instances.indices {
    let x = instances[i]
    expectEqual(x, baseCollection.index(x, offsetBy: 0))

    for j in distances.indices {
      let y = distances[j]
      expectEqual(advanceOracle(i, j), baseCollection.index(x, offsetBy: y))
    }

    for j in instances.indices {
      let y = instances[j]
      expectEqual(distanceOracle(i, j), baseCollection.distance(from: x, to: y))
    }
  }
}

// Generate two overloads: one for Array (which will get
// picked up when the caller passes a literal), and another that
// accepts any appropriate Collection type.

// Top-level check for Collection instances. Alias for checkForwardCollection.
// Checks all slices: O(n^2).
public func checkCollection<Expected: Collection, C : Collection>(
  _ expected: Expected,
  _ collection: C,

  _ message: @autoclosure () -> String = "",
  stackTrace: SourceLocStack = SourceLocStack(),
  showFrame: Bool = true,
  file: String = #file, line: UInt = #line,
  resiliencyChecks: CollectionMisuseResiliencyChecks = .all,
  sameValue: (Expected.Element, Expected.Element) -> Bool
) where C.Element == Expected.Element {

  checkForwardCollection(expected, collection, message(),
    stackTrace: stackTrace, showFrame: showFrame, file: file, line: line,
    resiliencyChecks: resiliencyChecks,
    sameValue: sameValue)
}


// Calls checkForwardCollection with default `sameValue`.
public func checkForwardCollection<
  Expected: Collection, C : Collection
>(
  _ expected: Expected, _ collection: C,

  _ message: @autoclosure () -> String = "",
  stackTrace: SourceLocStack = SourceLocStack(),
  showFrame: Bool = true,
  file: String = #file, line: UInt = #line,
  resiliencyChecks: CollectionMisuseResiliencyChecks = .all
) where
  C.Element == Expected.Element,
  Expected.Element : Equatable {

  checkForwardCollection(
    expected, collection, message(),
    stackTrace: stackTrace.pushIf(showFrame, file: file, line: line),
    resiliencyChecks: resiliencyChecks) { $0 == $1 }
}

// Top-Level check for all Collection semantics on a single
// instance. This constrains SubSequence associated types in order to check
// slice semantics.
// Checks all slices: O(n^2).
public func checkForwardCollection<
  Expected: Collection, C : Collection
>(
  _ expected: Expected, _ collection: C,

  _ message: @autoclosure () -> String = "",
  stackTrace: SourceLocStack = SourceLocStack(),
  showFrame: Bool = true,
  file: String = #file, line: UInt = #line,
  resiliencyChecks: CollectionMisuseResiliencyChecks = .all,
  sameValue: (Expected.Element, Expected.Element) -> Bool
) where
  C.Element == Expected.Element {

  checkOneLevelOfForwardCollection(expected, collection, message(),
    stackTrace: stackTrace.pushIf(showFrame, file: file, line: line),
    resiliencyChecks: resiliencyChecks, sameValue: sameValue)

  // Avoid validation of all possible (n^2) slices on large collection.
  // Test cases should call checkOneLevelOfForwardCollection instead.
  expectLT(expected.count, 30)

  _checkSliceableWithForwardIndex(expected, collection, message(),
    stackTrace: stackTrace.pushIf(showFrame, file: file, line: line),
    resiliencyChecks: resiliencyChecks, sameValue: sameValue)
}

// Helper for checkForwardCollection. Check that instance of `C`,
// `collection`, upholds the semantics of `Collection`,
// non-recursively. This does not check subsequences. It may be called for each
// subsequence without combinatorial explosion. Also, since recursive protocol
// constraints are not supported, our second level of checks cannot depend on the
// associated type properties of SubSequence.
//
// Checks all slices: O(n^2).
public func checkOneLevelOfForwardCollection<
  Expected: Collection, C : Collection
>(
  _ expected: Expected, _ collection: C,

  _ message: @autoclosure () -> String = "",
  stackTrace: SourceLocStack = SourceLocStack(),
  showFrame: Bool = true,
  file: String = #file, line: UInt = #line,
  resiliencyChecks: CollectionMisuseResiliencyChecks = .all,
  sameValue: (Expected.Element, Expected.Element) -> Bool
) where C.Element == Expected.Element {

  // A `Collection` is a multi-pass `Sequence`.
  for _ in 0..<3 {
    checkSequence(
      expected, collection, message(),
      stackTrace: stackTrace.pushIf(showFrame, file: file, line: line),
      resiliencyChecks: resiliencyChecks, sameValue: sameValue)
  }

  //===------------------------------------------------------------------===//
  // Check Index semantics
  //===------------------------------------------------------------------===//

  let succ = { collection.index(after: $0) }
  // Advances up to 1 positions without passing endIndex.  Don't use
  // advanced(by: n) to do this because it's under test here.
  let next = { $0 == collection.endIndex ? $0 : succ($0) }

  // advances up to 5 positions without passing endIndex.  Picking a
  // small constant to avoid complexity explosion on large input
  // collections.
  let next5 = { next(next(next(next(next($0))))) }

  let partWay0 = next5(collection.startIndex)
  let partWay1 = next5(partWay0)


  let instances = _allIndices(into: collection,
    in: collection.startIndex..<partWay0)
  checkForwardIndex(instances, of: collection,
    equalityOracle: { $0 == $1 }, endIndex: partWay1, message(),
    stackTrace: stackTrace.pushIf(showFrame, file: file, line: line))


  let expectedArray = Array(expected)

  // Check `count`.
  expectEqual(Int64(expectedArray.count), Int64(collection.count), message(),
    stackTrace: stackTrace.pushIf(showFrame, file: file, line: line))

  //===------------------------------------------------------------------===//
  // Check Iteration behavior.
  //===------------------------------------------------------------------===//

  for _ in 0..<3 {
    do {
      let startIndex = collection.startIndex
      let endIndex = collection.endIndex

      for _ in collection.indices {
        expectEqual(
          startIndex, collection.startIndex,
          "Iteration should not change startIndex",
          stackTrace: stackTrace.pushIf(showFrame, file: file, line: line))

        expectEqual(
          endIndex, collection.endIndex,
          "Iteration should not change endIndex",
          stackTrace: stackTrace.pushIf(showFrame, file: file, line: line))
      }
    }

    let allIndices = Array(collection.indices)

    if expectedArray.count >= 2 {
      for i in 0..<allIndices.count-1 {
        let successor1 = succ(allIndices[i])
        var successor2 = allIndices[i]
        successor2 = succ(successor2)
        var successor3 = allIndices[i]
        successor3 = succ(successor3)
        for s in [ successor1, successor2, successor3 ] {
          expectEqual(allIndices[i + 1], s, message(),
            stackTrace: stackTrace.pushIf(showFrame, file: file, line: line))
          expectEqualTest(
            expectedArray[i + 1], collection[s], message(),
            stackTrace: stackTrace.pushIf(showFrame, file: file, line: line), sameValue: sameValue)
        }
      }


    } // end of `if expectedArray.count >= 2`

    do {
      var allIndices2: [C.Index] = []
      for i in collection.indices {
        allIndices2.append(i)
      }

      expectEqualSequence(
        allIndices, allIndices2, "iteration should not invalidate indices",
        stackTrace: stackTrace.pushIf(showFrame, file: file, line: line))

      expectEqualSequence(
        expectedArray, allIndices.map { collection[$0] },
        stackTrace: stackTrace.pushIf(showFrame, file: file, line: line), sameValue: sameValue)
      expectEqualSequence(
        expectedArray, allIndices2.map { collection[$0] },
        stackTrace: stackTrace.pushIf(showFrame, file: file, line: line), sameValue: sameValue)
    }
  } // end of `for _ in 0..<3`

  // FIXME: more checks for bidirectional and random access collections.
}

// Helper for checkForwardCollection to check Slices.
//
// Checks all slices: O(n^2).
internal func _checkSliceableWithForwardIndex<
Expected: Collection, S : Collection
>(
  _ expected: Expected, _ sliceable: S,
  _ message: @autoclosure () -> String = "",
  stackTrace: SourceLocStack = SourceLocStack(),
  showFrame: Bool = true,
  file: String = #file, line: UInt = #line,
  resiliencyChecks: CollectionMisuseResiliencyChecks = .all,
  sameValue: (Expected.Element, Expected.Element) -> Bool
) where
  S.Element == Expected.Element {

  let expectedArray = Array(expected)

  let succ = { sliceable.index(after: $0) }

  var start = sliceable.startIndex
  for startNumericIndex in 0...expectedArray.count {
    var end = start
    for endNumericIndex in startNumericIndex...expectedArray.count {
      let expectedSlice = expectedArray[startNumericIndex..<endNumericIndex]
      let slice = sliceable[start..<end]
      // For every possible slice, verify that the slice's bounds are identical
      // to the indices used to form the slice.
      expectEqual(start, slice.startIndex)
      expectEqual(end, slice.endIndex)

      checkOneLevelOfForwardCollection(expectedSlice, slice, message(),
        stackTrace: stackTrace.pushIf(showFrame, file: file, line: line),
        resiliencyChecks: resiliencyChecks,
        sameValue: sameValue)

      if end != sliceable.endIndex {
        end = succ(end)
      }
    }
    if start != sliceable.endIndex {
      start = succ(start)
    }
  }
}


// Calls checkBidirectionalCollection with default `sameValue`.
public func checkBidirectionalCollection<
  Expected: Collection, C : BidirectionalCollection
>(
  _ expected: Expected, _ collection: C,

  _ message: @autoclosure () -> String = "",
  stackTrace: SourceLocStack = SourceLocStack(),
  showFrame: Bool = true,
  file: String = #file, line: UInt = #line,
  resiliencyChecks: CollectionMisuseResiliencyChecks = .all
) where
  C.Element == Expected.Element,
  Expected.Element : Equatable {

  checkBidirectionalCollection(
    expected, collection, message(),
    stackTrace: stackTrace.pushIf(showFrame, file: file, line: line),
    resiliencyChecks: resiliencyChecks) { $0 == $1 }
}

// Top-Level check for all BidirectionalCollection semantics on a single
// instance. This constrains SubSequence associated types in order to check
// slice semantics.
// Checks all slices: O(n^2).
public func checkBidirectionalCollection<
  Expected: Collection, C : BidirectionalCollection
>(
  _ expected: Expected, _ collection: C,

  _ message: @autoclosure () -> String = "",
  stackTrace: SourceLocStack = SourceLocStack(),
  showFrame: Bool = true,
  file: String = #file, line: UInt = #line,
  resiliencyChecks: CollectionMisuseResiliencyChecks = .all,
  sameValue: (Expected.Element, Expected.Element) -> Bool
) where
  C.Element == Expected.Element {

  checkOneLevelOfBidirectionalCollection(expected, collection, message(),
    stackTrace: stackTrace.pushIf(showFrame, file: file, line: line),
    resiliencyChecks: resiliencyChecks, sameValue: sameValue)

  // Avoid validation of all possible (n^2) slices on large collection.
  // Test cases should call checkOneLevelOfBidirectionalCollection instead.
  expectLT(expected.count, 30)

  _checkSliceableWithBidirectionalIndex(expected, collection, message(),
    stackTrace: stackTrace.pushIf(showFrame, file: file, line: line),
    resiliencyChecks: resiliencyChecks, sameValue: sameValue)
}

// Helper for checkBidirectionalCollection. Check that instance of `C`,
// `collection`, upholds the semantics of `BidirectionalCollection`,
// non-recursively. This does not check subsequences. It may be called for each
// subsequence without combinatorial explosion. Also, since recursive protocol
// constraints are not supported, our second level of checks cannot depend on the
// associated type properties of SubSequence.
//
// Checks all slices: O(n^2).
public func checkOneLevelOfBidirectionalCollection<
  Expected: Collection, C : BidirectionalCollection
>(
  _ expected: Expected, _ collection: C,

  _ message: @autoclosure () -> String = "",
  stackTrace: SourceLocStack = SourceLocStack(),
  showFrame: Bool = true,
  file: String = #file, line: UInt = #line,
  resiliencyChecks: CollectionMisuseResiliencyChecks = .all,
  sameValue: (Expected.Element, Expected.Element) -> Bool
) where C.Element == Expected.Element {

  // A `Collection` is a multi-pass `Sequence`.
  for _ in 0..<3 {
    checkSequence(
      expected, collection, message(),
      stackTrace: stackTrace.pushIf(showFrame, file: file, line: line),
      resiliencyChecks: resiliencyChecks, sameValue: sameValue)
  }

  //===------------------------------------------------------------------===//
  // Check Index semantics
  //===------------------------------------------------------------------===//

  let succ = { collection.index(after: $0) }
  let pred = { collection.index(before: $0) }
  // Advances up to 1 positions without passing endIndex.  Don't use
  // advanced(by: n) to do this because it's under test here.
  let next = { $0 == collection.endIndex ? $0 : succ($0) }

  // advances up to 5 positions without passing endIndex.  Picking a
  // small constant to avoid complexity explosion on large input
  // collections.
  let next5 = { next(next(next(next(next($0))))) }

  let partWay0 = next5(collection.startIndex)
  let partWay1 = next5(partWay0)


  let instances = _allIndices(into: collection, in: partWay0..<partWay1)
  checkBidirectionalIndex(instances, of: collection,
    equalityOracle: { $0 == $1 },
    startIndex: collection.startIndex,
    endIndex: next5(partWay1), message(),
    stackTrace: stackTrace.pushIf(showFrame, file: file, line: line))


  let expectedArray = Array(expected)

  // Check `count`.
  expectEqual(Int64(expectedArray.count), Int64(collection.count), message(),
    stackTrace: stackTrace.pushIf(showFrame, file: file, line: line))

  //===------------------------------------------------------------------===//
  // Check Iteration behavior.
  //===------------------------------------------------------------------===//

  for _ in 0..<3 {
    do {
      let startIndex = collection.startIndex
      let endIndex = collection.endIndex

      for _ in collection.indices {
        expectEqual(
          startIndex, collection.startIndex,
          "Iteration should not change startIndex",
          stackTrace: stackTrace.pushIf(showFrame, file: file, line: line))

        expectEqual(
          endIndex, collection.endIndex,
          "Iteration should not change endIndex",
          stackTrace: stackTrace.pushIf(showFrame, file: file, line: line))
      }
    }

    let allIndices = Array(collection.indices)

    if expectedArray.count >= 2 {
      for i in 0..<allIndices.count-1 {
        let successor1 = succ(allIndices[i])
        var successor2 = allIndices[i]
        successor2 = succ(successor2)
        var successor3 = allIndices[i]
        successor3 = succ(successor3)
        for s in [ successor1, successor2, successor3 ] {
          expectEqual(allIndices[i + 1], s, message(),
            stackTrace: stackTrace.pushIf(showFrame, file: file, line: line))
          expectEqualTest(
            expectedArray[i + 1], collection[s], message(),
            stackTrace: stackTrace.pushIf(showFrame, file: file, line: line), sameValue: sameValue)
        }
      }


      for i in 1..<allIndices.count {
        let predecessor1 = pred(allIndices[i])
        var predecessor2 = allIndices[i]
        predecessor2 = pred(predecessor2)
        var predecessor3 = allIndices[i]
        predecessor3 = pred(predecessor3)
        for p in [ predecessor1, predecessor2, predecessor3 ] {
          expectEqual(allIndices[i - 1], p, message(),
            stackTrace: stackTrace.pushIf(showFrame, file: file, line: line))
          expectEqualTest(
            expectedArray[i - 1], collection[p], message(),
            stackTrace: stackTrace.pushIf(showFrame, file: file, line: line), sameValue: sameValue)
        }
      }
      for i in 1..<allIndices.count {
        let index = succ(pred(allIndices[i]))
        expectEqual(allIndices[i], index, message(),
          stackTrace: stackTrace.pushIf(showFrame, file: file, line: line))
        expectEqualTest(
          expectedArray[i], collection[index], message(),
          stackTrace: stackTrace.pushIf(showFrame, file: file, line: line), sameValue: sameValue)
      }


    } // end of `if expectedArray.count >= 2`

    do {
      var allIndices2: [C.Index] = []
      for i in collection.indices {
        allIndices2.append(i)
      }

      expectEqualSequence(
        allIndices, allIndices2, "iteration should not invalidate indices",
        stackTrace: stackTrace.pushIf(showFrame, file: file, line: line))

      expectEqualSequence(
        expectedArray, allIndices.map { collection[$0] },
        stackTrace: stackTrace.pushIf(showFrame, file: file, line: line), sameValue: sameValue)
      expectEqualSequence(
        expectedArray, allIndices2.map { collection[$0] },
        stackTrace: stackTrace.pushIf(showFrame, file: file, line: line), sameValue: sameValue)
    }
  } // end of `for _ in 0..<3`

  // FIXME: more checks for bidirectional and random access collections.
}

// Helper for checkBidirectionalCollection to check Slices.
//
// Checks all slices: O(n^2).
internal func _checkSliceableWithBidirectionalIndex<
Expected: Collection, S : BidirectionalCollection
>(
  _ expected: Expected, _ sliceable: S,
  _ message: @autoclosure () -> String = "",
  stackTrace: SourceLocStack = SourceLocStack(),
  showFrame: Bool = true,
  file: String = #file, line: UInt = #line,
  resiliencyChecks: CollectionMisuseResiliencyChecks = .all,
  sameValue: (Expected.Element, Expected.Element) -> Bool
) where
  S.Element == Expected.Element {

  let expectedArray = Array(expected)

  let succ = { sliceable.index(after: $0) }
  let pred = { sliceable.index(before: $0) }

  var start = sliceable.startIndex
  for startNumericIndex in 0...expectedArray.count {
    if start != sliceable.endIndex {
      start = succ(start)
      start = pred(start)
      start = succ(start)
      start = pred(start)
    }
    var end = start
    for endNumericIndex in startNumericIndex...expectedArray.count {
      if end != sliceable.endIndex {
        end = succ(end)
        end = pred(end)
        end = succ(end)
        end = pred(end)
      }
      let expectedSlice = expectedArray[startNumericIndex..<endNumericIndex]
      let slice = sliceable[start..<end]
      // For every possible slice, verify that the slice's bounds are identical
      // to the indices used to form the slice.
      expectEqual(start, slice.startIndex)
      expectEqual(end, slice.endIndex)

      checkOneLevelOfBidirectionalCollection(expectedSlice, slice, message(),
        stackTrace: stackTrace.pushIf(showFrame, file: file, line: line),
        resiliencyChecks: resiliencyChecks,
        sameValue: sameValue)

      if end != sliceable.endIndex {
        end = succ(end)
      }
    }
    if start != sliceable.endIndex {
      start = succ(start)
    }
  }
}


// Calls checkRandomAccessCollection with default `sameValue`.
public func checkRandomAccessCollection<
  Expected: Collection, C : RandomAccessCollection
>(
  _ expected: Expected, _ collection: C,

  _ message: @autoclosure () -> String = "",
  stackTrace: SourceLocStack = SourceLocStack(),
  showFrame: Bool = true,
  file: String = #file, line: UInt = #line,
  resiliencyChecks: CollectionMisuseResiliencyChecks = .all
) where
  C.Element == Expected.Element,
  Expected.Element : Equatable {

  checkRandomAccessCollection(
    expected, collection, message(),
  stackTrace: stackTrace.pushIf(showFrame, file: file, line: line),
    resiliencyChecks: resiliencyChecks) { $0 == $1 }
}

// Top-Level check for all RandomAccessCollection semantics on a single
// instance. This constrains SubSequence associated types in order to check
// slice semantics.
// Checks all slices: O(n^2).
public func checkRandomAccessCollection<
  Expected: Collection, C : RandomAccessCollection
>(
  _ expected: Expected, _ collection: C,

  _ message: @autoclosure () -> String = "",
  stackTrace: SourceLocStack = SourceLocStack(),
  showFrame: Bool = true,
  file: String = #file, line: UInt = #line,
  resiliencyChecks: CollectionMisuseResiliencyChecks = .all,
  sameValue: (Expected.Element, Expected.Element) -> Bool
) where
  C.Element == Expected.Element {

  checkOneLevelOfRandomAccessCollection(expected, collection, message(),
    stackTrace: stackTrace.pushIf(showFrame, file: file, line: line),
    resiliencyChecks: resiliencyChecks, sameValue: sameValue)

  // Avoid validation of all possible (n^2) slices on large collection.
  // Test cases should call checkOneLevelOfRandomAccessCollection instead.
  expectLT(expected.count, 30)

  _checkSliceableWithRandomAccessIndex(expected, collection, message(),
    stackTrace: stackTrace.pushIf(showFrame, file: file, line: line),
    resiliencyChecks: resiliencyChecks, sameValue: sameValue)
}

// Helper for checkRandomAccessCollection. Check that instance of `C`,
// `collection`, upholds the semantics of `RandomAccessCollection`,
// non-recursively. This does not check subsequences. It may be called for each
// subsequence without combinatorial explosion. Also, since recursive protocol
// constraints are not supported, our second level of checks cannot depend on the
// associated type properties of SubSequence.
//
// Checks all slices: O(n^2).
public func checkOneLevelOfRandomAccessCollection<
  Expected: Collection, C : RandomAccessCollection
>(
  _ expected: Expected, _ collection: C,

  _ message: @autoclosure () -> String = "",
  stackTrace: SourceLocStack = SourceLocStack(),
  showFrame: Bool = true,
  file: String = #file, line: UInt = #line,
  resiliencyChecks: CollectionMisuseResiliencyChecks = .all,
  sameValue: (Expected.Element, Expected.Element) -> Bool
) where C.Element == Expected.Element {

  // A `Collection` is a multi-pass `Sequence`.
  for _ in 0..<3 {
    checkSequence(
      expected, collection, message(),
      stackTrace: stackTrace.pushIf(showFrame, file: file, line: line),
      resiliencyChecks: resiliencyChecks, sameValue: sameValue)
  }

  //===------------------------------------------------------------------===//
  // Check Index semantics
  //===------------------------------------------------------------------===//

  let succ = { collection.index(after: $0) }
  // Advances up to 1 positions without passing endIndex.  Don't use
  // advanced(by: n) to do this because it's under test here.
  let next = { $0 == collection.endIndex ? $0 : succ($0) }

  // advances up to 5 positions without passing endIndex.  Picking a
  // small constant to avoid complexity explosion on large input
  // collections.
  let next5 = { next(next(next(next(next($0))))) }

  let partWay0 = next5(collection.startIndex)
  let partWay1 = next5(partWay0)

  typealias Distance = Int

  let count: Distance  = collection.count
  let offset0 = min(5, count)
  let offset1 = min(10, count)

  let distanceCandidates: [Distance] = [
    -11, -7, -5, -3, -2, -1, 0, 1, 2, 3, 5, 7, 11]

  let distances = distanceCandidates.filter { (x: Distance) -> Bool in
    x + offset0 >= 0 && x + offset1 <= count
  }

  func nextN(_ n: Distance, _ i: C.Index) -> C.Index {
    return collection.index(i, offsetBy: n)
  }

  let instances = _allIndices(into: collection, in: partWay0..<partWay1)

  checkRandomAccessIndex(
    instances,
    distances: distances,
    of: collection,
    distanceOracle: { (x:Int, y:Int) in y - x },
    advanceOracle: { x, y in nextN(distances[y], instances[x]) },
    startIndex: collection.startIndex,
    endIndex: next5(partWay1), message(),
    stackTrace: stackTrace.pushIf(showFrame, file: file, line: line))


  let expectedArray = Array(expected)

  // Check `count`.
  expectEqual(Int64(expectedArray.count), Int64(collection.count), message(),
    stackTrace: stackTrace.pushIf(showFrame, file: file, line: line))

  //===------------------------------------------------------------------===//
  // Check Iteration behavior.
  //===------------------------------------------------------------------===//

  for _ in 0..<3 {
    do {
      let startIndex = collection.startIndex
      let endIndex = collection.endIndex

      for _ in collection.indices {
        expectEqual(
          startIndex, collection.startIndex,
          "Iteration should not change startIndex",
          stackTrace: stackTrace.pushIf(showFrame, file: file, line: line))

        expectEqual(
          endIndex, collection.endIndex,
          "Iteration should not change endIndex",
          stackTrace: stackTrace.pushIf(showFrame, file: file, line: line))
      }
    }

    let allIndices = Array(collection.indices)

    if expectedArray.count >= 2 {
      for i in 0..<allIndices.count-1 {
        let successor1 = succ(allIndices[i])
        var successor2 = allIndices[i]
        successor2 = succ(successor2)
        var successor3 = allIndices[i]
        successor3 = succ(successor3)
        for s in [ successor1, successor2, successor3 ] {
          expectEqual(allIndices[i + 1], s, message(),
            stackTrace: stackTrace.pushIf(showFrame, file: file, line: line))
          expectEqualTest(
            expectedArray[i + 1], collection[s], message(),
            stackTrace: stackTrace.pushIf(showFrame, file: file, line: line), sameValue: sameValue)
        }
      }


    } // end of `if expectedArray.count >= 2`

    do {
      var allIndices2: [C.Index] = []
      for i in collection.indices {
        allIndices2.append(i)
      }

      expectEqualSequence(
        allIndices, allIndices2, "iteration should not invalidate indices",
        stackTrace: stackTrace.pushIf(showFrame, file: file, line: line))

      expectEqualSequence(
        expectedArray, allIndices.map { collection[$0] },
        stackTrace: stackTrace.pushIf(showFrame, file: file, line: line), sameValue: sameValue)
      expectEqualSequence(
        expectedArray, allIndices2.map { collection[$0] },
        stackTrace: stackTrace.pushIf(showFrame, file: file, line: line), sameValue: sameValue)
    }
  } // end of `for _ in 0..<3`

  // FIXME: more checks for bidirectional and random access collections.
}

// Helper for checkRandomAccessCollection to check Slices.
//
// Checks all slices: O(n^2).
internal func _checkSliceableWithRandomAccessIndex<
Expected: Collection, S : RandomAccessCollection
>(
  _ expected: Expected, _ sliceable: S,
  _ message: @autoclosure () -> String = "",
  stackTrace: SourceLocStack = SourceLocStack(),
  showFrame: Bool = true,
  file: String = #file, line: UInt = #line,
  resiliencyChecks: CollectionMisuseResiliencyChecks = .all,
  sameValue: (Expected.Element, Expected.Element) -> Bool
) where
  S.Element == Expected.Element {

  let expectedArray = Array(expected)

  let succ = { sliceable.index(after: $0) }
  let pred = { sliceable.index(before: $0) }

  var start = sliceable.startIndex
  for startNumericIndex in 0...expectedArray.count {
    if start != sliceable.endIndex {
      start = succ(start)
      start = pred(start)
      start = succ(start)
      start = pred(start)
    }
    var end = start
    for endNumericIndex in startNumericIndex...expectedArray.count {
      if end != sliceable.endIndex {
        end = succ(end)
        end = pred(end)
        end = succ(end)
        end = pred(end)
      }
      let expectedSlice = expectedArray[startNumericIndex..<endNumericIndex]
      let slice = sliceable[start..<end]
      // For every possible slice, verify that the slice's bounds are identical
      // to the indices used to form the slice.
      expectEqual(start, slice.startIndex)
      expectEqual(end, slice.endIndex)

      checkOneLevelOfRandomAccessCollection(expectedSlice, slice, message(),
        stackTrace: stackTrace.pushIf(showFrame, file: file, line: line),
        resiliencyChecks: resiliencyChecks,
        sameValue: sameValue)

      if end != sliceable.endIndex {
        end = succ(end)
      }
    }
    if start != sliceable.endIndex {
      start = succ(start)
    }
  }
}



// Top-level check for Collection instances. Alias for checkForwardCollection.
// Checks all slices: O(n^2).
public func checkCollection<Element, C : Collection>(
  _ expected: Array<Element>,
  _ collection: C,

  _ message: @autoclosure () -> String = "",
  stackTrace: SourceLocStack = SourceLocStack(),
  showFrame: Bool = true,
  file: String = #file, line: UInt = #line,
  resiliencyChecks: CollectionMisuseResiliencyChecks = .all,
  sameValue: (Element, Element) -> Bool
) where C.Element == Element {

  checkForwardCollection(expected, collection, message(),
    stackTrace: stackTrace, showFrame: showFrame, file: file, line: line,
    resiliencyChecks: resiliencyChecks,
    sameValue: sameValue)
}


// Calls checkForwardCollection with default `sameValue`.
public func checkForwardCollection<
  Element, C : Collection
>(
  _ expected: Array<Element>, _ collection: C,

  _ message: @autoclosure () -> String = "",
  stackTrace: SourceLocStack = SourceLocStack(),
  showFrame: Bool = true,
  file: String = #file, line: UInt = #line,
  resiliencyChecks: CollectionMisuseResiliencyChecks = .all
) where
  C.Element == Element,
  Element : Equatable {

  checkForwardCollection(
    expected, collection, message(),
    stackTrace: stackTrace.pushIf(showFrame, file: file, line: line),
    resiliencyChecks: resiliencyChecks) { $0 == $1 }
}

// Top-Level check for all Collection semantics on a single
// instance. This constrains SubSequence associated types in order to check
// slice semantics.
// Checks all slices: O(n^2).
public func checkForwardCollection<
  Element, C : Collection
>(
  _ expected: Array<Element>, _ collection: C,

  _ message: @autoclosure () -> String = "",
  stackTrace: SourceLocStack = SourceLocStack(),
  showFrame: Bool = true,
  file: String = #file, line: UInt = #line,
  resiliencyChecks: CollectionMisuseResiliencyChecks = .all,
  sameValue: (Element, Element) -> Bool
) where
  C.Element == Element {

  checkOneLevelOfForwardCollection(expected, collection, message(),
  stackTrace: stackTrace.pushIf(showFrame, file: file, line: line),
    resiliencyChecks: resiliencyChecks, sameValue: sameValue)

  // Avoid validation of all possible (n^2) slices on large collection.
  // Test cases should call checkOneLevelOfForwardCollection instead.
  expectLT(expected.count, 30)

  _checkSliceableWithForwardIndex(expected, collection, message(),
    stackTrace: stackTrace.pushIf(showFrame, file: file, line: line),
    resiliencyChecks: resiliencyChecks, sameValue: sameValue)
}

// Helper for checkForwardCollection. Check that instance of `C`,
// `collection`, upholds the semantics of `Collection`,
// non-recursively. This does not check subsequences. It may be called for each
// subsequence without combinatorial explosion. Also, since recursive protocol
// constraints are not supported, our second level of checks cannot depend on the
// associated type properties of SubSequence.
//
// Checks all slices: O(n^2).
public func checkOneLevelOfForwardCollection<
  Element, C : Collection
>(
  _ expected: Array<Element>, _ collection: C,

  _ message: @autoclosure () -> String = "",
  stackTrace: SourceLocStack = SourceLocStack(),
  showFrame: Bool = true,
  file: String = #file, line: UInt = #line,
  resiliencyChecks: CollectionMisuseResiliencyChecks = .all,
  sameValue: (Element, Element) -> Bool
) where C.Element == Element {

  // A `Collection` is a multi-pass `Sequence`.
  for _ in 0..<3 {
    checkSequence(
      expected, collection, message(),
      stackTrace: stackTrace.pushIf(showFrame, file: file, line: line),
      resiliencyChecks: resiliencyChecks, sameValue: sameValue)
  }

  //===------------------------------------------------------------------===//
  // Check Index semantics
  //===------------------------------------------------------------------===//

  let succ = { collection.index(after: $0) }
  // Advances up to 1 positions without passing endIndex.  Don't use
  // advanced(by: n) to do this because it's under test here.
  let next = { $0 == collection.endIndex ? $0 : succ($0) }

  // advances up to 5 positions without passing endIndex.  Picking a
  // small constant to avoid complexity explosion on large input
  // collections.
  let next5 = { next(next(next(next(next($0))))) }

  let partWay0 = next5(collection.startIndex)
  let partWay1 = next5(partWay0)


  let instances = _allIndices(into: collection,
    in: collection.startIndex..<partWay0)
  checkForwardIndex(instances, of: collection,
    equalityOracle: { $0 == $1 }, endIndex: partWay1, message(),
    stackTrace: stackTrace.pushIf(showFrame, file: file, line: line))


  let expectedArray = Array(expected)

  // Check `count`.
  expectEqual(Int64(expectedArray.count), Int64(collection.count), message(),
    stackTrace: stackTrace.pushIf(showFrame, file: file, line: line))

  //===------------------------------------------------------------------===//
  // Check Iteration behavior.
  //===------------------------------------------------------------------===//

  for _ in 0..<3 {
    do {
      let startIndex = collection.startIndex
      let endIndex = collection.endIndex

      for _ in collection.indices {
        expectEqual(
          startIndex, collection.startIndex,
          "Iteration should not change startIndex",
          stackTrace: stackTrace.pushIf(showFrame, file: file, line: line))

        expectEqual(
          endIndex, collection.endIndex,
          "Iteration should not change endIndex",
          stackTrace: stackTrace.pushIf(showFrame, file: file, line: line))
      }
    }

    let allIndices = Array(collection.indices)

    if expectedArray.count >= 2 {
      for i in 0..<allIndices.count-1 {
        let successor1 = succ(allIndices[i])
        var successor2 = allIndices[i]
        successor2 = succ(successor2)
        var successor3 = allIndices[i]
        successor3 = succ(successor3)
        for s in [ successor1, successor2, successor3 ] {
          expectEqual(allIndices[i + 1], s, message(),
            stackTrace: stackTrace.pushIf(showFrame, file: file, line: line))
          expectEqualTest(
            expectedArray[i + 1], collection[s], message(),
            stackTrace: stackTrace.pushIf(showFrame, file: file, line: line), sameValue: sameValue)
        }
      }


    } // end of `if expectedArray.count >= 2`

    do {
      var allIndices2: [C.Index] = []
      for i in collection.indices {
        allIndices2.append(i)
      }

      expectEqualSequence(
        allIndices, allIndices2, "iteration should not invalidate indices",
        stackTrace: stackTrace.pushIf(showFrame, file: file, line: line))

      expectEqualSequence(
        expectedArray, allIndices.map { collection[$0] },
        stackTrace: stackTrace.pushIf(showFrame, file: file, line: line), sameValue: sameValue)
      expectEqualSequence(
        expectedArray, allIndices2.map { collection[$0] },
        stackTrace: stackTrace.pushIf(showFrame, file: file, line: line), sameValue: sameValue)
    }
  } // end of `for _ in 0..<3`

  // FIXME: more checks for bidirectional and random access collections.
}

// Helper for checkForwardCollection to check Slices.
//
// Checks all slices: O(n^2).
internal func _checkSliceableWithForwardIndex<
Element, S : Collection
>(
  _ expected: Array<Element>, _ sliceable: S,
  _ message: @autoclosure () -> String = "",
  stackTrace: SourceLocStack = SourceLocStack(),
  showFrame: Bool = true,
  file: String = #file, line: UInt = #line,
  resiliencyChecks: CollectionMisuseResiliencyChecks = .all,
  sameValue: (Element, Element) -> Bool
) where
  S.Element == Element {

  let expectedArray = Array(expected)

  let succ = { sliceable.index(after: $0) }

  var start = sliceable.startIndex
  for startNumericIndex in 0...expectedArray.count {
    var end = start
    for endNumericIndex in startNumericIndex...expectedArray.count {
      let expectedSlice = expectedArray[startNumericIndex..<endNumericIndex]
      let slice = sliceable[start..<end]
      // For every possible slice, verify that the slice's bounds are identical
      // to the indices used to form the slice.
      expectEqual(start, slice.startIndex)
      expectEqual(end, slice.endIndex)

      checkOneLevelOfForwardCollection(expectedSlice, slice, message(),
        stackTrace: stackTrace.pushIf(showFrame, file: file, line: line),
        resiliencyChecks: resiliencyChecks,
        sameValue: sameValue)

      if end != sliceable.endIndex {
        end = succ(end)
      }
    }
    if start != sliceable.endIndex {
      start = succ(start)
    }
  }
}


// Calls checkBidirectionalCollection with default `sameValue`.
public func checkBidirectionalCollection<
  Element, C : BidirectionalCollection
>(
  _ expected: Array<Element>, _ collection: C,

  _ message: @autoclosure () -> String = "",
  stackTrace: SourceLocStack = SourceLocStack(),
  showFrame: Bool = true,
  file: String = #file, line: UInt = #line,
  resiliencyChecks: CollectionMisuseResiliencyChecks = .all
) where
  C.Element == Element,
  Element : Equatable {

  checkBidirectionalCollection(
    expected, collection, message(),
  stackTrace: stackTrace.pushIf(showFrame, file: file, line: line),
    resiliencyChecks: resiliencyChecks) { $0 == $1 }
}

// Top-Level check for all BidirectionalCollection semantics on a single
// instance. This constrains SubSequence associated types in order to check
// slice semantics.
// Checks all slices: O(n^2).
public func checkBidirectionalCollection<
  Element, C : BidirectionalCollection
>(
  _ expected: Array<Element>, _ collection: C,

  _ message: @autoclosure () -> String = "",
  stackTrace: SourceLocStack = SourceLocStack(),
  showFrame: Bool = true,
  file: String = #file, line: UInt = #line,
  resiliencyChecks: CollectionMisuseResiliencyChecks = .all,
  sameValue: (Element, Element) -> Bool
) where
  C.Element == Element {

  checkOneLevelOfBidirectionalCollection(expected, collection, message(),
    stackTrace: stackTrace.pushIf(showFrame, file: file, line: line),
    resiliencyChecks: resiliencyChecks, sameValue: sameValue)

  // Avoid validation of all possible (n^2) slices on large collection.
  // Test cases should call checkOneLevelOfBidirectionalCollection instead.
  expectLT(expected.count, 30)

  _checkSliceableWithBidirectionalIndex(expected, collection, message(),
    stackTrace: stackTrace.pushIf(showFrame, file: file, line: line),
    resiliencyChecks: resiliencyChecks, sameValue: sameValue)
}

// Helper for checkBidirectionalCollection. Check that instance of `C`,
// `collection`, upholds the semantics of `BidirectionalCollection`,
// non-recursively. This does not check subsequences. It may be called for each
// subsequence without combinatorial explosion. Also, since recursive protocol
// constraints are not supported, our second level of checks cannot depend on the
// associated type properties of SubSequence.
//
// Checks all slices: O(n^2).
public func checkOneLevelOfBidirectionalCollection<
  Element, C : BidirectionalCollection
>(
  _ expected: Array<Element>, _ collection: C,

  _ message: @autoclosure () -> String = "",
  stackTrace: SourceLocStack = SourceLocStack(),
  showFrame: Bool = true,
  file: String = #file, line: UInt = #line,
  resiliencyChecks: CollectionMisuseResiliencyChecks = .all,
  sameValue: (Element, Element) -> Bool
) where C.Element == Element {

  // A `Collection` is a multi-pass `Sequence`.
  for _ in 0..<3 {
    checkSequence(
      expected, collection, message(),
      stackTrace: stackTrace.pushIf(showFrame, file: file, line: line),
      resiliencyChecks: resiliencyChecks, sameValue: sameValue)
  }

  //===------------------------------------------------------------------===//
  // Check Index semantics
  //===------------------------------------------------------------------===//

  let succ = { collection.index(after: $0) }
  let pred = { collection.index(before: $0) }
  // Advances up to 1 positions without passing endIndex.  Don't use
  // advanced(by: n) to do this because it's under test here.
  let next = { $0 == collection.endIndex ? $0 : succ($0) }

  // advances up to 5 positions without passing endIndex.  Picking a
  // small constant to avoid complexity explosion on large input
  // collections.
  let next5 = { next(next(next(next(next($0))))) }

  let partWay0 = next5(collection.startIndex)
  let partWay1 = next5(partWay0)


  let instances = _allIndices(into: collection, in: partWay0..<partWay1)
  checkBidirectionalIndex(instances, of: collection,
    equalityOracle: { $0 == $1 },
    startIndex: collection.startIndex,
    endIndex: next5(partWay1), message(),
    stackTrace: stackTrace.pushIf(showFrame, file: file, line: line))


  let expectedArray = Array(expected)

  // Check `count`.
  expectEqual(Int64(expectedArray.count), Int64(collection.count), message(),
    stackTrace: stackTrace.pushIf(showFrame, file: file, line: line))

  //===------------------------------------------------------------------===//
  // Check Iteration behavior.
  //===------------------------------------------------------------------===//

  for _ in 0..<3 {
    do {
      let startIndex = collection.startIndex
      let endIndex = collection.endIndex

      for _ in collection.indices {
        expectEqual(
          startIndex, collection.startIndex,
          "Iteration should not change startIndex",
          stackTrace: stackTrace.pushIf(showFrame, file: file, line: line))

        expectEqual(
          endIndex, collection.endIndex,
          "Iteration should not change endIndex",
          stackTrace: stackTrace.pushIf(showFrame, file: file, line: line))
      }
    }

    let allIndices = Array(collection.indices)

    if expectedArray.count >= 2 {
      for i in 0..<allIndices.count-1 {
        let successor1 = succ(allIndices[i])
        var successor2 = allIndices[i]
        successor2 = succ(successor2)
        var successor3 = allIndices[i]
        successor3 = succ(successor3)
        for s in [ successor1, successor2, successor3 ] {
          expectEqual(allIndices[i + 1], s, message(),
            stackTrace: stackTrace.pushIf(showFrame, file: file, line: line))
          expectEqualTest(
            expectedArray[i + 1], collection[s], message(),
            stackTrace: stackTrace.pushIf(showFrame, file: file, line: line), sameValue: sameValue)
        }
      }


      for i in 1..<allIndices.count {
        let predecessor1 = pred(allIndices[i])
        var predecessor2 = allIndices[i]
        predecessor2 = pred(predecessor2)
        var predecessor3 = allIndices[i]
        predecessor3 = pred(predecessor3)
        for p in [ predecessor1, predecessor2, predecessor3 ] {
          expectEqual(allIndices[i - 1], p, message(),
            stackTrace: stackTrace.pushIf(showFrame, file: file, line: line))
          expectEqualTest(
            expectedArray[i - 1], collection[p], message(),
            stackTrace: stackTrace.pushIf(showFrame, file: file, line: line), sameValue: sameValue)
        }
      }
      for i in 1..<allIndices.count {
        let index = succ(pred(allIndices[i]))
        expectEqual(allIndices[i], index, message(),
          stackTrace: stackTrace.pushIf(showFrame, file: file, line: line))
        expectEqualTest(
          expectedArray[i], collection[index], message(),
          stackTrace: stackTrace.pushIf(showFrame, file: file, line: line), sameValue: sameValue)
      }


    } // end of `if expectedArray.count >= 2`

    do {
      var allIndices2: [C.Index] = []
      for i in collection.indices {
        allIndices2.append(i)
      }

      expectEqualSequence(
        allIndices, allIndices2, "iteration should not invalidate indices",
        stackTrace: stackTrace.pushIf(showFrame, file: file, line: line))

      expectEqualSequence(
        expectedArray, allIndices.map { collection[$0] },
        stackTrace: stackTrace.pushIf(showFrame, file: file, line: line), sameValue: sameValue)
      expectEqualSequence(
        expectedArray, allIndices2.map { collection[$0] },
        stackTrace: stackTrace.pushIf(showFrame, file: file, line: line), sameValue: sameValue)
    }
  } // end of `for _ in 0..<3`

  // FIXME: more checks for bidirectional and random access collections.
}

// Helper for checkBidirectionalCollection to check Slices.
//
// Checks all slices: O(n^2).
internal func _checkSliceableWithBidirectionalIndex<
Element, S : BidirectionalCollection
>(
  _ expected: Array<Element>, _ sliceable: S,
  _ message: @autoclosure () -> String = "",
  stackTrace: SourceLocStack = SourceLocStack(),
  showFrame: Bool = true,
  file: String = #file, line: UInt = #line,
  resiliencyChecks: CollectionMisuseResiliencyChecks = .all,
  sameValue: (Element, Element) -> Bool
) where
  S.Element == Element {

  let expectedArray = Array(expected)

  let succ = { sliceable.index(after: $0) }
  let pred = { sliceable.index(before: $0) }

  var start = sliceable.startIndex
  for startNumericIndex in 0...expectedArray.count {
    if start != sliceable.endIndex {
      start = succ(start)
      start = pred(start)
      start = succ(start)
      start = pred(start)
    }
    var end = start
    for endNumericIndex in startNumericIndex...expectedArray.count {
      if end != sliceable.endIndex {
        end = succ(end)
        end = pred(end)
        end = succ(end)
        end = pred(end)
      }
      let expectedSlice = expectedArray[startNumericIndex..<endNumericIndex]
      let slice = sliceable[start..<end]
      // For every possible slice, verify that the slice's bounds are identical
      // to the indices used to form the slice.
      expectEqual(start, slice.startIndex)
      expectEqual(end, slice.endIndex)

      checkOneLevelOfBidirectionalCollection(expectedSlice, slice, message(),
        stackTrace: stackTrace.pushIf(showFrame, file: file, line: line),
        resiliencyChecks: resiliencyChecks,
        sameValue: sameValue)

      if end != sliceable.endIndex {
        end = succ(end)
      }
    }
    if start != sliceable.endIndex {
      start = succ(start)
    }
  }
}


// Calls checkRandomAccessCollection with default `sameValue`.
public func checkRandomAccessCollection<
  Element, C : RandomAccessCollection
>(
  _ expected: Array<Element>, _ collection: C,

  _ message: @autoclosure () -> String = "",
  stackTrace: SourceLocStack = SourceLocStack(),
  showFrame: Bool = true,
  file: String = #file, line: UInt = #line,
  resiliencyChecks: CollectionMisuseResiliencyChecks = .all
) where
  C.Element == Element,
  Element : Equatable {

  checkRandomAccessCollection(
    expected, collection, message(),
    stackTrace: stackTrace.pushIf(showFrame, file: file, line: line),
    resiliencyChecks: resiliencyChecks) { $0 == $1 }
}

// Top-Level check for all RandomAccessCollection semantics on a single
// instance. This constrains SubSequence associated types in order to check
// slice semantics.
// Checks all slices: O(n^2).
public func checkRandomAccessCollection<
  Element, C : RandomAccessCollection
>(
  _ expected: Array<Element>, _ collection: C,

  _ message: @autoclosure () -> String = "",
  stackTrace: SourceLocStack = SourceLocStack(),
  showFrame: Bool = true,
  file: String = #file, line: UInt = #line,
  resiliencyChecks: CollectionMisuseResiliencyChecks = .all,
  sameValue: (Element, Element) -> Bool
) where
  C.Element == Element {

  checkOneLevelOfRandomAccessCollection(expected, collection, message(),
    stackTrace: stackTrace.pushIf(showFrame, file: file, line: line),
    resiliencyChecks: resiliencyChecks, sameValue: sameValue)

  // Avoid validation of all possible (n^2) slices on large collection.
  // Test cases should call checkOneLevelOfRandomAccessCollection instead.
  expectLT(expected.count, 30)

  _checkSliceableWithRandomAccessIndex(expected, collection, message(),
    stackTrace: stackTrace.pushIf(showFrame, file: file, line: line),
    resiliencyChecks: resiliencyChecks, sameValue: sameValue)
}

// Helper for checkRandomAccessCollection. Check that instance of `C`,
// `collection`, upholds the semantics of `RandomAccessCollection`,
// non-recursively. This does not check subsequences. It may be called for each
// subsequence without combinatorial explosion. Also, since recursive protocol
// constraints are not supported, our second level of checks cannot depend on the
// associated type properties of SubSequence.
//
// Checks all slices: O(n^2).
public func checkOneLevelOfRandomAccessCollection<
  Element, C : RandomAccessCollection
>(
  _ expected: Array<Element>, _ collection: C,

  _ message: @autoclosure () -> String = "",
  stackTrace: SourceLocStack = SourceLocStack(),
  showFrame: Bool = true,
  file: String = #file, line: UInt = #line,
  resiliencyChecks: CollectionMisuseResiliencyChecks = .all,
  sameValue: (Element, Element) -> Bool
) where C.Element == Element {

  // A `Collection` is a multi-pass `Sequence`.
  for _ in 0..<3 {
    checkSequence(
      expected, collection, message(),
      stackTrace: stackTrace.pushIf(showFrame, file: file, line: line),
      resiliencyChecks: resiliencyChecks, sameValue: sameValue)
  }

  //===------------------------------------------------------------------===//
  // Check Index semantics
  //===------------------------------------------------------------------===//

  let succ = { collection.index(after: $0) }
  // Advances up to 1 positions without passing endIndex.  Don't use
  // advanced(by: n) to do this because it's under test here.
  let next = { $0 == collection.endIndex ? $0 : succ($0) }

  // advances up to 5 positions without passing endIndex.  Picking a
  // small constant to avoid complexity explosion on large input
  // collections.
  let next5 = { next(next(next(next(next($0))))) }

  let partWay0 = next5(collection.startIndex)
  let partWay1 = next5(partWay0)

  typealias Distance = Int

  let count: Distance  = collection.count
  let offset0 = min(5, count)
  let offset1 = min(10, count)

  let distanceCandidates: [Distance] = [
    -11, -7, -5, -3, -2, -1, 0, 1, 2, 3, 5, 7, 11]

  let distances = distanceCandidates.filter { (x: Distance) -> Bool in
    x + offset0 >= 0 && x + offset1 <= count
  }

  func nextN(_ n: Distance, _ i: C.Index) -> C.Index {
    return collection.index(i, offsetBy: n)
  }

  let instances = _allIndices(into: collection, in: partWay0..<partWay1)

  checkRandomAccessIndex(
    instances,
    distances: distances,
    of: collection,
    distanceOracle: { (x:Int, y:Int) in y - x },
    advanceOracle: { x, y in nextN(distances[y], instances[x]) },
    startIndex: collection.startIndex,
    endIndex: next5(partWay1), message(),
    stackTrace: stackTrace.pushIf(showFrame, file: file, line: line))


  let expectedArray = Array(expected)

  // Check `count`.
  expectEqual(Int64(expectedArray.count), Int64(collection.count), message(),
    stackTrace: stackTrace.pushIf(showFrame, file: file, line: line))

  //===------------------------------------------------------------------===//
  // Check Iteration behavior.
  //===------------------------------------------------------------------===//

  for _ in 0..<3 {
    do {
      let startIndex = collection.startIndex
      let endIndex = collection.endIndex

      for _ in collection.indices {
        expectEqual(
          startIndex, collection.startIndex,
          "Iteration should not change startIndex",
          stackTrace: stackTrace.pushIf(showFrame, file: file, line: line))

        expectEqual(
          endIndex, collection.endIndex,
          "Iteration should not change endIndex",
          stackTrace: stackTrace.pushIf(showFrame, file: file, line: line))
      }
    }

    let allIndices = Array(collection.indices)

    if expectedArray.count >= 2 {
      for i in 0..<allIndices.count-1 {
        let successor1 = succ(allIndices[i])
        var successor2 = allIndices[i]
        successor2 = succ(successor2)
        var successor3 = allIndices[i]
        successor3 = succ(successor3)
        for s in [ successor1, successor2, successor3 ] {
          expectEqual(allIndices[i + 1], s, message(),
            stackTrace: stackTrace.pushIf(showFrame, file: file, line: line))
          expectEqualTest(
            expectedArray[i + 1], collection[s], message(),
            stackTrace: stackTrace.pushIf(showFrame, file: file, line: line), sameValue: sameValue)
        }
      }


    } // end of `if expectedArray.count >= 2`

    do {
      var allIndices2: [C.Index] = []
      for i in collection.indices {
        allIndices2.append(i)
      }

      expectEqualSequence(
        allIndices, allIndices2, "iteration should not invalidate indices",
        stackTrace: stackTrace.pushIf(showFrame, file: file, line: line))

      expectEqualSequence(
        expectedArray, allIndices.map { collection[$0] },
        stackTrace: stackTrace.pushIf(showFrame, file: file, line: line), sameValue: sameValue)
      expectEqualSequence(
        expectedArray, allIndices2.map { collection[$0] },
        stackTrace: stackTrace.pushIf(showFrame, file: file, line: line), sameValue: sameValue)
    }
  } // end of `for _ in 0..<3`

  // FIXME: more checks for bidirectional and random access collections.
}

// Helper for checkRandomAccessCollection to check Slices.
//
// Checks all slices: O(n^2).
internal func _checkSliceableWithRandomAccessIndex<
Element, S : RandomAccessCollection
>(
  _ expected: Array<Element>, _ sliceable: S,
  _ message: @autoclosure () -> String = "",
  stackTrace: SourceLocStack = SourceLocStack(),
  showFrame: Bool = true,
  file: String = #file, line: UInt = #line,
  resiliencyChecks: CollectionMisuseResiliencyChecks = .all,
  sameValue: (Element, Element) -> Bool
) where
  S.Element == Element {

  let expectedArray = Array(expected)

  let succ = { sliceable.index(after: $0) }
  let pred = { sliceable.index(before: $0) }

  var start = sliceable.startIndex
  for startNumericIndex in 0...expectedArray.count {
    if start != sliceable.endIndex {
      start = succ(start)
      start = pred(start)
      start = succ(start)
      start = pred(start)
    }
    var end = start
    for endNumericIndex in startNumericIndex...expectedArray.count {
      if end != sliceable.endIndex {
        end = succ(end)
        end = pred(end)
        end = succ(end)
        end = pred(end)
      }
      let expectedSlice = expectedArray[startNumericIndex..<endNumericIndex]
      let slice = sliceable[start..<end]
      // For every possible slice, verify that the slice's bounds are identical
      // to the indices used to form the slice.
      expectEqual(start, slice.startIndex)
      expectEqual(end, slice.endIndex)

      checkOneLevelOfRandomAccessCollection(expectedSlice, slice, message(),
        stackTrace: stackTrace.pushIf(showFrame, file: file, line: line),
        resiliencyChecks: resiliencyChecks,
        sameValue: sameValue)

      if end != sliceable.endIndex {
        end = succ(end)
      }
    }
    if start != sliceable.endIndex {
      start = succ(start)
    }
  }
}



// Check RangeReplaceableCollection using a factory.
//
// Note: This does not invoke other collection tests.
public func checkRangeReplaceable<C, N>(
  _ makeCollection: @escaping () -> C,
  _ makeNewValues: (Int) -> N
) where
  C : RangeReplaceableCollection,
  N : Collection,
  C.Element : Equatable,
  C.Element == N.Element {

  typealias A = C

  // First make an independent copy of the array that we can use for
  // comparison later.
  let source = Array<A.Element>(makeCollection())

  for (ix, i) in source.indices.enumerated() {
    for (jx_, _) in (i..<source.endIndex).enumerated() {
      let jx = jx_ + ix

      let oldCount = jx - ix
      for newCount in 0..<(2 * oldCount) {
        let newValues = makeNewValues(newCount)

        func reportFailure(_ a: inout A, _ message: String) {
          print("\(message) when replacing indices \(ix)...\(jx)")
          print("  in \(Array(source)) with \(Array(newValues))")
          print("  yielding \(Array(a))")
          print("====================================")
          expectTrue(false)
        }

        var a = makeCollection()

        a.replaceSubrange(nthIndex(a, ix)..<nthIndex(a, jx), with: newValues)
        let growth = newCount - oldCount

        let expectedCount = source.count + growth
        let actualCount = a.count
        if actualCount != expectedCount {
          reportFailure(
            &a, "\(actualCount) != expected count \(expectedCount)")
        }

        for (kx, k) in a.indices.enumerated() {
          let expectedValue = kx < ix ? nth(source, kx)
          : kx < jx + growth ? nth(newValues, kx - ix)
          : nth(source, kx - growth)

          if a[k] != expectedValue {
            reportFailure(
              &a,
              // FIXME: why do we need to break this string into two parts?
              "a[\(kx)] = "
              + "\(a[k]) != expected value \(expectedValue)")
          }
        }
      }
    }
  }
}