Lazy.swift.gyb

//===--- Lazy.swift - Tests for LazySequence and LazyCollection -----------===//
//
// This source file is part of the Swift.org open source project
//
// Copyright (c) 2014 - 2015 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See http://swift.org/LICENSE.txt for license information
// See http://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
//
//===----------------------------------------------------------------------===//
// RUN: rm -rf %t
// RUN: mkdir -p %t
// RUN: %S/../../utils/gyb %s -o %t/Lazy.swift
// RUN: %S/../../utils/line-directive %t/Lazy.swift -- %target-build-swift %t/Lazy.swift -o %t/a.out
// RUN: %S/../../utils/line-directive %t/Lazy.swift -- %target-run %t/a.out
// REQUIRES: executable_test

import StdlibUnittest

var LazyTestSuite = TestSuite("Lazy")

protocol TestProtocol1 {}

//===----------------------------------------------------------------------===//
// Repeat
//===----------------------------------------------------------------------===//

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

LazyTestSuite.test("Repeat") {
  checkRandomAccessCollection(
    [] as Array<OpaqueValue<Int>>,
    Repeat(count: 0, repeatedValue: OpaqueValue(42)))
    { $0.value == $1.value }

  checkRandomAccessCollection(
    [ OpaqueValue(42) ] as Array<OpaqueValue<Int>>,
    Repeat(count: 1, repeatedValue: OpaqueValue(42)))
    { $0.value == $1.value }

  checkRandomAccessCollection(
    [ OpaqueValue(42), OpaqueValue(42), OpaqueValue(42) ] as Array<OpaqueValue<Int>>,
    Repeat(count: 3, repeatedValue: OpaqueValue(42)))
    { $0.value == $1.value }
}

// FIXME: trap tests.

//===----------------------------------------------------------------------===//
// CollectionOfOne
//===----------------------------------------------------------------------===//

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

LazyTestSuite.test("CollectionOfOne") {
  checkRandomAccessCollection(
    [ OpaqueValue(42) ],
    CollectionOfOne(OpaqueValue(42))) { $0.value == $1.value }
}

// FIXME: trap tests.

//===----------------------------------------------------------------------===//
// GeneratorOfOne
//===----------------------------------------------------------------------===//

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

LazyTestSuite.test("GeneratorOfOne") {
  checkGenerator(
    [] as Array<OpaqueValue<Int>>,
    GeneratorOfOne(nil as Optional<OpaqueValue<Int>>)) { $0.value == $1.value }

  checkGenerator(
    [ OpaqueValue(42) ] as Array<OpaqueValue<Int>>,
    GeneratorOfOne(OpaqueValue(42))) { $0.value == $1.value }
}

//===----------------------------------------------------------------------===//
// EmptyCollection
//===----------------------------------------------------------------------===//

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

LazyTestSuite.test("EmptyCollection") {
  checkRandomAccessCollection(
    [],
    EmptyCollection<OpaqueValue<Int>>()) { $0.value == $1.value }
}

// FIXME: trap tests.

//===----------------------------------------------------------------------===//
// EmptyGenerator
//===----------------------------------------------------------------------===//

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

LazyTestSuite.test("EmptyGenerator") {
  checkGenerator(
    [] as Array<OpaqueValue<Int>>,
    EmptyGenerator<OpaqueValue<Int>>())
    { $0.value == $1.value }
}

// FIXME: trap tests.

//===----------------------------------------------------------------------===//
// lazy()
//===----------------------------------------------------------------------===//

LazyTestSuite.test("isEmpty") {
  expectTrue((0..<0).lazy.isEmpty)
  expectFalse((0...0).lazy.isEmpty)
}

LazyTestSuite.test("firstLast") {
  expectOptionalEqual(7 as Int, (7..<42).lazy.first)
  expectOptionalEqual(41 as Int, (7..<42).lazy.last)
  expectEmpty((7..<7).lazy.first)
  expectEmpty((7..<7).lazy.last)
}

//===----------------------------------------------------------------------===//
// LazySequence
//===----------------------------------------------------------------------===//

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

LazyTestSuite.test("LazySequence<Sequence>/underestimateCount") {
  let s = MinimalSequence(
    elements: [ 0, 30, 10, 90 ].map(OpaqueValue.init),
    underestimatedCount: .Value(42))
  var lazySeq = s.lazy
  expectType(LazySequence<MinimalSequence<OpaqueValue<Int>>>.self, &lazySeq)
  expectEqual(42, lazySeq.underestimateCount())
}

%for traversal in [ 'Forward', 'Bidirectional', 'RandomAccess' ]:

LazyTestSuite.test("LazySequence<${traversal}Collection>/underestimateCount") {
  let s = Minimal${traversal}Collection(
    elements: [ 0, 30, 10, 90 ].map(OpaqueValue.init),
    underestimatedCount: .Value(42))
  var lazySeq = s.lazy
  expectType(
    LazyCollection<
      Minimal${traversal}Collection<OpaqueValue<Int>>
    >.self,
    &lazySeq)
  expectEqual(42, lazySeq.underestimateCount())
}

%end

//===----------------------------------------------------------------------===//
// MapSequence
//===----------------------------------------------------------------------===//

LazyTestSuite.test("MapSequence<Sequence>/underestimateCount") {
  let s = MinimalSequence(
    elements: [ 0, 30, 10, 90 ].map(OpaqueValue.init),
    underestimatedCount: .Value(42))
  var lazyMap = s.lazy.map { OpaqueValue(Int32($0.value)) }
  expectType(
    LazyMapSequence<MinimalSequence<OpaqueValue<Int>>, OpaqueValue<Int32>>.self,
    &lazyMap)
  expectEqual(42, lazyMap.underestimateCount())
}

struct SequenceWithCustomUnderestimateCount : SequenceType {
  init(_ data: [Int]) {
    self._data = MinimalSequence(elements: data.map(OpaqueValue.init))
  }

  func generate() -> MinimalSequence<OpaqueValue<Int>>.Generator {
    return _data.generate()
  }

  func underestimateCount() -> Int {
    ++SequenceWithCustomUnderestimateCount.timesUnderestimateCountWasCalled
    return _data.underestimateCount()
  }

  static var timesUnderestimateCountWasCalled: Int = 0

  let _data: MinimalSequence<OpaqueValue<Int>>
}

LazyTestSuite.test("LazySequence.array") {
  SequenceWithCustomUnderestimateCount.timesUnderestimateCountWasCalled = 0

  let base = SequenceWithCustomUnderestimateCount([ 0, 30, 10, 90 ])
  let lazySequence = LazySequence(base)
  let arrayFromLazy = Array(lazySequence)

  expectEqual([ 0, 30, 10, 90 ], arrayFromLazy.map { $0.value })

  // Lazy sequences should use underestimated count to preallocate array
  // storage.
  expectEqual(1, SequenceWithCustomUnderestimateCount.timesUnderestimateCountWasCalled)

  expectEqualSequence(
    [], Array(base).map { $0.value }, "sequence should be consumed")
}

%for traversal in [ 'Forward', 'Bidirectional', 'RandomAccess' ]:

LazyTestSuite.test("MapCollection<${traversal}Collection>/underestimateCount") {
  let s = Minimal${traversal}Collection(
    elements: [ 0, 30, 10, 90 ].map(OpaqueValue.init),
    underestimatedCount: .Value(42))
  var lazyMap = s.lazy.map {
    (input: OpaqueValue<Int>) -> OpaqueValue<Int32> in
    OpaqueValue(Int32(input.value))
  }
  expectType(
    LazyMapCollection<
      Minimal${traversal}Collection<OpaqueValue<Int>>, OpaqueValue<Int32>
    >.self,
    &lazyMap)
  expectEqual(42, lazyMap.underestimateCount())
}

%end

//===----------------------------------------------------------------------===//
// LazyCollection
//===----------------------------------------------------------------------===//

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

%for (traversal, ReversedType) in [
%    ('Forward', None),
%    ('Bidirectional', 'ReverseCollection'),
%    ('RandomAccess', 'ReverseRandomAccessCollection')
%]:

LazyTestSuite.test("LazyCollection.array") {
  let base = Minimal${traversal}Collection(
    elements: [ 0, 30, 10, 90 ], underestimatedCount: .Value(42))
  let lazyCollection = LazyCollection(base)
  let arrayFromLazy = Array(lazyCollection)

  expectEqual([ 0, 30, 10, 90 ], arrayFromLazy)

  // Lazy collections should not use underestimated count to preallocate array
  // storage, since they have access to real count instead.
  expectLE(4, arrayFromLazy.capacity)
  expectGE(40, arrayFromLazy.capacity)
}

%  if ReversedType is not None:
LazyTestSuite.test("LazyCollection.reverse") {
  let base = Minimal${traversal}Collection(
    elements: [ 0, 30, 10, 90 ].map(OpaqueValue.init),
    underestimatedCount: .Value(42))
  let lazyCollection = LazyCollection(base)
  var reversed = lazyCollection.reverse()
  expectType(
    LazyCollection<${ReversedType}<Minimal${traversal}Collection<OpaqueValue<Int>>>>.self,
    &reversed)

  check${traversal}Collection(
    [ 90, 10, 30, 0 ].map(OpaqueValue.init) as [OpaqueValue<Int>],
    reversed) { $0.value == $1.value }

  var reversedTwice = reversed.reverse()
  expectType(
    LazyCollection<${ReversedType}<${ReversedType}<Minimal${traversal}Collection<OpaqueValue<Int>>>>>.self,
    &reversedTwice)

  check${traversal}Collection(
    [ 0, 30, 10, 90 ].map(OpaqueValue.init) as [OpaqueValue<Int>],
    reversedTwice) { $0.value == $1.value }
}
%  end

%end

//===----------------------------------------------------------------------===//
// ReverseCollection
//===----------------------------------------------------------------------===//

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

//===----------------------------------------------------------------------===//
// ReverseIndex
//===----------------------------------------------------------------------===//

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

//===----------------------------------------------------------------------===//
// RandomAccessReverseCollection
//===----------------------------------------------------------------------===//

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

//===----------------------------------------------------------------------===//
// ReverseRandomAccessIndex
//===----------------------------------------------------------------------===//

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

var tests = TestSuite("NewLazy")

tests.test("LazySequence/SequenceType") {
  let expected = (0..<100).map(OpaqueValue.init)
  var actual = MinimalSequence(elements: expected).lazy
  
  expectType(
    LazySequence<MinimalSequence<OpaqueValue<Int>>>.self, &actual)

  // Asking for .lazy again doesn't re-wrap the type
  var again = actual.lazy
  expectType(
    LazySequence<MinimalSequence<OpaqueValue<Int>>>.self, &again)
  
  var elements = actual.elements

  // Expect .elements to strip a lazy wrapper
  expectType(MinimalSequence<OpaqueValue<Int>>.self, &elements)

  checkSequence(expected, actual, resiliencyChecks: .none) {
    $0.value == $1.value
  }
}

func expectSequencePassthrough<
  S : SequenceType, Base : SequenceType
  where S : LazySequenceType, Base : LoggingType,
    Base.Generator.Element == S.Generator.Element
>(s: S, base: Base, arbitraryElement: S.Generator.Element, count: Int) {
  let baseType = base.dynamicType

  SequenceLog.generate.expectIncrement(baseType) { _ = s.generate() }
  SequenceLog.underestimateCount.expectIncrement(baseType) {
    _ = s.underestimateCount()
  }
  SequenceLog._customContainsEquatableElement.expectIncrement(baseType) {
    _ = s._customContainsEquatableElement(arbitraryElement)
  }
  SequenceLog._copyToNativeArrayBuffer.expectIncrement(baseType) {
    _ = s._copyToNativeArrayBuffer()
  }
  
  SequenceLog._initializeTo.expectIncrement(baseType) { ()->Void in
    let buf = UnsafeMutablePointer<S.Generator.Element>.alloc(count)
  
    let end = s._initializeTo(buf)
    expectTrue(end <= buf + count)
    buf.destroy(end - buf)
    buf.dealloc(count)
  }
}

tests.test("LazySequence/Passthrough") {
  // Test that operations that might be optimized are passed
  // through to the underlying sequence.
  let a = (0..<100).map(OpaqueValue.init)
  let base = LoggingSequence(a)
  
  expectSequencePassthrough(
    base.lazy,
    base: base, arbitraryElement: OpaqueValue(0), count: a.count)
}

% for traversal in 'Forward', 'Bidirectional', 'RandomAccess':
tests.test("LazyCollection/CollectionType/${traversal}") {
  let expected = (0..<100).map(OpaqueValue.init)
  let base = Minimal${traversal}Collection(elements: expected)
  var actual = base.lazy
  
  expectType(
    LazyCollection<Minimal${traversal}Collection<OpaqueValue<Int>>>.self,
    &actual)

  // Asking for .lazy again doesn't re-wrap the type
  var again = actual.lazy
  expectType(
    LazyCollection<Minimal${traversal}Collection<OpaqueValue<Int>>>.self,
    &again)
  
  check${traversal}Collection(
    expected, base.lazy, resiliencyChecks: .none
  ) { $0.value == $1.value }

  var elements = base.lazy.elements
  expectType(Minimal${traversal}Collection<OpaqueValue<Int>>.self, &elements)
}
% end

tests.test("LazyCollection/Passthrough") {
  let expected = (0..<100).map(OpaqueValue.init)
  let base = LoggingCollection(expected)
  
  expectSequencePassthrough(
    base.lazy,
    base: base.lazy._base,
    arbitraryElement: OpaqueValue(0),
    count: Int(expected.count))

  let s = base.lazy
  let baseType = base.dynamicType
  let startIndex = CollectionLog.startIndex.expectIncrement(baseType) {
    s.startIndex
  }
  
  let endIndex = CollectionLog.endIndex.expectIncrement(baseType) {
    s.endIndex
  }
  
  CollectionLog.subscriptIndex.expectIncrement(baseType) { _ = s[startIndex] }
  CollectionLog.subscriptRange.expectUnchanged(baseType) {
    _ = s[startIndex..<endIndex]
  }
  CollectionLog.isEmpty.expectIncrement(baseType) { _ = s.isEmpty }
  CollectionLog.count.expectIncrement(baseType) { _ = s.count }
  CollectionLog._customIndexOfEquatableElement.expectIncrement(baseType) {
    _ = s._customIndexOfEquatableElement(OpaqueValue(0))
  }
  CollectionLog.first.expectIncrement(baseType) { _ = s.first }
}

//===--- Map --------------------------------------------------------------===//

tests.test("LazyMapSequence") {
  let base = MinimalSequence(
    elements: [2, 3, 5, 7, 11].map(OpaqueValue.init)).lazy

  var calls = 0
  var mapped = base.map {
    (x: OpaqueValue<Int>)->OpaqueValue<Double> in
    ++calls
    return OpaqueValue(Double(x.value) / 2.0)
  }

  expectEqual(0, calls)
  
  expectType(
    LazyMapSequence<
      MinimalSequence<OpaqueValue<Int>>, 
      OpaqueValue<Double>>.self,
    &mapped)
  
  let expected = [ 1.0, 1.5, 2.5, 3.5, 5.5 ].map(OpaqueValue.init)
  
  checkSequence(expected, mapped, resiliencyChecks: .none) {
    $0.value == $1.value
  }
  
  expectEqual(expected.count, calls)
}

tests.test("MapSequence/Passthrough") {
  let expected = (0..<100).map(OpaqueValue.init)
  let base = LoggingSequence(expected)
  let mapped = base.lazy.map { OpaqueValue(Double($0.value) / 2.0) }
  CollectionLog.underestimateCount.expectIncrement(base.dynamicType) {
    _ = mapped.underestimateCount()
  }
  // Not exactly passthrough because we wrap the result
  CollectionLog.generate.expectIncrement(base.dynamicType) {
    _ = mapped.generate()
  }
}

% for traversal in 'Forward', 'Bidirectional', 'RandomAccess':
tests.test("LazyMapCollection/${traversal}") {
  let base = Minimal${traversal}Collection(
    elements: [2, 3, 5, 7, 11].map(OpaqueValue.init)).lazy

  var calls = 0
  var mapped = base.map {
    (x: OpaqueValue<Int>)->OpaqueValue<Double> in
    ++calls
    return OpaqueValue(Double(x.value) / 2.0)
  }
  expectEqual(0, calls)
  
  expectType(
    LazyMapCollection<
      Minimal${traversal}Collection<OpaqueValue<Int>>, 
      OpaqueValue<Double>>.self,
    &mapped)
  
  let expected = [ 1.0, 1.5, 2.5, 3.5, 5.5 ].map(OpaqueValue.init)
  
  check${traversal}Collection(expected, mapped, resiliencyChecks: .none) {
    $0.value == $1.value
  }

  // check${traversal}Collection makes multiple passes over the input,
  // so we test that each element was transformed *at least* once.
  expectLE(expected.count, calls)
}
%end

tests.test("LazyMapCollection/Passthrough") {
  let expected = (0..<100).map(OpaqueValue.init)
  let base = LoggingCollection(expected)
  let mapped = base.lazy.map { OpaqueValue(Double($0.value) / 2.0) }
  
  let startIndex = CollectionLog.startIndex.expectIncrement(base.dynamicType) {
    mapped.startIndex
  }
  let endIndex = CollectionLog.endIndex.expectIncrement(base.dynamicType) {
    mapped.endIndex
  }
  // Not exactly passthrough, because mapping transforms the result
  CollectionLog.subscriptIndex.expectIncrement(base.dynamicType) {
    _ = mapped[startIndex]
  }
  CollectionLog.isEmpty.expectIncrement(base.dynamicType) {
    _ = mapped.isEmpty
  }
  CollectionLog.first.expectIncrement(base.dynamicType) {
    _ = mapped.first
  }
  CollectionLog.underestimateCount.expectIncrement(base.dynamicType) {
    _ = mapped.underestimateCount()
  }
  // Not exactly passthrough because we wrap the result
  CollectionLog.generate.expectIncrement(base.dynamicType) {
    _ = mapped.generate()
  }
}


//===--- Reverse ----------------------------------------------------------===//
tests.test("ReverseCollection") {

  let expected = Array(11.stride(through: 0, by: -1))
  let r = 0..<12
  checkRandomAccessCollection(
    expected,
    r.reverse())

  // Check that the reverse collection is still eager
  do {
    var calls = 0
    _ = r.reverse().map { _ in ++calls }
    expectEqual(r.count, calls)
  }
  
  checkBidirectionalCollection(
    "raboof".characters,
    "foobar".characters.reverse())

  // Check that the reverse collection is still eager
  do {
    var calls = 0
    _ = "foobar".characters.reverse().map { _ in ++calls }
    expectEqual("foobar".characters.count, calls)
  }
}

enum _Void {}
struct ExpectType<T> {
  static func test(_: T){ print("T") }
  static func test(_: Any) { fatalError() }
  static func test(_: Any) -> _Void { fatalError() }
}

tests.test("ReverseCollection/Lazy") {
  // Check that reversing a lazy collection, or lazy-ing a reverse
  // collection, produces the same lazy reverse collection.
  do {
    
    let base = Array(11.stride(through: 0, by: -1)).lazy.map { $0 }
    
    typealias Base = LazyMapCollection<[Int], Int>
    ExpectType<Base>.test(base)
    
    typealias LazyReversedBase = LazyCollection<
      ReverseRandomAccessCollection<Base>>

    let reversed = base.reverse()
    ExpectType<LazyReversedBase>.test(reversed)
    
    var calls = 0
    let reversedAndMapped = reversed.map { (x)->Int in ++calls; return x }
    expectEqual(0, calls)
    checkRandomAccessCollection(0...11, reversedAndMapped)
    expectNotEqual(0, calls)
  }

  do {
    typealias Expected = LazyCollection<
      ReverseCollection<String.CharacterView>
    >
    
    let base = "foobar".characters.lazy.map { $0 }
    typealias Base = LazyMapCollection<String.CharacterView, Character>
    ExpectType<Base>.test(base)
    
    typealias LazyReversedBase = LazyCollection<
      ReverseCollection<Base>>

    let reversed = base.reverse()
    ExpectType<LazyReversedBase>.test(reversed)
    
    var calls = 0
    let reversedAndMapped = reversed.map { (x)->Character in ++calls; return x }
    expectEqual(0, calls)
    checkBidirectionalCollection("raboof".characters, reversedAndMapped)
    expectNotEqual(0, calls)
  }
}

// Given a couple of sequences backed by FilterGenerator's, check that
// the first selects even numbers and the second selects odd numbers,
// both from an underlying sequence of whole numbers.
func checkFilterGeneratorBase<
  S : SequenceType, T : GeneratorType 
    where S.Generator == LazyFilterGenerator<T>, T.Element == OpaqueValue<Int>
>(s1: S, _ s2: S) {
  var g1 = s1.generate()
  expectEqual(0, g1.next()!.value)
  expectEqual(2, g1.next()!.value)
  expectEqual(4, g1.next()!.value)
  var h1 = g1.base
  expectEqual(5, h1.next()!.value)
  expectEqual(6, h1.next()!.value)
  expectEqual(7, h1.next()!.value)

  var g2 = s2.generate()
  expectEqual(1, g2.next()!.value)
  expectEqual(3, g2.next()!.value)
  expectEqual(5, g2.next()!.value)
  var h2 = g2.base
  expectEqual(6, h2.next()!.value)
  expectEqual(7, h2.next()!.value)
  expectEqual(8, h2.next()!.value)
}

tests.test("LazyFilterSequence") {
  let base = (0..<100).map(OpaqueValue.init)

  var calls = 0
  var filtered = MinimalSequence(elements: base).lazy.filter {
    x in ++calls;
    return x.value % 2 == 0
  }
  expectEqual(calls, 0, "filtering was eager!")
  
  ExpectType<
    LazyFilterSequence<MinimalSequence<OpaqueValue<Int>>>
  >.test(filtered)

  let evens = 0.stride(to: 100, by: 2).map(OpaqueValue.init)
  checkSequence(evens, filtered, resiliencyChecks: .none) {
    $0.value == $1.value 
  }
  expectEqual(100, calls)

  // check that it works when the first element doesn't satify the predicate
  let odds = 1.stride(to: 100, by: 2).map(OpaqueValue.init)
  filtered =
    MinimalSequence(elements: base).lazy.filter { $0.value % 2 != 0 }
  checkSequence(odds, filtered, resiliencyChecks: .none) {
    $0.value == $1.value
  }
  
  // Try again using explicit construction
  filtered = LazyFilterSequence(
    MinimalSequence(elements: base),
    whereElementsSatisfy: { x in ++calls; return x.value % 2 == 0})
  
  expectEqual(100, calls)

  // Check that it constructs the same sequence
  checkSequence(evens, filtered, resiliencyChecks: .none) {
    $0.value == $1.value 
  }
  
  expectEqual(200, calls)

  checkFilterGeneratorBase(
    MinimalSequence(elements: base).lazy.filter { $0.value % 2 == 0 },
    MinimalSequence(elements: base).lazy.filter { $0.value % 2 != 0 })
}

tests.test("LazyFilterIndex/base") {
  let base = MinimalForwardCollection(elements: (0..<100).map(OpaqueValue.init))
  let evens = base.lazy.filter { $0.value % 2 == 0 }
  let odds = base.lazy.filter { $0.value % 2 != 0 }
  
  expectEqual(base.startIndex, evens.startIndex.base)
  expectEqual(base.startIndex.successor(), odds.startIndex.base)

  expectEqual(
    base.startIndex.successor().successor(),
    evens.startIndex.successor().base)
  
  expectEqual(
    base.startIndex.successor().successor().successor(),
    odds.startIndex.successor().base)
}

tests.test("LazyFilterCollection") {
  let base = MinimalForwardCollection(elements: (0..<100).map(OpaqueValue.init))

  var calls = 0
  let filtered = base.lazy.filter {
    x in ++calls;
    return x.value % 2 == 0
  }
  expectEqual(calls, 0, "filtering was eager!")
  
  ExpectType<
    LazyFilterCollection<MinimalForwardCollection<OpaqueValue<Int>>>
  >.test(filtered)
  
  checkForwardCollection(
    0.stride(to: 100, by: 2).map(OpaqueValue.init), filtered,
    resiliencyChecks: .none
  ) {
    $0.value == $1.value
  }

  expectGE(calls, 100)
  let oldCalls = calls
  _ = filtered.first
  expectLT(oldCalls, calls)
  expectGE(oldCalls + 2, calls)

  checkFilterGeneratorBase(
    base.lazy.filter { $0.value % 2 == 0 },
    base.lazy.filter { $0.value % 2 != 0 })
}

do {
  struct Sample {
    var expected: Range<Int>
    var data: [Range<Int>]
  }
  
  let flattenSamples: [Sample] = [
    Sample(
      expected: 0..<8, data: [ 1..<1, 0..<5, 7..<7, 5..<7, 7..<8 ]),
    Sample(expected: 0..<8, data: [ 0..<5, 7..<7, 5..<7, 7..<8 ]),
    Sample(
      expected: 0..<8, data: [ 1..<1, 0..<5, 7..<7, 5..<7, 7..<8, 11..<11 ]),
    Sample(
      expected: 0..<16, data: [ 0..<10, 14..<14, 10..<14, 14..<16, 22..<22 ]),
    Sample(expected: 0..<0, data: [ 11..<11 ]),
    Sample(expected: 0..<0, data: [ 3..<3, 11..<11 ]),
    Sample(expected: 0..<0, data: []),
  ]

  for sample in flattenSamples {
    let expected = sample.expected
    let data = sample.data
    
    tests.test("FlattenSequence/\(data)") {
      var base = MinimalSequence(
        elements: data.map { MinimalSequence(elements: $0) })
      checkSequence(expected, base.flatten(), resiliencyChecks: .none)

      // Checking that flatten doesn't introduce laziness
      
      // checkSequence consumed base, so reassign
      base = MinimalSequence(
        elements: data.map { MinimalSequence(elements: $0) })
      let flattened = base.flatten()
      var calls = 0
      _ = flattened.map { _ in ++calls }
      expectEqual(
        expected.count, calls,
        "unexpected laziness in \(flattened.dynamicType)")
    }

    tests.test("FlattenSequence/Lazy/\(data)") {
      // Checking that flatten doesn't remove laziness
      let base = MinimalSequence(
        elements: data.map { MinimalSequence(elements: $0) }
      ).lazy.map { $0 }

      let flattened = base.flatten()
      var calls = 0
      _ = flattened.map { _ in ++calls }
      expectEqual(0, calls, "unexpected eagerness in \(flattened.dynamicType)")
    }
    
  % for traversal in 'Forward', 'Bidirectional':
  %   t = '' if traversal == 'Forward' else traversal
    tests.test("Flatten${t}Collection/\(data)") {
      let base = Minimal${traversal}Collection(
        elements: data.map { Minimal${traversal}Collection(elements: $0) })

      let flattened = base.flatten()
      check${traversal}Collection(expected, flattened, resiliencyChecks: .none)

      // Checking that flatten doesn't introduce laziness
      var calls = 0
      _ = flattened.map { _ in ++calls }
      expectLE(
        expected.count, calls,
        "unexpected laziness in \(flattened.dynamicType)")
    }
    
    tests.test("Flatten${t}Collection/Lazy\(data)") {
      // Checking that flatten doesn't remove laziness
      let base = Minimal${traversal}Collection(
        elements: data.map { Minimal${traversal}Collection(elements: $0) }
      ).lazy.map { $0 }

      let flattened = base.flatten()
    
      var calls = 0
      _ = flattened.map { _ in ++calls }
      expectEqual(0, calls, "unexpected eagerness in \(flattened.dynamicType)")
    }
  % end
  }
}

runAllTests()