stdlib/private/StdlibCollectionUnittest/CheckCollectionInstance.swift.gyb - third_party/swift - Git at Google

 //===--- CheckCollectionInstance.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_unittest_support import TRACE, stackTrace, trace
 from gyb_stdlib_support import TRAVERSALS, collectionForTraversal
 }%

 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)
   }
 }

 % for inc, protocol, direction, end in (
 %  ('inc', 'Collection', 'after', 'end'),
 %  ('dec', 'BidirectionalCollection', 'before', 'start')):

 /// Test that the elements of `instances` satisfy
 /// ${'some of ' if inc == 'dec' else ''}the semantic
 /// requirements of `${protocol}`, using `equalityOracle` to
 /// generate equality expectations from pairs of positions in
 /// `instances`.
 ///
 /// - Precondition: ${'''`endIndex` is reachable from all
 ///   elements of `instances`.''' if inc == 'inc' else '''all
 ///   elements of `instances` are reachable from `startIndex`.'''}
 public func check${inc.capitalize()}rementable<Instances, BaseCollection>(
   _ instances: Instances,
   of baseCollection: BaseCollection,
   equalityOracle: (Instances.Index, Instances.Index) -> Bool,
   ${end}Index: Instances.Element, ${TRACE}
 ) where
   Instances : Collection,
   BaseCollection : ${protocol},
   Instances.Element == BaseCollection.Index {

   checkEquatable(instances, oracle: equalityOracle, ${trace})
   for i in instances {
     if i != ${end}Index {
       let next = baseCollection.index(${direction}: i)
       // index(${direction}:) gets us a new index value
       expectNotEqual(i, next, ${trace})

       // Which is the same as if we apply formIndex(${direction}:)
       var j = i
       baseCollection.formIndex(${direction}: &j)
       expectEqual(j, next, ${trace})
     }
   }
 }
 %end

 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,
   ${TRACE}
 ) 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, ${trace})
       }
       expectEqual(jAtLimit ? j : next(j), k, ${trace})
       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, ${TRACE}
 ) where
   Instances : Collection,
   BaseCollection : Collection,
   Instances.Element == BaseCollection.Index {

   checkIncrementable(instances, of: baseCollection,
     equalityOracle: equalityOracle, endIndex: endIndex, ${trace})

   _checkIncrementalAdvance(instances, of: baseCollection,
     equalityOracle: equalityOracle, limit: endIndex,
     sign: 1, next: { baseCollection.index(after: $0) }, ${trace})
 }

 /// 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,
   ${TRACE}
 ) 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, ${trace})

   _checkIncrementalAdvance(instances, of: baseCollection,
     equalityOracle: equalityOracle, limit: startIndex,
     sign: -1, next: { baseCollection.index(before: $0) }, ${trace})
 }

 /// 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.Iterator.Element,
   endIndex: Instances.Iterator.Element,
   ${TRACE}
 ) 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, ${trace})

   checkAdvancesAndDistances(
     instances, distances: distances,
     of: baseCollection,
     distanceOracle: distanceOracle,
     advanceOracle: advanceOracle, ${trace})
 }

 // 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,
   ${TRACE}
 ) 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
     },
     ${trace})

   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.
 % for genericParam, Element, Expected in [
 %   ('Expected: Collection',  'Expected.Element',  'Expected'),
 %   ('Element'             ,  'Element'                  ,  'Array<Element>')]:

 // Top-level check for Collection instances. Alias for checkForwardCollection.
 // Checks all slices: O(n^2).
 public func checkCollection<${genericParam}, C : Collection>(
   _ expected: ${Expected},
   _ collection: C,
   ${TRACE},
   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)
 }

 %   for Traversal in TRAVERSALS:
 %     TraversalCollection = collectionForTraversal(Traversal)

 // Calls check${Traversal}Collection with default `sameValue`.
 public func check${Traversal}Collection<
   ${genericParam}, C : ${TraversalCollection}
 >(
   _ expected: ${Expected}, _ collection: C,
   ${TRACE},
   resiliencyChecks: CollectionMisuseResiliencyChecks = .all
 ) where
   C.Element == ${Element},
   ${Element} : Equatable {

   check${Traversal}Collection(
     expected, collection, ${trace},
     resiliencyChecks: resiliencyChecks) { $0 == $1 }
 }

 // Top-Level check for all ${TraversalCollection} semantics on a single
 // instance. This constrains SubSequence associated types in order to check
 // slice semantics.
 // Checks all slices: O(n^2).
 public func check${Traversal}Collection<
   ${genericParam}, C : ${TraversalCollection}
 >(
   _ expected: ${Expected}, _ collection: C,
   ${TRACE},
   resiliencyChecks: CollectionMisuseResiliencyChecks = .all,
   sameValue: (${Element}, ${Element}) -> Bool
 ) where
   C.Element == ${Element} {

   checkOneLevelOf${Traversal}Collection(expected, collection, ${trace},
     resiliencyChecks: resiliencyChecks, sameValue: sameValue)

   // Avoid validation of all possible (n^2) slices on large collection.
   // Test cases should call checkOneLevelOf${Traversal}Collection instead.
   expectLT(expected.count, 30)

   _checkSliceableWith${Traversal}Index(expected, collection, ${trace},
     resiliencyChecks: resiliencyChecks, sameValue: sameValue)
 }

 // Helper for check${Traversal}Collection. Check that instance of `C`,
 // `collection`, upholds the semantics of `${TraversalCollection}`,
 // 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 checkOneLevelOf${Traversal}Collection<
   ${genericParam}, C : ${TraversalCollection}
 >(
   _ expected: ${Expected}, _ collection: C,
   ${TRACE},
   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, ${trace},
       resiliencyChecks: resiliencyChecks, sameValue: sameValue)
   }

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

   let succ = { collection.index(after: $0) }
 %     if Traversal != 'Forward':
   let pred = { collection.index(before: $0) }
 %     end
   // 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)

 %     if Traversal == 'Forward':

   let instances = _allIndices(into: collection,
     in: collection.startIndex..<partWay0)
   checkForwardIndex(instances, of: collection,
     equalityOracle: { $0 == $1 }, endIndex: partWay1, ${trace})

 %     elif Traversal == 'Bidirectional':

   let instances = _allIndices(into: collection, in: partWay0..<partWay1)
   checkBidirectionalIndex(instances, of: collection,
     equalityOracle: { $0 == $1 },
     startIndex: collection.startIndex,
     endIndex: next5(partWay1), ${trace})

 %     else:
 %       assert(Traversal == 'RandomAccess')
   typealias Distance = Int

   let count: Distance  = collection.count
   let offset0 = min(5, count)
   let offset1 = min(10, count)
   let offset2 = min(15, 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 numericCast(y - x) },
     advanceOracle: { x, y in nextN(distances[y], instances[x]) },
     startIndex: collection.startIndex,
     endIndex: next5(partWay1), ${trace})

 %     end

   let expectedArray = Array(expected)

   // Check `count`.
   expectEqual(Int64(expectedArray.count), Int64(collection.count), ${trace})

   //===------------------------------------------------------------------===//
   // 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})

         expectEqual(
           endIndex, collection.endIndex,
           "Iteration should not change endIndex",
           stackTrace: ${stackTrace})
       }
     }

     var 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, ${trace})
           expectEqualTest(
             expectedArray[i + 1], collection[s], ${trace}, sameValue: sameValue)
         }
       }

 %       if Traversal == "Bidirectional":

       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, ${trace})
           expectEqualTest(
             expectedArray[i - 1], collection[p], ${trace}, sameValue: sameValue)
         }
       }
       for i in 1..<allIndices.count {
         let index = succ(pred(allIndices[i]))
         expectEqual(allIndices[i], index, ${trace})
         expectEqualTest(
           expectedArray[i], collection[index], ${trace}, sameValue: sameValue)
       }

 %       end # Traversal == "Bidirectional"

     } // 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})

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

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

 // Helper for check${Traversal}Collection to check Slices.
 //
 // Checks all slices: O(n^2).
 internal func _checkSliceableWith${Traversal}Index<
 ${genericParam}, S : ${TraversalCollection}
 >(
   _ expected: ${Expected}, _ sliceable: S, ${TRACE},
   resiliencyChecks: CollectionMisuseResiliencyChecks = .all,
   sameValue: (${Element}, ${Element}) -> Bool
 ) where
   S.Element == ${Element} {

   let expectedArray = Array(expected)

   let succ = { sliceable.index(after: $0) }
 %       if Traversal != "Forward":
   let pred = { sliceable.index(before: $0) }
 %       end

   var start = sliceable.startIndex
   for startNumericIndex in 0...expectedArray.count {
 %       if Traversal != "Forward":
     if start != sliceable.endIndex {
       start = succ(start)
       start = pred(start)
       start = succ(start)
       start = pred(start)
     }
 %       end
     var end = start
     for endNumericIndex in startNumericIndex...expectedArray.count {
 %       if Traversal != "Forward":
       if end != sliceable.endIndex {
         end = succ(end)
         end = pred(end)
         end = succ(end)
         end = pred(end)
       }
 %       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)

       checkOneLevelOf${Traversal}Collection(expectedSlice, slice, ${trace},
         resiliencyChecks: resiliencyChecks,
         sameValue: sameValue)

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

 %   end # Traversal

 % end # genericParam, Elements, Expected

 // 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_, j) 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 = numericCast(a.count) as Int
         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)")
           }
         }
       }
     }
   }
 }
	//===--- CheckCollectionInstance.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_unittest_support import TRACE, stackTrace, trace
	from gyb_stdlib_support import TRAVERSALS, collectionForTraversal
	}%

	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)
	}
	}

	% for inc, protocol, direction, end in (
	% ('inc', 'Collection', 'after', 'end'),
	% ('dec', 'BidirectionalCollection', 'before', 'start')):

	/// Test that the elements of `instances` satisfy
	/// ${'some of ' if inc == 'dec' else ''}the semantic
	/// requirements of `${protocol}`, using `equalityOracle` to
	/// generate equality expectations from pairs of positions in
	/// `instances`.
	///
	/// - Precondition: ${'''`endIndex` is reachable from all
	/// elements of `instances`.''' if inc == 'inc' else '''all
	/// elements of `instances` are reachable from `startIndex`.'''}
	public func check${inc.capitalize()}rementable<Instances, BaseCollection>(
	_ instances: Instances,
	of baseCollection: BaseCollection,
	equalityOracle: (Instances.Index, Instances.Index) -> Bool,
	${end}Index: Instances.Element, ${TRACE}
	) where
	Instances : Collection,
	BaseCollection : ${protocol},
	Instances.Element == BaseCollection.Index {

	checkEquatable(instances, oracle: equalityOracle, ${trace})
	for i in instances {
	if i != ${end}Index {
	let next = baseCollection.index(${direction}: i)
	// index(${direction}:) gets us a new index value
	expectNotEqual(i, next, ${trace})

	// Which is the same as if we apply formIndex(${direction}:)
	var j = i
	baseCollection.formIndex(${direction}: &j)
	expectEqual(j, next, ${trace})
	}
	}
	}
	%end

	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,
	${TRACE}
	) 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, ${trace})
	}
	expectEqual(jAtLimit ? j : next(j), k, ${trace})
	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, ${TRACE}
	) where
	Instances : Collection,
	BaseCollection : Collection,
	Instances.Element == BaseCollection.Index {

	checkIncrementable(instances, of: baseCollection,
	equalityOracle: equalityOracle, endIndex: endIndex, ${trace})

	_checkIncrementalAdvance(instances, of: baseCollection,
	equalityOracle: equalityOracle, limit: endIndex,
	sign: 1, next: { baseCollection.index(after: $0) }, ${trace})
	}

	/// 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,
	${TRACE}
	) 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, ${trace})

	_checkIncrementalAdvance(instances, of: baseCollection,
	equalityOracle: equalityOracle, limit: startIndex,
	sign: -1, next: { baseCollection.index(before: $0) }, ${trace})
	}

	/// 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.Iterator.Element,
	endIndex: Instances.Iterator.Element,
	${TRACE}
	) 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, ${trace})

	checkAdvancesAndDistances(
	instances, distances: distances,
	of: baseCollection,
	distanceOracle: distanceOracle,
	advanceOracle: advanceOracle, ${trace})
	}

	// 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,
	${TRACE}
	) 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
	},
	${trace})

	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.
	% for genericParam, Element, Expected in [
	% ('Expected: Collection', 'Expected.Element', 'Expected'),
	% ('Element' , 'Element' , 'Array<Element>')]:

	// Top-level check for Collection instances. Alias for checkForwardCollection.
	// Checks all slices: O(n^2).
	public func checkCollection<${genericParam}, C : Collection>(
	_ expected: ${Expected},
	_ collection: C,
	${TRACE},
	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)
	}

	% for Traversal in TRAVERSALS:
	% TraversalCollection = collectionForTraversal(Traversal)

	// Calls check${Traversal}Collection with default `sameValue`.
	public func check${Traversal}Collection<
	${genericParam}, C : ${TraversalCollection}
	>(
	_ expected: ${Expected}, _ collection: C,
	${TRACE},
	resiliencyChecks: CollectionMisuseResiliencyChecks = .all
	) where
	C.Element == ${Element},
	${Element} : Equatable {

	check${Traversal}Collection(
	expected, collection, ${trace},
	resiliencyChecks: resiliencyChecks) { $0 == $1 }
	}

	// Top-Level check for all ${TraversalCollection} semantics on a single
	// instance. This constrains SubSequence associated types in order to check
	// slice semantics.
	// Checks all slices: O(n^2).
	public func check${Traversal}Collection<
	${genericParam}, C : ${TraversalCollection}
	>(
	_ expected: ${Expected}, _ collection: C,
	${TRACE},
	resiliencyChecks: CollectionMisuseResiliencyChecks = .all,
	sameValue: (${Element}, ${Element}) -> Bool
	) where
	C.Element == ${Element} {

	checkOneLevelOf${Traversal}Collection(expected, collection, ${trace},
	resiliencyChecks: resiliencyChecks, sameValue: sameValue)

	// Avoid validation of all possible (n^2) slices on large collection.
	// Test cases should call checkOneLevelOf${Traversal}Collection instead.
	expectLT(expected.count, 30)

	_checkSliceableWith${Traversal}Index(expected, collection, ${trace},
	resiliencyChecks: resiliencyChecks, sameValue: sameValue)
	}

	// Helper for check${Traversal}Collection. Check that instance of `C`,
	// `collection`, upholds the semantics of `${TraversalCollection}`,
	// 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 checkOneLevelOf${Traversal}Collection<
	${genericParam}, C : ${TraversalCollection}
	>(
	_ expected: ${Expected}, _ collection: C,
	${TRACE},
	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, ${trace},
	resiliencyChecks: resiliencyChecks, sameValue: sameValue)
	}

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

	let succ = { collection.index(after: $0) }
	% if Traversal != 'Forward':
	let pred = { collection.index(before: $0) }
	% end
	// 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)

	% if Traversal == 'Forward':

	let instances = _allIndices(into: collection,
	in: collection.startIndex..<partWay0)
	checkForwardIndex(instances, of: collection,
	equalityOracle: { $0 == $1 }, endIndex: partWay1, ${trace})

	% elif Traversal == 'Bidirectional':

	let instances = _allIndices(into: collection, in: partWay0..<partWay1)
	checkBidirectionalIndex(instances, of: collection,
	equalityOracle: { $0 == $1 },
	startIndex: collection.startIndex,
	endIndex: next5(partWay1), ${trace})

	% else:
	% assert(Traversal == 'RandomAccess')
	typealias Distance = Int

	let count: Distance = collection.count
	let offset0 = min(5, count)
	let offset1 = min(10, count)
	let offset2 = min(15, 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 numericCast(y - x) },
	advanceOracle: { x, y in nextN(distances[y], instances[x]) },
	startIndex: collection.startIndex,
	endIndex: next5(partWay1), ${trace})

	% end

	let expectedArray = Array(expected)

	// Check `count`.
	expectEqual(Int64(expectedArray.count), Int64(collection.count), ${trace})

	//===------------------------------------------------------------------===//
	// 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})

	expectEqual(
	endIndex, collection.endIndex,
	"Iteration should not change endIndex",
	stackTrace: ${stackTrace})
	}
	}

	var 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, ${trace})
	expectEqualTest(
	expectedArray[i + 1], collection[s], ${trace}, sameValue: sameValue)
	}
	}

	% if Traversal == "Bidirectional":

	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, ${trace})
	expectEqualTest(
	expectedArray[i - 1], collection[p], ${trace}, sameValue: sameValue)
	}
	}
	for i in 1..<allIndices.count {
	let index = succ(pred(allIndices[i]))
	expectEqual(allIndices[i], index, ${trace})
	expectEqualTest(
	expectedArray[i], collection[index], ${trace}, sameValue: sameValue)
	}

	% end # Traversal == "Bidirectional"

	} // 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})

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

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

	// Helper for check${Traversal}Collection to check Slices.
	//
	// Checks all slices: O(n^2).
	internal func _checkSliceableWith${Traversal}Index<
	${genericParam}, S : ${TraversalCollection}
	>(
	_ expected: ${Expected}, _ sliceable: S, ${TRACE},
	resiliencyChecks: CollectionMisuseResiliencyChecks = .all,
	sameValue: (${Element}, ${Element}) -> Bool
	) where
	S.Element == ${Element} {

	let expectedArray = Array(expected)

	let succ = { sliceable.index(after: $0) }
	% if Traversal != "Forward":
	let pred = { sliceable.index(before: $0) }
	% end

	var start = sliceable.startIndex
	for startNumericIndex in 0...expectedArray.count {
	% if Traversal != "Forward":
	if start != sliceable.endIndex {
	start = succ(start)
	start = pred(start)
	start = succ(start)
	start = pred(start)
	}
	% end
	var end = start
	for endNumericIndex in startNumericIndex...expectedArray.count {
	% if Traversal != "Forward":
	if end != sliceable.endIndex {
	end = succ(end)
	end = pred(end)
	end = succ(end)
	end = pred(end)
	}
	% 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)

	checkOneLevelOf${Traversal}Collection(expectedSlice, slice, ${trace},
	resiliencyChecks: resiliencyChecks,
	sameValue: sameValue)

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

	% end # Traversal

	% end # genericParam, Elements, Expected

	// 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_, j) 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 = numericCast(a.count) as Int
	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)")
	}
	}
	}
	}
	}
	}