SequenceType.swift.gyb

// -*- swift -*-
// RUN: rm -rf %t ; mkdir -p %t
// RUN: %S/../../utils/gyb %s -o %t/SequenceType.swift -D test_path="%S"
// RUN: %S/../../utils/line-directive %t/SequenceType.swift -- %target-build-swift %t/SequenceType.swift -o %t/a.out
// RUN: %S/../../utils/line-directive %t/SequenceType.swift -- %target-run %t/a.out
// REQUIRES: executable_test

% import gyb

import StdlibUnittest
import SwiftPrivate

// Extend LoggingSequence to shadow the new operation.  When
// requirements are added to a protocol 'P', there should be an
// implementation in 'InstrumentedP' that does some bookeeping for
// testing (like counting calls to the operation) and then dispatches
// to the same operation on its 'base' member.  InstrumentedSequence
// already contains implementations of all the SequenceType
// requirements.

var _nonCustomizableOperation = TypeIndexed(0)
extension SequenceLog {
  static var nonCustomizableOperation : TypeIndexed<Int> {
    get {return _nonCustomizableOperation}
    set {_nonCustomizableOperation = newValue}
  }
}

extension LoggingSequence {
  func nonCustomizableOperation() {
    ++Log.nonCustomizableOperation[self.dynamicType]
    return base.nonCustomizableOperation()
  }
}

// Add a non-customizable operation to sequence
extension SequenceType {
  func nonCustomizableOperation() {}
}

var SequenceTypeTests = TestSuite("SequenceType")

//===----------------------------------------------------------------------===//

// FIXME: add tests for:
//
// - Array, ContiguousArray and ArraySlice as inputs.  These types special-case
// a lot of collection behavior for performance reasons.  Not to even mention
// that these are important types to test in any case.
//
// - NaN behavior of floating point types, combined with these generic
// algorithms, should make sense if possible.  For example,
// [1.0, Double.NaN].startsWith([1.0, 2.0]) should be false.

//===----------------------------------------------------------------------===//
// minElement(), maxElement()
//===----------------------------------------------------------------------===//

% for algorithmKind in [ 'min', 'max' ]:
%   AlgorithmKind = algorithmKind.capitalize()

SequenceTypeTests.test("${algorithmKind}Element/WhereElementIsComparable") {
  for test in minMaxElementTests {
    let s = MinimalSequence<MinimalComparableValue>(
      elements: test.sequence.enumerate().map {
        MinimalComparableValue($1, identity: $0)
      })
    var maybeResult = s.${algorithmKind}Element()
    expectType(Optional<MinimalComparableValue>.self, &maybeResult)
    if let result = maybeResult {
      expectEqual(
        test.expected${AlgorithmKind}Value!, result.value,
        stackTrace: SourceLocStack().with(test.loc))
      expectEqual(
        test.expected${AlgorithmKind}Index!, result.identity,
        stackTrace: SourceLocStack().with(test.loc))
    } else {
      expectEmpty(
        test.expected${AlgorithmKind}Value,
        stackTrace: SourceLocStack().with(test.loc))
      expectEmpty(
        test.expected${AlgorithmKind}Index,
        stackTrace: SourceLocStack().with(test.loc))
    }
    expectEqual([], s.map { $0.value }, "sequence should be consumed")
  }
}

SequenceTypeTests.test("${algorithmKind}Element/Predicate") {
  for test in minMaxElementTests {
    let s = MinimalSequence<OpaqueValue<Int>>(
      elements: test.sequence.enumerate().map {
        OpaqueValue($1, identity: $0)
      })
    var timesClosureWasCalled = 0
    var maybeResult = s.${algorithmKind}Element {
      (lhs, rhs) -> Bool in
      ++timesClosureWasCalled
      return lhs.value < rhs.value
    }
    expectType(Optional<OpaqueValue<Int>>.self, &maybeResult)
    if let result = maybeResult {
      expectEqual(
        test.expected${AlgorithmKind}Value!, result.value,
        stackTrace: SourceLocStack().with(test.loc))
      expectEqual(
        test.expected${AlgorithmKind}Index!, result.identity,
        stackTrace: SourceLocStack().with(test.loc))
    } else {
      expectEmpty(
        test.expected${AlgorithmKind}Value,
        stackTrace: SourceLocStack().with(test.loc))
      expectEmpty(
        test.expected${AlgorithmKind}Index,
        stackTrace: SourceLocStack().with(test.loc))
    }
    expectEqual([], s.map { $0.value }, "sequence should be consumed")
    expectEqual(
      max(0, test.sequence.count - 1), timesClosureWasCalled,
      "maxElement() should be eager and should only call its predicate"
      + " once per element")
  }
}

% end


//===----------------------------------------------------------------------===//
// GeneratorSequence
//===----------------------------------------------------------------------===//

// Check that the generic parameter is called 'Base'.
protocol TestProtocol1 {}

extension GeneratorSequence where Base : TestProtocol1 {
  var _baseIsTestProtocol1: Bool {
    fatalError("not implemented")
  }
}

//===--- Demonstrate technique for testing generic dispatching ------------===//
// A counter we can use to record calls to our non-customizable operation

SequenceTypeTests.test("Demonstration/NotCustomizable") {
  let tester = SequenceLog.dispatchTester([OpaqueValue(1)])

  tester.nonCustomizableOperation()
  
  expectNotCustomizable(tester, tester.log.nonCustomizableOperation)
}

SequenceTypeTests.test("GeneratorSequence/GeneratorType/empty") {
  if true {
    let data: [OpaqueValue<Int>] = []
    let base = MinimalGenerator(data)
    var g = GeneratorSequence(base)
    expectType(
      GeneratorSequence<MinimalGenerator<OpaqueValue<Int>>>.self,
      &g)
    checkGenerator(data, g, resiliencyChecks: .none) { $0.value == $1.value }
  }
  if true {
    let data: [OpaqueValue<Int>] = []
    let base = data.generate()
    var g = GeneratorSequence(base)
    expectType(
      GeneratorSequence<IndexingGenerator<Array<OpaqueValue<Int>>>>.self,
      &g)
    checkGenerator(data, g) { $0.value == $1.value }
  }
}

SequenceTypeTests.test("GeneratorSequence/GeneratorType") {
  if true {
    let data: [OpaqueValue<Int>] = []
    let base = MinimalGenerator(data)
    var g = GeneratorSequence(base)
    expectType(
      GeneratorSequence<MinimalGenerator<OpaqueValue<Int>>>.self,
      &g)
    checkGenerator(data, g, resiliencyChecks: .none) { $0.value == $1.value }
  }
  if true {
    let data: [OpaqueValue<Int>] = []
    let base = data.generate()
    var g = GeneratorSequence(base)
    expectType(
      GeneratorSequence<IndexingGenerator<Array<OpaqueValue<Int>>>>.self,
      &g)
    checkGenerator(data, g) { $0.value == $1.value }
  }
}

SequenceTypeTests.test("GeneratorSequence/SequenceType/empty") {
  if true {
    let data = [ 10, 20, 30 ].map(OpaqueValue.init)
    let base = MinimalGenerator(data)
    var g = GeneratorSequence(base)
    expectType(
      GeneratorSequence<MinimalGenerator<OpaqueValue<Int>>>.self,
      &g)
    checkSequence(data, g, resiliencyChecks: .none) { $0.value == $1.value }
  }
  if true {
    let data = [ 10, 20, 30 ].map(OpaqueValue.init)
    let base = data.generate()
    var g = GeneratorSequence(base)
    expectType(
      GeneratorSequence<IndexingGenerator<Array<OpaqueValue<Int>>>>.self,
      &g)
    checkSequence(data, g) { $0.value == $1.value }
  }
}

SequenceTypeTests.test("GeneratorSequence/SequenceType") {
  if true {
    let data = [ 10, 20, 30 ].map(OpaqueValue.init)
    let base = MinimalGenerator(data)
    var g = GeneratorSequence(base)
    expectType(
      GeneratorSequence<MinimalGenerator<OpaqueValue<Int>>>.self,
      &g)
    checkSequence(data, g, resiliencyChecks: .none) { $0.value == $1.value }
  }
  if true {
    let data = [ 10, 20, 30 ].map(OpaqueValue.init)
    let base = data.generate()
    var g = GeneratorSequence(base)
    expectType(
      GeneratorSequence<IndexingGenerator<Array<OpaqueValue<Int>>>>.self,
      &g)
    checkSequence(data, g) { $0.value == $1.value }
  }
}

//===----------------------------------------------------------------------===//
// enumerate()
//===----------------------------------------------------------------------===//

// Check that the generic parameter is called 'Base'.
extension EnumerateGenerator where Base : TestProtocol1 {
  var _elementIsTestProtocol1: Bool {
    fatalError("not implemented")
  }
}

extension EnumerateSequence where Base : TestProtocol1 {
  var _elementIsTestProtocol1: Bool {
    fatalError("not implemented")
  }
}

SequenceTypeTests.test("enumerate") {
  typealias Element = (index: Int, element: OpaqueValue<Int>)
  func compareElements(lhs: Element, rhs: Element) -> Bool {
    return lhs.0 == rhs.0 && lhs.1.value == rhs.1.value
  }

  for test in enumerateTests {
    let s = MinimalSequence<OpaqueValue<Int>>(
      elements: test.sequence.map(OpaqueValue.init))
    var result = s.enumerate()
    expectType(
      EnumerateSequence<MinimalSequence<OpaqueValue<Int>>>.self,
      &result)
    
    checkSequence(
      test.expected.map {
        (index: $0.0, element: OpaqueValue($0.1))
      } as [Element],
      result,
      resiliencyChecks: .none, sameValue: compareElements)
    expectEqual([], s.map { $0.value }, "sequence should be consumed")
  }
}

//===----------------------------------------------------------------------===//
// startsWith()
//===----------------------------------------------------------------------===//

SequenceTypeTests.test("startsWith/WhereElementIsEquatable") {
  for test in startsWithTests {
    if true {
      let s = MinimalSequence<MinimalEquatableValue>(
        elements: test.sequence.map(MinimalEquatableValue.init))
      let prefix = MinimalSequence<MinimalEquatableValue>(
        elements: test.prefix.map(MinimalEquatableValue.init))
      expectEqual(
        test.expected,
        s.startsWith(prefix),
        stackTrace: SourceLocStack().with(test.loc))
      expectEqual(
        test.expectedLeftoverSequence, s.map { $0.value },
        stackTrace: SourceLocStack().with(test.loc))
      expectEqual(
        test.expectedLeftoverPrefix, prefix.map { $0.value },
        stackTrace: SourceLocStack().with(test.loc))
    }

    // Use different types for the sequence and prefix.
    if true {
      let s = MinimalForwardCollection<MinimalEquatableValue>(
        elements: test.sequence.map(MinimalEquatableValue.init))
      let prefix = MinimalSequence<MinimalEquatableValue>(
        elements: test.prefix.map(MinimalEquatableValue.init))
      expectEqual(
        test.expected,
        s.startsWith(prefix),
        stackTrace: SourceLocStack().with(test.loc))
      expectEqual(
        test.sequence, s.map { $0.value },
        stackTrace: SourceLocStack().with(test.loc))
      expectEqual(
        test.expectedLeftoverPrefix, prefix.map { $0.value },
        stackTrace: SourceLocStack().with(test.loc))
    }
  }
}

SequenceTypeTests.test("startsWith/Predicate") {
  for test in startsWithTests {
    if true {
      let s = MinimalSequence<OpaqueValue<Int>>(
        elements: test.sequence.map(OpaqueValue.init))
      let prefix = MinimalSequence<OpaqueValue<Int>>(
        elements: test.prefix.map(OpaqueValue.init))
      expectEqual(
        test.expected,
        s.startsWith(prefix) { $0.value == $1.value },
        stackTrace: SourceLocStack().with(test.loc))
      expectEqual(
        test.expectedLeftoverSequence, s.map { $0.value },
        stackTrace: SourceLocStack().with(test.loc))
      expectEqual(
        test.expectedLeftoverPrefix, prefix.map { $0.value },
        stackTrace: SourceLocStack().with(test.loc))
    }
    if true {
      let s = MinimalSequence<OpaqueValue<Int>>(
        elements: test.sequence.map { OpaqueValue($0 * 2) })
      let prefix = MinimalSequence<OpaqueValue<Int>>(
        elements: test.prefix.map(OpaqueValue.init))
      expectEqual(
        test.expected,
        s.startsWith(prefix) { $0.value / 2 == $1.value },
        stackTrace: SourceLocStack().with(test.loc))
      expectEqual(
        test.expectedLeftoverSequence, s.map { $0.value / 2 },
        stackTrace: SourceLocStack().with(test.loc))
      expectEqual(
        test.expectedLeftoverPrefix, prefix.map { $0.value },
        stackTrace: SourceLocStack().with(test.loc))
    }

    // Use different types for the sequence and prefix.
    if true {
      let s = MinimalForwardCollection<OpaqueValue<Int>>(
        elements: test.sequence.map(OpaqueValue.init))
      let prefix = MinimalSequence<OpaqueValue<Int>>(
        elements: test.prefix.map(OpaqueValue.init))
      expectEqual(
        test.expected,
        s.startsWith(prefix) { $0.value == $1.value },
        stackTrace: SourceLocStack().with(test.loc))
      expectEqual(
        test.sequence, s.map { $0.value },
        stackTrace: SourceLocStack().with(test.loc))
      expectEqual(
        test.expectedLeftoverPrefix, prefix.map { $0.value },
        stackTrace: SourceLocStack().with(test.loc))
    }
  }
}

//===----------------------------------------------------------------------===//
// equal()
//===----------------------------------------------------------------------===//

SequenceTypeTests.test("elementsEqual/WhereElementIsEquatable") {
  for test in elementsEqualTests {
    if true {
      let s = MinimalSequence<MinimalEquatableValue>(
        elements: test.sequence.map(MinimalEquatableValue.init))
      let other = MinimalSequence<MinimalEquatableValue>(
        elements: test.other.map(MinimalEquatableValue.init))
      expectEqual(
        test.expected,
        s.elementsEqual(other),
        stackTrace: SourceLocStack().with(test.loc))
      expectEqual(
        test.expectedLeftoverSequence, s.map { $0.value },
        stackTrace: SourceLocStack().with(test.loc))
      expectEqual(
        test.expectedLeftoverOther, other.map { $0.value },
        stackTrace: SourceLocStack().with(test.loc))
    }

    // Use different types for the sequence and other.
    if true {
      let s = MinimalForwardCollection<MinimalEquatableValue>(
        elements: test.sequence.map(MinimalEquatableValue.init))
      let other = MinimalSequence<MinimalEquatableValue>(
        elements: test.other.map(MinimalEquatableValue.init))
      expectEqual(
        test.expected,
        s.elementsEqual(other),
        stackTrace: SourceLocStack().with(test.loc))
      expectEqual(
        test.sequence, s.map { $0.value },
        stackTrace: SourceLocStack().with(test.loc))
      expectEqual(
        test.expectedLeftoverOther, other.map { $0.value },
        stackTrace: SourceLocStack().with(test.loc))
    }
  }
}

SequenceTypeTests.test("elementsEqual/Predicate") {
  for test in elementsEqualTests {
    if true {
      let s = MinimalSequence<OpaqueValue<Int>>(
        elements: test.sequence.map(OpaqueValue.init))
      let other = MinimalSequence<OpaqueValue<Int>>(
        elements: test.other.map(OpaqueValue.init))
      expectEqual(
        test.expected,
        s.elementsEqual(other) { $0.value == $1.value },
        stackTrace: SourceLocStack().with(test.loc))
      expectEqual(
        test.expectedLeftoverSequence, s.map { $0.value },
        stackTrace: SourceLocStack().with(test.loc))
      expectEqual(
        test.expectedLeftoverOther, other.map { $0.value },
        stackTrace: SourceLocStack().with(test.loc))
    }

    // Use different types for the sequence and other.
    if true {
      let s = MinimalForwardCollection<OpaqueValue<Int>>(
        elements: test.sequence.map(OpaqueValue.init))
      let other = MinimalSequence<OpaqueValue<Int>>(
        elements: test.other.map(OpaqueValue.init))
      expectEqual(
        test.expected,
        s.elementsEqual(other) { $0.value == $1.value },
        stackTrace: SourceLocStack().with(test.loc))
      expectEqual(
        test.sequence, s.map { $0.value },
        stackTrace: SourceLocStack().with(test.loc))
      expectEqual(
        test.expectedLeftoverOther, other.map { $0.value },
        stackTrace: SourceLocStack().with(test.loc))
    }
  }
}

//===----------------------------------------------------------------------===//
// lexicographicalCompare()
//===----------------------------------------------------------------------===//

SequenceTypeTests.test("lexicographicalCompare/WhereElementIsComparable") {
  for test in lexicographicalCompareTests {
    if true {
      let s = MinimalSequence<MinimalComparableValue>(
        elements: test.sequence.map(MinimalComparableValue.init))
      let other = MinimalSequence<MinimalComparableValue>(
        elements: test.other.map(MinimalComparableValue.init))
      expectEqual(
        test.expected.isLT(),
        s.lexicographicalCompare(other),
        stackTrace: SourceLocStack().with(test.loc))
      expectEqual(
        test.expectedLeftoverSequence, s.map { $0.value },
        stackTrace: SourceLocStack().with(test.loc))
      expectEqual(
        test.expectedLeftoverOther, other.map { $0.value },
        stackTrace: SourceLocStack().with(test.loc))
    }

    // Use different types for the sequence and other.
    if true {
      let s = MinimalForwardCollection<MinimalComparableValue>(
        elements: test.sequence.map(MinimalComparableValue.init))
      let other = MinimalSequence<MinimalComparableValue>(
        elements: test.other.map(MinimalComparableValue.init))
      expectEqual(
        test.expected.isLT(),
        s.lexicographicalCompare(other),
        stackTrace: SourceLocStack().with(test.loc))
      expectEqual(
        test.sequence, s.map { $0.value },
        stackTrace: SourceLocStack().with(test.loc))
      expectEqual(
        test.expectedLeftoverOther, other.map { $0.value },
        stackTrace: SourceLocStack().with(test.loc))
    }
  }
}

SequenceTypeTests.test("lexicographicalCompare/Predicate") {
  for test in lexicographicalCompareTests {
    if true {
      let s = MinimalSequence<OpaqueValue<Int>>(
        elements: test.sequence.map(OpaqueValue.init))
      let other = MinimalSequence<OpaqueValue<Int>>(
        elements: test.other.map(OpaqueValue.init))
      expectEqual(
        test.expected.isLT(),
        s.lexicographicalCompare(other) { $0.value < $1.value },
        stackTrace: SourceLocStack().with(test.loc))
      expectEqual(
        test.expectedLeftoverSequence, s.map { $0.value },
        stackTrace: SourceLocStack().with(test.loc))
      expectEqual(
        test.expectedLeftoverOther, other.map { $0.value },
        stackTrace: SourceLocStack().with(test.loc))
    }

    // Use different types for the sequence and other.
    if true {
      let s = MinimalForwardCollection<OpaqueValue<Int>>(
        elements: test.sequence.map(OpaqueValue.init))
      let other = MinimalSequence<OpaqueValue<Int>>(
        elements: test.other.map(OpaqueValue.init))
      expectEqual(
        test.expected.isLT(),
        s.lexicographicalCompare(other) { $0.value < $1.value },
        stackTrace: SourceLocStack().with(test.loc))
      expectEqual(
        test.sequence, s.map { $0.value },
        stackTrace: SourceLocStack().with(test.loc))
      expectEqual(
        test.expectedLeftoverOther, other.map { $0.value },
        stackTrace: SourceLocStack().with(test.loc))
    }
  }
}

//===----------------------------------------------------------------------===//
// contains()
//===----------------------------------------------------------------------===//

typealias StrictSequenceOfEquatable = MinimalSequence<MinimalEquatableValue>

// FIXME: rename in StdlibUnittest
// typealias StrictSequence = MinimalSequence

SequenceTypeTests.test("contains/WhereElementIsEquatable/dispatch") {
  let tester = SequenceLog.dispatchTester([MinimalEquatableValue(1)])
  _ = tester.contains(MinimalEquatableValue(1))
  expectCustomizable(tester, tester.log._customContainsEquatableElement)
}

func callStaticContains(
  set: Set<MinimalHashableValue>,
  _ element: MinimalHashableValue
) -> Bool {
  return set.contains(element)
}

func callGenericContains<
  S : SequenceType where S.Generator.Element : Equatable
>(sequence: S, _ element: S.Generator.Element) -> Bool {
  return sequence.contains(element)
}

% for dispatch in [ 'Static', 'Generic' ]:

// FIXME: implement the same optimization for Dictionary.
// FIXME: move to the file where other Set tests live.
SequenceTypeTests.test("Set<T>.contains/CustomImplementation/${dispatch}") {
  for test in findTests {
    let s = Set<MinimalHashableValue>(
      test.sequence.map { MinimalHashableValue($0.value) })
    MinimalHashableValue.timesEqualEqualWasCalled = 0
    MinimalHashableValue.timesHashValueWasCalled = 0
    expectEqual(
      test.expected != nil,
      call${dispatch}Contains(s, MinimalHashableValue(test.element.value)),
      stackTrace: SourceLocStack().with(test.loc))
    if test.sequence.isEmpty {
      expectEqual(
        0, MinimalHashableValue.timesEqualEqualWasCalled,
        stackTrace: SourceLocStack().with(test.loc))
      expectEqual(
        0, MinimalHashableValue.timesHashValueWasCalled,
        stackTrace: SourceLocStack().with(test.loc))
    } else {
      expectNotEqual(
        0, MinimalHashableValue.timesHashValueWasCalled,
        stackTrace: SourceLocStack().with(test.loc))
    }
    if test.expected != nil {
      expectNotEqual(
        0, MinimalHashableValue.timesEqualEqualWasCalled,
        stackTrace: SourceLocStack().with(test.loc))
    }
  }
}

% end

SequenceTypeTests.test("contains/Predicate") {
  for test in findTests {
    let s = MinimalSequence<OpaqueValue<Int>>(
      elements: test.sequence.map { OpaqueValue($0.value) })
    expectEqual(
      test.expected != nil,
      s.contains { $0.value == test.element.value },
      stackTrace: SourceLocStack().with(test.loc))
    expectEqual(
      test.expectedLeftoverSequence.map { $0.value }, s.map { $0.value },
      stackTrace: SourceLocStack().with(test.loc))
  }
}

//===----------------------------------------------------------------------===//
// reduce()
//===----------------------------------------------------------------------===//

SequenceTypeTests.test("reduce") {
  for test in reduceTests {
    let s = MinimalSequence<OpaqueValue<Int>>(
      elements: test.sequence.map(OpaqueValue.init))
    var timesClosureWasCalled = 0
    let result = s.reduce(OpaqueValue<[Int]>([])) {
      (partialResult: OpaqueValue<[Int]>, element: OpaqueValue<Int>)
        -> OpaqueValue<[Int]> in
      ++timesClosureWasCalled
      return OpaqueValue<[Int]>(partialResult.value + [ element.value ])
    }
    expectEqual(test.sequence, result.value)
    expectEqual([], s.map { $0.value }, "sequence should be consumed")
    expectEqual(
      test.sequence.count, timesClosureWasCalled,
      "reduce() should be eager and should only call its predicate"
      + "once per element")
  }
}

//===----------------------------------------------------------------------===//
// reverse()
//===----------------------------------------------------------------------===//

SequenceTypeTests.test("reverse/SequenceType") {
  for test in reverseTests {
    let s = MinimalSequence<OpaqueValue<Int>>(
      elements: test.sequence.map(OpaqueValue.init))
    var result = s.reverse()
    expectType([OpaqueValue<Int>].self, &result)
    expectEqual(
      test.expected, result.map { $0.value },
      stackTrace: SourceLocStack().with(test.loc))
    expectEqual([], s.map { $0.value }, "sequence should be consumed")
  }
}

SequenceTypeTests.test("reverse/WhereIndexIsBidirectional,BidirectionalReverseView") {
  for test in reverseTests {
    let s = MinimalBidirectionalCollection<OpaqueValue<Int>>(
      elements: test.sequence.map(OpaqueValue.init))
    var result = s.reverse()
    expectType(
      ReverseCollection<MinimalBidirectionalCollection<OpaqueValue<Int>>>.self,
      &result)
    expectEqual(
      test.expected, result.map { $0.value },
      stackTrace: SourceLocStack().with(test.loc))

    // Check ReverseCollection's CollectionType conformance.
    checkBidirectionalCollection(
      test.expected.map(OpaqueValue.init) as [OpaqueValue<Int>],
      result) { $0.value == $1.value }
  }
}

SequenceTypeTests.test("reverse/WhereIndexIsRandomAccess,RandomAccessReverseView") {
  for test in reverseTests {
    let s = MinimalRandomAccessCollection<OpaqueValue<Int>>(
      elements: test.sequence.map(OpaqueValue.init))
    var result = s.reverse()
    expectType(
      ReverseRandomAccessCollection<MinimalRandomAccessCollection<OpaqueValue<Int>>>.self,
      &result)
    expectEqual(
      test.expected, result.map { $0.value },
      stackTrace: SourceLocStack().with(test.loc))

    // Check ReverseRandomAccessCollection CollectionType conformance.
    checkRandomAccessCollection(
      test.expected.map(OpaqueValue.init) as [OpaqueValue<Int>],
      result) { $0.value == $1.value }

  }
}

//===----------------------------------------------------------------------===//
// filter()
//===----------------------------------------------------------------------===//

SequenceTypeTests.test("filter/SequenceType/Dispatch") {
  let tester = SequenceLog.dispatchTester([OpaqueValue(1)])
  _ = tester.filter { _ in false }
  expectCustomizable(tester, tester.log.filter)
}

SequenceTypeTests.test("filter/SequenceType/Semantics") {
  for test in filterTests {
    for underestimateCountBehavior in [
      UnderestimateCountBehavior.Precise,
      UnderestimateCountBehavior.Half,
      UnderestimateCountBehavior.Value(0)
    ] {
      
      let s = DefaultedSequence<OpaqueValue<Int>>(
        elements: test.sequence.map(OpaqueValue.init),
        underestimatedCount: underestimateCountBehavior)
      
      let closureLifetimeTracker = LifetimeTracked(0)
      expectEqual(1, LifetimeTracked.instances)
      var timesClosureWasCalled = 0
      var result = s.filter {
        (element) in
        _blackHole(closureLifetimeTracker)
        ++timesClosureWasCalled
        return test.includeElement(element.value)
      }
      expectType([OpaqueValue<Int>].self, &result)
      expectEqual(test.expected, result.map { $0.value })
      expectEqual([], s.map { $0.value }, "sequence should be consumed")
      expectEqual(
        test.sequence.count, timesClosureWasCalled,
        "filter() should be eager and should only call its predicate"
        + "once per element")
      expectGE(
        2 * result.count, result.capacity,
        "filter() should not reserve capacity (it does not know how much the"
        + "predicate will filter out)")
    }
  }
}

//===----------------------------------------------------------------------===//
// map()
//===----------------------------------------------------------------------===//

var MinimalSequenceWithCustomMap_timesMapWasCalled: Int = 0

% for Implementation in [ 'Default', 'Custom' ]:

struct MinimalSequenceWith${Implementation}Map<Element> : SequenceType {
  init(_ data: [Element], underestimatedCount: UnderestimateCountBehavior) {
    self._data = MinimalSequence(
      elements: data, underestimatedCount: underestimatedCount)
  }

  func generate() -> MinimalGenerator<Element> {
    return _data.generate()
  }

  var _data: MinimalSequence<Element>


%   if Implementation == 'Custom':

  static var timesMapWasCalled: Int {
    get {
      return MinimalSequenceWithCustomMap_timesMapWasCalled
    }
    set {
      MinimalSequenceWithCustomMap_timesMapWasCalled = newValue
    }
  }

  func map<T>(
    @noescape transform: (Element) throws -> T
  ) rethrows -> [T] {
    ++MinimalSequenceWithCustomMap.timesMapWasCalled
    return try _data.map(transform)
  }

%   end
}

% end

func callStaticSequenceMap<T>(
  sequence: MinimalSequenceWithDefaultMap<OpaqueValue<Int>>,
  @noescape transform: (OpaqueValue<Int>) -> T
) -> [T] {
  var result = sequence.map(transform)
  expectType([T].self, &result)
  return result
}

func callStaticSequenceMap<T>(
  sequence: MinimalSequenceWithCustomMap<OpaqueValue<Int>>,
  @noescape transform: (OpaqueValue<Int>) -> T
) -> [T] {
  var result = sequence.map(transform)
  expectType([T].self, &result)
  return result
}

func callGenericSequenceMap<S : SequenceType, T>(
  sequence: S,
  @noescape transform: (S.Generator.Element) -> T
) -> [T] {
  var result = sequence.map(transform)
  expectType([T].self, &result)
  return result
}

% for Implementation in [ 'Default', 'Custom' ]:

%   for dispatch in [ 'Static', 'Generic' ]:

SequenceTypeTests.test(
  "map/SequenceType/${Implementation}Implementation/${dispatch}"
) {
  for test in mapTests {
    for underestimateCountBehavior in [
      UnderestimateCountBehavior.Precise,
      UnderestimateCountBehavior.Half,
      UnderestimateCountBehavior.Value(0)
    ] {
      let s = MinimalSequenceWith${Implementation}Map<OpaqueValue<Int>>(
        test.sequence.map(OpaqueValue.init),
        underestimatedCount: underestimateCountBehavior)
      let closureLifetimeTracker = LifetimeTracked(0)
      expectEqual(1, LifetimeTracked.instances)
      var timesClosureWasCalled = 0
%     if Implementation == 'Custom':
      MinimalSequenceWithCustomMap<OpaqueValue<Int>>.timesMapWasCalled = 0
%     end
      var result = call${dispatch}SequenceMap(s) {
        (element: OpaqueValue<Int>) -> OpaqueValue<Int32> in
        _blackHole(closureLifetimeTracker)
        ++timesClosureWasCalled
        return OpaqueValue(Int32(test.transform(element.value)))
      }
      expectType([OpaqueValue<Int32>].self, &result)
      expectEqual(test.expected, result.map { $0.value })
%     if Implementation == 'Custom':
      expectEqual(
        1, MinimalSequenceWithCustomMap<OpaqueValue<Int>>.timesMapWasCalled)
%     end
      expectEqual([], s.map { $0.value }, "sequence should be consumed")
      expectEqual(
        test.sequence.count, timesClosureWasCalled,
        "map() should be eager and should only call its predicate"
        + "once per element")
    }
  }
}

%   end

% end

//===----------------------------------------------------------------------===//
// flatMap()
//===----------------------------------------------------------------------===//

SequenceTypeTests.test("flatMap/SequenceType") {
  for test in flatMapTests {
    for underestimateCountBehavior in [
      UnderestimateCountBehavior.Precise,
      UnderestimateCountBehavior.Value(0)
    ] {
      let s = MinimalSequence<OpaqueValue<Int>>(
        elements: test.sequence.map(OpaqueValue.init),
        underestimatedCount: underestimateCountBehavior)
      let closureLifetimeTracker = LifetimeTracked(0)
      var timesClosureWasCalled = 0
      var result = s.flatMap {
        (element: OpaqueValue<Int>) -> MinimalSequence<OpaqueValue<Int32>> in
        _blackHole(closureLifetimeTracker)
        ++timesClosureWasCalled
        return MinimalSequence<OpaqueValue<Int32>>(
          elements: test.transform(element.value).map { OpaqueValue(Int32($0)) })
      }
      expectType([OpaqueValue<Int32>].self, &result)
      expectEqual(
        test.expected, result.map { $0.value },
        stackTrace: SourceLocStack().with(test.loc))
      expectTrue(Array(s).isEmpty, "sequence should be consumed")
      expectEqual(
        test.sequence.count, timesClosureWasCalled,
        "flatMap() should be eager and should only call its predicate"
        + "once per element")
      expectGE(
        2 * result.count, result.capacity,
        "flatMap() should not reserve capacity")
    }
  }
}

% TLazyFlatMapTest = gyb.parseTemplate("{}/Inputs/flatMap.gyb".format(test_path))
% LazyFlatMapTest = gyb.executeTemplate(TLazyFlatMapTest, Test='SequenceTypeTests', Kinds=['Sequence'])
${LazyFlatMapTest}

SequenceTypeTests.test("flatMap/SequenceType/TransformProducesOptional") {
  for test in flatMapToOptionalTests {
    for underestimateCountBehavior in [
      UnderestimateCountBehavior.Precise,
      UnderestimateCountBehavior.Value(0)
    ] {
      let s = MinimalSequence<OpaqueValue<Int>>(
        elements: test.sequence.map(OpaqueValue.init),
        underestimatedCount: underestimateCountBehavior)
      let closureLifetimeTracker = LifetimeTracked(0)
      expectEqual(1, LifetimeTracked.instances)
      var timesClosureWasCalled = 0
      var result = s.flatMap {
        (element: OpaqueValue<Int>) -> OpaqueValue<Int32>? in
        _blackHole(closureLifetimeTracker)
        ++timesClosureWasCalled
        return test.transform(element.value).map { OpaqueValue(Int32($0)) }
      }
      expectType([OpaqueValue<Int32>].self, &result)
      expectEqual(
        test.expected, result.map { $0.value },
        stackTrace: SourceLocStack().with(test.loc))
      expectTrue(Array(s).isEmpty, "sequence should be consumed")
      expectEqual(
        test.sequence.count, timesClosureWasCalled,
        "flatMap() should be eager and should only call its predicate"
        + "once per element")
      expectGE(
        2 * result.count, result.capacity,
        "flatMap() should not reserve capacity")
    }
  }
}

//===----------------------------------------------------------------------===//
// forEach()
//===----------------------------------------------------------------------===//

SequenceTypeTests.test("forEach/dispatch") {
  let tester = SequenceLog.dispatchTester([OpaqueValue(1)])
  tester.forEach { print($0) }
  expectCustomizable(tester, tester.log.forEach)
}

//===----------------------------------------------------------------------===//
// dropFirst()
//===----------------------------------------------------------------------===//

SequenceTypeTests.test("dropFirst/dispatch") {
  var tester = SequenceLog.dispatchTester([OpaqueValue(1)])
  tester.dropFirst(1)
  expectCustomizable(tester, tester.log.dropFirst)
}

//===----------------------------------------------------------------------===//
// dropLast()
//===----------------------------------------------------------------------===//

SequenceTypeTests.test("dropLast/dispatch") {
  var tester = SequenceLog.dispatchTester([OpaqueValue(1)])
  tester.dropLast(1)
  expectCustomizable(tester, tester.log.dropLast)
}

//===----------------------------------------------------------------------===//
// prefix()
//===----------------------------------------------------------------------===//

SequenceTypeTests.test("prefix/dispatch") {
  var tester = SequenceLog.dispatchTester([OpaqueValue(1)])
  tester.prefix(1)
  expectCustomizable(tester, tester.log.prefix)
}

//===----------------------------------------------------------------------===//
// suffix()
//===----------------------------------------------------------------------===//

SequenceTypeTests.test("suffix/dispatch") {
  var tester = SequenceLog.dispatchTester([OpaqueValue(1)])
  tester.suffix(1)
  expectCustomizable(tester, tester.log.suffix)
}

//===----------------------------------------------------------------------===//
// split()
//===----------------------------------------------------------------------===//

SequenceTypeTests.test("SequenceType/split/dispatch") {
  var tester = SequenceLog.dispatchTester([OpaqueValue(1)])
  tester.split { $0.value == 1 }
  expectCustomizable(tester, tester.log.split)
}

//===----------------------------------------------------------------------===//
// zip()
//===----------------------------------------------------------------------===//

// Check that the generic parameters are called 'Generator1' and 'Generator2'.
extension Zip2Generator
  where Generator1 : TestProtocol1, Generator2 : TestProtocol1 {

  var _generator1IsTestProtocol1: Bool {
    fatalError("not implemented")
  }
}

extension Zip2Sequence
  where Sequence1 : TestProtocol1, Sequence2 : TestProtocol1 {

  var _sequence1IsTestProtocol1: Bool {
    fatalError("not implemented")
  }
}

SequenceTypeTests.test("zip") {
  typealias Element = (OpaqueValue<Int>, OpaqueValue<Int32>)
  func compareElements(lhs: Element, rhs: Element) -> Bool {
    return lhs.0.value == rhs.0.value && lhs.1.value == rhs.1.value
  }

  for test in zipTests {
    let s = MinimalSequence<OpaqueValue<Int>>(
      elements: test.sequence.map(OpaqueValue.init))
    let other = MinimalSequence<OpaqueValue<Int32>>(
      elements: test.other.map(OpaqueValue.init))
    var result = zip(s, other)
    expectType(
      Zip2Sequence<MinimalSequence<OpaqueValue<Int>>, MinimalSequence<OpaqueValue<Int32>>>.self,
      &result)

    // Check for expected result and check the Zip2Sequence's SequenceType
    // conformance.
    checkSequence(
      test.expected.map { (OpaqueValue($0), OpaqueValue($1)) }, result,
      stackTrace: SourceLocStack().with(test.loc), sameValue: compareElements)
    
    // Check leftovers *after* doing checkSequence(), not before, to ensure
    // that checkSequence() didn't force us to consume more elements than
    // needed.
    expectEqual(
      test.expectedLeftoverSequence, s.map { $0.value },
      stackTrace: SourceLocStack().with(test.loc))
    expectEqual(
      test.expectedLeftoverOther, other.map { $0.value },
      stackTrace: SourceLocStack().with(test.loc))
  }
}

//===----------------------------------------------------------------------===//
// underestimateCount()
//===----------------------------------------------------------------------===//

struct SequenceWithDefaultUnderestimateCount : SequenceType {
  init() {}

  func generate() -> MinimalSequence<OpaqueValue<Int>>.Generator {
    expectUnreachable()
    return MinimalSequence(
      elements: [ 1, 2, 3 ].map(OpaqueValue.init)
    ).generate()
  }
}

SequenceTypeTests.test("underestimateCount/SequenceType/DefaultImplementation") {
  let s = SequenceWithDefaultUnderestimateCount()
  expectEqual(0, callGenericUnderestimatedCount(s))
}

struct SequenceWithCustomUnderestimateCount : SequenceType {
  init(underestimatedCount: Int) {
    self._underestimatedCount = underestimatedCount
  }

  func generate() -> MinimalSequence<OpaqueValue<Int>>.Generator {
    expectUnreachable()
    return MinimalSequence(
      elements: [ 0xffff, 0xffff, 0xffff ].map(OpaqueValue.init)
    ).generate()
  }

  func underestimateCount() -> Int {
    return _underestimatedCount
  }

  let _underestimatedCount: Int
}

SequenceTypeTests.test("underestimateCount/SequenceType/CustomImplementation") {
  if true {
    let s = SequenceWithCustomUnderestimateCount(underestimatedCount: 5)
    expectEqual(5, callGenericUnderestimatedCount(s))
  }
  if true {
    let s = SequenceWithCustomUnderestimateCount(underestimatedCount: 42)
    expectEqual(42, callGenericUnderestimatedCount(s))
  }
}

//===----------------------------------------------------------------------===//
// _copyToNativeArrayBuffer()
//===----------------------------------------------------------------------===//
SequenceTypeTests.test("_copyToNativeArrayBuffer/OverestimatedCount")
  .skip(.Custom(
    { _isFastAssertConfiguration() },
    reason: "this trap is not guaranteed to happen in -Ounchecked"))
  .code {
  let s = MinimalSequence<OpaqueValue<Int>>(
    elements: [ 1, 2, 3 ].map(OpaqueValue.init),
    underestimatedCount: .Value(4))
  expectCrashLater()
  let array = s._copyToNativeArrayBuffer()
  _blackHole(array)
}

//===----------------------------------------------------------------------===//
// Standard sequence tests
//===----------------------------------------------------------------------===//

% for Base in [ 'DefaultedSequence', 'MinimalSequence' ]:
if true {
  let checksAdded: Box<Set<String>> = Box([])
  let resiliencyChecks = CollectionMisuseResiliencyChecks.all

  SequenceTypeTests.addSequenceTests(
    makeSequence: { (elements: [OpaqueValue<Int>]) in
      return ${Base}(elements: elements)
    },
    wrapValue: identity,
    extractValue: identity,
    makeSequenceOfEquatable: { (elements: [MinimalEquatableValue]) in
      return ${Base}(elements: elements)
    },
    wrapValueIntoEquatable: identityEq,
    extractValueFromEquatable: identityEq,
    checksAdded: checksAdded,
    resiliencyChecks: resiliencyChecks)
}
% end

runAllTests()