//===--- 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', '_Indexable', 'after', 'end'),
%  ('dec', '_BidirectionalIndexable', '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.Iterator.Element, ${TRACE}
) where
  Instances : Collection,
  BaseCollection : ${protocol},
  Instances.Iterator.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.Iterator.Element,
  sign: BaseCollection.IndexDistance, // 1 or -1
  next: (Instances.Iterator.Element) -> Instances.Iterator.Element,
  ${TRACE}
) where
  Instances : Collection,
  BaseCollection : _Indexable,
  Instances.Iterator.Element == BaseCollection.Index {
  for i in instances {
    let d: BaseCollection.IndexDistance = sign > 0 ?
      baseCollection.distance(from: i, to: limit) :
      -baseCollection.distance(from: limit, to: i)

    var offset: BaseCollection.IndexDistance = 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.Iterator.Element, ${TRACE}
) where
  Instances : Collection,
  BaseCollection : _Indexable,
  Instances.Iterator.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.Iterator.Element,
  endIndex: Instances.Iterator.Element,
  ${TRACE}
) where
  Instances: Collection,
  BaseCollection : _BidirectionalIndexable,
  Instances.Iterator.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.Iterator.Element,
  advanceOracle:
    (Instances.Index, Distances.Index) -> Instances.Iterator.Element,
  startIndex: Instances.Iterator.Element,
  endIndex: Instances.Iterator.Element,
  ${TRACE}
) where
  Instances : Collection,
  Distances : Collection,
  BaseCollection : _RandomAccessIndexable,
  Instances.Iterator.Element == BaseCollection.Index,
  Distances.Iterator.Element == BaseCollection.IndexDistance {

  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.Iterator.Element,
  advanceOracle:
    (Instances.Index, Distances.Index) -> Instances.Iterator.Element,
  ${TRACE}
) where
  Instances : Collection,
  Distances : Collection,
  BaseCollection : _Indexable,
  Instances.Iterator.Element == BaseCollection.Index,
  Distances.Iterator.Element == BaseCollection.IndexDistance {

  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.Iterator.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.Iterator.Element == ${Element},
  C.SubSequence : Collection {

  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.Iterator.Element == ${Element},
  C.SubSequence : ${TraversalCollection},
  ${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.Iterator.Element == ${Element},
  C.SubSequence : ${TraversalCollection} {

  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.Iterator.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 = C.IndexDistance

  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.Iterator.Element == ${Element},
  S.SubSequence : ${TraversalCollection} {

  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.Iterator.Element : Equatable,
  C.Iterator.Element == N.Iterator.Element {

  typealias A = C

  // First make an independent copy of the array that we can use for
  // comparison later.
  let source = Array<A.Iterator.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)")
          }
        }
      }
    }
  }
}