stdlib/public/core/Stride.swift.gyb - third_party/swift - Git at Google

 //===--- Stride.swift.gyb - Components for stride(...) iteration ----------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//

 /// Conforming types are notionally continuous, one-dimensional
 /// values that can be offset and measured.
 ///
 /// - Important: The `Strideable` protocol provides default implementations for
 ///   the equal-to (`==`) and less-than (`<`) operators that depend on the
 ///   `Stride` type's implementations. If a type conforming to `Strideable`
 ///   is its own `Stride` type, it must provide concrete implementations of
 ///   the two operators to avoid infinite recursion.
 public protocol Strideable : Comparable {
   /// A type that represents the distance between two values of `Self`.
   associatedtype Stride : SignedNumeric, Comparable

   /// Returns a stride `x` such that `self.advanced(by: x)` approximates
   /// `other`.
   ///
   /// If `Stride` conforms to `Integer`, then `self.advanced(by: x) == other`.
   ///
   /// - Complexity: O(1).
   func distance(to other: Self) -> Stride

   /// Returns a `Self` `x` such that `self.distance(to: x)` approximates `n`.
   ///
   /// If `Stride` conforms to `Integer`, then `self.distance(to: x) == n`.
   ///
   /// - Complexity: O(1).
   func advanced(by n: Stride) -> Self

   /// `_step` is an implementation detail of Strideable; do not use it directly.
   static func _step(
     after current: (index: Int?, value: Self),
     from start: Self, by distance: Self.Stride
   ) -> (index: Int?, value: Self)

   associatedtype _DisabledRangeIndex = _DisabledRangeIndex_
 }

 extension Strideable {
   @_inlineable
   public static func < (x: Self, y: Self) -> Bool {
     return x.distance(to: y) > 0
   }

   @_inlineable
   public static func == (x: Self, y: Self) -> Bool {
     return x.distance(to: y) == 0
   }
 }

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

 %{
   # Strideable used to provide + and - unconditionally. With the updated
   # collection indexing model of Swift 3 this became unnecessary for integer
   # types, and was deprecated, as it was a way to write mixed-type arithmetic
   # expressions, that are otherwise are not allowed.
 }%
 % for Base, VersionInfo in [
 %   ('Strideable where Self : _Pointer', None),
 %   ('Strideable', 'deprecated: 3, obsoleted: 4'),
 %   ]:
 %   Availability = '@available(swift, %s, message: "Please use explicit type conversions or Strideable methods for mixed-type arithmetics.")' % (VersionInfo) if VersionInfo else ''

 extension ${Base} {
   @_inlineable // FIXME(sil-serialize-all)
   @_transparent
   ${Availability}
   public static func + (lhs: Self, rhs: Self.Stride) -> Self {
     return lhs.advanced(by: rhs)
   }

   @_inlineable // FIXME(sil-serialize-all)
   @_transparent
   ${Availability}
   public static func + (lhs: Self.Stride, rhs: Self) -> Self {
     return rhs.advanced(by: lhs)
   }

   @_inlineable // FIXME(sil-serialize-all)
   @_transparent
   ${Availability}
   public static func - (lhs: Self, rhs: Self.Stride) -> Self {
     return lhs.advanced(by: -rhs)
   }

   @_inlineable // FIXME(sil-serialize-all)
   @_transparent
   ${Availability}
   public static func - (lhs: Self, rhs: Self) -> Self.Stride {
     return rhs.distance(to: lhs)
   }

   @_inlineable // FIXME(sil-serialize-all)
   @_transparent
   ${Availability}
   public static func += (lhs: inout Self, rhs: Self.Stride) {
     lhs = lhs.advanced(by: rhs)
   }

   @_inlineable // FIXME(sil-serialize-all)
   @_transparent
   ${Availability}
   public static func -= (lhs: inout Self, rhs: Self.Stride) {
     lhs = lhs.advanced(by: -rhs)
   }
 }

 % end

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

 extension Strideable {
   @_inlineable
   public static func _step(
     after current: (index: Int?, value: Self),
     from start: Self, by distance: Self.Stride
   ) -> (index: Int?, value: Self) {
     return (nil, current.value.advanced(by: distance))
   }
 }

 extension Strideable where Stride : FloatingPoint {
   @_inlineable
   public static func _step(
     after current: (index: Int?, value: Self),
     from start: Self, by distance: Self.Stride
   ) -> (index: Int?, value: Self) {
     if let i = current.index {
       return (i + 1, start.advanced(by: Stride(i + 1) * distance))
     }
     // If current.index == nil, either we're just starting out (in which case
     // the next index is 1), or we should proceed without an index just as
     // though this floating point specialization doesn't exist.
     return (current.value == start ? 1 : nil,
             current.value.advanced(by: distance))
   }
 }

 /// An iterator for `StrideTo<Element>`.
 @_fixed_layout
 public struct StrideToIterator<Element : Strideable> : IteratorProtocol {
   @_versioned
   internal let _start: Element

   @_versioned
   internal let _end: Element

   @_versioned
   internal let _stride: Element.Stride

   @_versioned
   internal var _current: (index: Int?, value: Element)

   @_inlineable
   @_versioned
   internal init(_start: Element, end: Element, stride: Element.Stride) {
     self._start = _start
     _end = end
     _stride = stride
     _current = (nil, _start)
   }

   /// Advances to the next element and returns it, or `nil` if no next element
   /// exists.
   ///
   /// Once `nil` has been returned, all subsequent calls return `nil`.

   @_inlineable
   public mutating func next() -> Element? {
     let result = _current.value
     if _stride > 0 ? result >= _end : result <= _end {
       return nil
     }
     _current = Element._step(after: _current, from: _start, by: _stride)
     return result
   }
 }

 /// A `Sequence` of values formed by striding over a half-open interval.
 @_fixed_layout
 public struct StrideTo<Element : Strideable> : Sequence, CustomReflectable {
   // FIXME: should really be a Collection, as it is multipass

   /// Returns an iterator over the elements of this sequence.
   ///
   /// - Complexity: O(1).
   @_inlineable
   public func makeIterator() -> StrideToIterator<Element> {
     return StrideToIterator(_start: _start, end: _end, stride: _stride)
   }

   @_inlineable
   public func _preprocessingPass<R>(
     _ preprocess: () throws -> R
   ) rethrows -> R? {
     return try preprocess()
   }

   @_inlineable
   public func _customContainsEquatableElement(
     _ element: Element
   ) -> Bool? {
     if element < _start || _end <= element {
       return false
     }
     return nil
   }

   @_inlineable
   @_versioned
   internal init(_start: Element, end: Element, stride: Element.Stride) {
     _precondition(stride != 0, "Stride size must not be zero")
     // At start, striding away from end is allowed; it just makes for an
     // already-empty Sequence.
     self._start = _start
     self._end = end
     self._stride = stride
   }

   @_versioned
   internal let _start: Element

   @_versioned
   internal let _end: Element

   @_versioned
   internal let _stride: Element.Stride

   @_inlineable // FIXME(sil-serialize-all)
   public var customMirror: Mirror {
     return Mirror(self, children: ["from": _start, "to": _end, "by": _stride])
   }

   // FIXME(conditional-conformances): this is O(N) instead of O(1), leaving it
   // here until a proper Collection conformance is possible
   @_inlineable
   public var underestimatedCount: Int {
     var it = self.makeIterator()
     var count = 0
     while it.next() != nil {
       count += 1
     }
     return count
   }
 }

 // FIXME(conditional-conformances): these extra types can easily be turned into
 // conditional extensions to StrideTo type
 % for Self, ElementConstraint, Where in [
 %   ('IntegerStrideToCollection', 'BinaryInteger', 'Element.Stride : BinaryInteger'),
 %   ('FloatingPointStrideToCollection', 'BinaryFloatingPoint', 'Element.Stride == Element'),
 % ]:
 %   ElementIsInteger = ElementConstraint == 'BinaryInteger'

 internal struct ${Self}<
   Element : ${ElementConstraint}
 > : RandomAccessCollection, CustomReflectable
 where ${Where} {

 //===----------------------------------------------------------------------===//
 // This block is copied from StrideTo struct definition                       //
 //===----------------------------------------------------------------------===//
   @_inlineable
   public func makeIterator() -> StrideToIterator<Element> {
     return StrideToIterator(_start: _start, end: _end, stride: _stride)
   }

   @_inlineable
   public func _customContainsEquatableElement(
     _ element: Element
   ) -> Bool? {
     if element < _start || _end <= element {
       return false
     }
     return nil
   }

   @_inlineable
   @_versioned
   internal init(_start: Element, end: Element, stride: Element.Stride) {
     _precondition(stride != 0, "Stride size must not be zero")
     // At start, striding away from end is allowed; it just makes for an
     // already-empty Sequence.
     self._start = _start
     self._end = end
     self._stride = stride
   }

   @_versioned
   internal let _start: Element

   @_versioned
   internal let _end: Element

   @_versioned
   internal let _stride: Element.Stride

   @_inlineable // FIXME(sil-serialize-all)
   public var customMirror: Mirror {
     return Mirror(self, children: ["from": _start, "to": _end, "by": _stride])
   }
 //===----------------------------------------------------------------------===//
 // The end of the copied block
 //===----------------------------------------------------------------------===//

   // RandomAccessCollection conformance
   public typealias Index = Int
   public typealias SubSequence = RandomAccessSlice<${Self}>
   public typealias Indices = CountableRange<Int>

   public var startIndex: Index { return 0 }
   public var endIndex: Index { return count }

   public var count: Int {
     let (start, end, stride) =
       (_stride > 0) ? (_start, _end, _stride) : (_end, _start, -_stride)
 %   if ElementIsInteger:
     return Int((start.distance(to: end) - 1) / stride) + 1
 %   else:
     let nonExactCount = (start.distance(to: end)) / stride
     return Int(nonExactCount.rounded(.toNearestOrAwayFromZero))
 %   end
   }

   public subscript(position: Index) -> Element {
     _failEarlyRangeCheck(position, bounds: startIndex ..< endIndex)
     return _indexToElement(position)
   }

   public subscript(bounds: Range<Index>) -> RandomAccessSlice<${Self}> {
     _failEarlyRangeCheck(bounds, bounds: startIndex ..< endIndex)
     return RandomAccessSlice(base: self, bounds: bounds)
   }

   public func index(after i: Index) -> Index {
     _failEarlyRangeCheck(i, bounds: startIndex-1 ..< endIndex)
     return i+1
   }

   public func index(before i: Index) -> Index {
     _failEarlyRangeCheck(i, bounds: startIndex+1 ... endIndex)
     return i-1
   }

   @inline(__always)
   internal func _indexToElement(_ i: Index) -> Element {
     return _start.advanced(by: Element.Stride(i) * _stride)
   }
 }

 % end

 /// Returns the sequence of values (`self`, `self + stride`, `self +
 /// 2 * stride`, ... *last*) where *last* is the last value in the
 /// progression that is less than `end`.
 @_inlineable
 public func stride<T>(
   from start: T, to end: T, by stride: T.Stride
 ) -> StrideTo<T> {
   return StrideTo(_start: start, end: end, stride: stride)
 }

 /// An iterator for `StrideThrough<Element>`.
 @_fixed_layout
 public struct StrideThroughIterator<Element : Strideable> : IteratorProtocol {
   @_versioned
   internal let _start: Element

   @_versioned
   internal let _end: Element

   @_versioned
   internal let _stride: Element.Stride

   @_versioned
   internal var _current: (index: Int?, value: Element)

   @_versioned
   internal var _didReturnEnd: Bool = false

   @_inlineable
   @_versioned
   internal init(_start: Element, end: Element, stride: Element.Stride) {
     self._start = _start
     _end = end
     _stride = stride
     _current = (nil, _start)
   }

   /// Advances to the next element and returns it, or `nil` if no next element
   /// exists.
   ///
   /// Once `nil` has been returned, all subsequent calls return `nil`.
   @_inlineable
   public mutating func next() -> Element? {
     let result = _current.value
     if _stride > 0 ? result >= _end : result <= _end {
       // This check is needed because if we just changed the above operators
       // to > and <, respectively, we might advance current past the end
       // and throw it out of bounds (e.g. above Int.max) unnecessarily.
       if result == _end && !_didReturnEnd {
         _didReturnEnd = true
         return result
       }
       return nil
     }
     _current = Element._step(after: _current, from: _start, by: _stride)
     return result
   }
 }

 /// A `Sequence` of values formed by striding over a closed interval.
 @_fixed_layout
 public struct StrideThrough<
   Element : Strideable
 > : Sequence, CustomReflectable {
   // FIXME: should really be a CollectionType, as it is multipass

   /// Returns an iterator over the elements of this sequence.
   ///
   /// - Complexity: O(1).
   @_inlineable
   public func makeIterator() -> StrideThroughIterator<Element> {
     return StrideThroughIterator(_start: _start, end: _end, stride: _stride)
   }

   @_inlineable
   public func _preprocessingPass<R>(
     _ preprocess: () throws -> R
   ) rethrows -> R? {
     return try preprocess()
   }

   @_inlineable
   public func _customContainsEquatableElement(
     _ element: Element
   ) -> Bool? {
     if element < _start || _end < element {
       return false
     }
     return nil
   }

   @_inlineable
   @_versioned
   internal init(_start: Element, end: Element, stride: Element.Stride) {
     _precondition(stride != 0, "Stride size must not be zero")
     self._start = _start
     self._end = end
     self._stride = stride
   }

   @_versioned
   internal let _start: Element
   @_versioned
   internal let _end: Element
   @_versioned
   internal let _stride: Element.Stride

   @_inlineable // FIXME(sil-serialize-all)
   public var customMirror: Mirror {
     return Mirror(self,
       children: ["from": _start, "through": _end, "by": _stride])
   }

   // FIXME(conditional-conformances): this is O(N) instead of O(1), leaving it
   // here until a proper Collection conformance is possible
   @_inlineable
   public var underestimatedCount: Int {
     var it = self.makeIterator()
     var count = 0
     while it.next() != nil {
       count += 1
     }
     return count
   }
 }

 // FIXME(conditional-conformances): these extra types can easily be turned into
 // conditional extensions to StrideThrough type
 % for Self, ElementConstraint, Where in [
 %   ('IntegerStrideThroughCollection', 'BinaryInteger', 'Element.Stride : BinaryInteger'),
 %   ('FloatingPointStrideThroughCollection', 'BinaryFloatingPoint', 'Element.Stride == Element'),
 % ]:
 %   ElementIsInteger = ElementConstraint == 'BinaryInteger'

 internal struct ${Self}<
   Element : ${ElementConstraint}
 > : RandomAccessCollection, CustomReflectable
 where ${Where} {

 //===----------------------------------------------------------------------===//
 // This block is copied from StrideThrough struct definition                  //
 //===----------------------------------------------------------------------===//
   /// Returns an iterator over the elements of this sequence.
   ///
   /// - Complexity: O(1).
   @_inlineable
   public func makeIterator() -> StrideThroughIterator<Element> {
     return StrideThroughIterator(_start: _start, end: _end, stride: _stride)
   }

   @_inlineable
   public func _customContainsEquatableElement(
     _ element: Element
   ) -> Bool? {
     if element < _start || _end < element {
       return false
     }
     return nil
   }

   @_inlineable
   @_versioned
   internal init(_start: Element, end: Element, stride: Element.Stride) {
     _precondition(stride != 0, "Stride size must not be zero")
     self._start = _start
     self._end = end
     self._stride = stride
   }

   @_versioned
   internal let _start: Element
   @_versioned
   internal let _end: Element
   @_versioned
   internal let _stride: Element.Stride

   @_inlineable // FIXME(sil-serialize-all)
   public var customMirror: Mirror {
     return Mirror(self,
       children: ["from": _start, "through": _end, "by": _stride])
   }
 //===----------------------------------------------------------------------===//
 // The end of the copied block
 //===----------------------------------------------------------------------===//

   // RandomAccessCollection conformance
   public typealias Index = ClosedRangeIndex<Int>
   public typealias IndexDistance = Int
   public typealias SubSequence = RandomAccessSlice<${Self}>

   @_inlineable
   public var startIndex: Index { return ClosedRangeIndex(0) }
   @_inlineable
   public var endIndex: Index { return ClosedRangeIndex() }

   @_inlineable
   public var count: Int {
     let (start, end, stride) =
       (_stride > 0) ? (_start, _end, _stride) : (_end, _start, -_stride)
 %   if ElementIsInteger:
     return Int(start.distance(to: end) / stride) + 1
 %   else:
     let nonExactCount = start.distance(to: end) / stride
     return Int(nonExactCount.rounded(.toNearestOrAwayFromZero)) + 1
 %   end
   }

   public subscript(position: Index) -> Element {
     let offset = Element.Stride(position._dereferenced) * _stride
     return _start.advanced(by: offset)
   }

   public subscript(bounds: Range<Index>) -> RandomAccessSlice<${Self}> {
     return RandomAccessSlice(base: self, bounds: bounds)
   }

   @_inlineable
   public func index(before i: Index) -> Index {
     switch i._value {
     case .inRange(let n):
       _precondition(n > 0, "Incrementing past start index")
       return ClosedRangeIndex(n - 1)
     case .pastEnd:
       _precondition(_end >= _start, "Incrementing past start index")
       return ClosedRangeIndex(count - 1)
     }
   }

   @_inlineable
   public func index(after i: Index) -> Index {
     switch i._value {
     case .inRange(let n):
       return n == (count - 1)
         ? ClosedRangeIndex()
         : ClosedRangeIndex(n + 1)
     case .pastEnd:
       _preconditionFailure("Incrementing past end index")
     }
   }
 }

 % end

 /// Returns the sequence of values (`self`, `self + stride`, `self +
 /// 2 * stride`, ... *last*) where *last* is the last value in the
 /// progression less than or equal to `end`.
 ///
 /// - Note: There is no guarantee that `end` is an element of the sequence.
 @_inlineable
 public func stride<T>(
   from start: T, through end: T, by stride: T.Stride
 ) -> StrideThrough<T> {
   return StrideThrough(_start: start, end: end, stride: stride)
 }
	//===--- Stride.swift.gyb - Components for stride(...) iteration ----------===//
	//
	// 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
	//
	//===----------------------------------------------------------------------===//

	/// Conforming types are notionally continuous, one-dimensional
	/// values that can be offset and measured.
	///
	/// - Important: The `Strideable` protocol provides default implementations for
	/// the equal-to (`==`) and less-than (`<`) operators that depend on the
	/// `Stride` type's implementations. If a type conforming to `Strideable`
	/// is its own `Stride` type, it must provide concrete implementations of
	/// the two operators to avoid infinite recursion.
	public protocol Strideable : Comparable {
	/// A type that represents the distance between two values of `Self`.
	associatedtype Stride : SignedNumeric, Comparable

	/// Returns a stride `x` such that `self.advanced(by: x)` approximates
	/// `other`.
	///
	/// If `Stride` conforms to `Integer`, then `self.advanced(by: x) == other`.
	///
	/// - Complexity: O(1).
	func distance(to other: Self) -> Stride

	/// Returns a `Self` `x` such that `self.distance(to: x)` approximates `n`.
	///
	/// If `Stride` conforms to `Integer`, then `self.distance(to: x) == n`.
	///
	/// - Complexity: O(1).
	func advanced(by n: Stride) -> Self

	/// `_step` is an implementation detail of Strideable; do not use it directly.
	static func _step(
	after current: (index: Int?, value: Self),
	from start: Self, by distance: Self.Stride
	) -> (index: Int?, value: Self)

	associatedtype _DisabledRangeIndex = _DisabledRangeIndex_
	}

	extension Strideable {
	@_inlineable
	public static func < (x: Self, y: Self) -> Bool {
	return x.distance(to: y) > 0
	}

	@_inlineable
	public static func == (x: Self, y: Self) -> Bool {
	return x.distance(to: y) == 0
	}
	}

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

	%{
	# Strideable used to provide + and - unconditionally. With the updated
	# collection indexing model of Swift 3 this became unnecessary for integer
	# types, and was deprecated, as it was a way to write mixed-type arithmetic
	# expressions, that are otherwise are not allowed.
	}%
	% for Base, VersionInfo in [
	% ('Strideable where Self : _Pointer', None),
	% ('Strideable', 'deprecated: 3, obsoleted: 4'),
	% ]:
	% Availability = '@available(swift, %s, message: "Please use explicit type conversions or Strideable methods for mixed-type arithmetics.")' % (VersionInfo) if VersionInfo else ''

	extension ${Base} {
	@_inlineable // FIXME(sil-serialize-all)
	@_transparent
	${Availability}
	public static func + (lhs: Self, rhs: Self.Stride) -> Self {
	return lhs.advanced(by: rhs)
	}

	@_inlineable // FIXME(sil-serialize-all)
	@_transparent
	${Availability}
	public static func + (lhs: Self.Stride, rhs: Self) -> Self {
	return rhs.advanced(by: lhs)
	}

	@_inlineable // FIXME(sil-serialize-all)
	@_transparent
	${Availability}
	public static func - (lhs: Self, rhs: Self.Stride) -> Self {
	return lhs.advanced(by: -rhs)
	}

	@_inlineable // FIXME(sil-serialize-all)
	@_transparent
	${Availability}
	public static func - (lhs: Self, rhs: Self) -> Self.Stride {
	return rhs.distance(to: lhs)
	}

	@_inlineable // FIXME(sil-serialize-all)
	@_transparent
	${Availability}
	public static func += (lhs: inout Self, rhs: Self.Stride) {
	lhs = lhs.advanced(by: rhs)
	}

	@_inlineable // FIXME(sil-serialize-all)
	@_transparent
	${Availability}
	public static func -= (lhs: inout Self, rhs: Self.Stride) {
	lhs = lhs.advanced(by: -rhs)
	}
	}

	% end

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

	extension Strideable {
	@_inlineable
	public static func _step(
	after current: (index: Int?, value: Self),
	from start: Self, by distance: Self.Stride
	) -> (index: Int?, value: Self) {
	return (nil, current.value.advanced(by: distance))
	}
	}

	extension Strideable where Stride : FloatingPoint {
	@_inlineable
	public static func _step(
	after current: (index: Int?, value: Self),
	from start: Self, by distance: Self.Stride
	) -> (index: Int?, value: Self) {
	if let i = current.index {
	return (i + 1, start.advanced(by: Stride(i + 1) * distance))
	}
	// If current.index == nil, either we're just starting out (in which case
	// the next index is 1), or we should proceed without an index just as
	// though this floating point specialization doesn't exist.
	return (current.value == start ? 1 : nil,
	current.value.advanced(by: distance))
	}
	}

	/// An iterator for `StrideTo<Element>`.
	@_fixed_layout
	public struct StrideToIterator<Element : Strideable> : IteratorProtocol {
	@_versioned
	internal let _start: Element

	@_versioned
	internal let _end: Element

	@_versioned
	internal let _stride: Element.Stride

	@_versioned
	internal var _current: (index: Int?, value: Element)

	@_inlineable
	@_versioned
	internal init(_start: Element, end: Element, stride: Element.Stride) {
	self._start = _start
	_end = end
	_stride = stride
	_current = (nil, _start)
	}

	/// Advances to the next element and returns it, or `nil` if no next element
	/// exists.
	///
	/// Once `nil` has been returned, all subsequent calls return `nil`.

	@_inlineable
	public mutating func next() -> Element? {
	let result = _current.value
	if _stride > 0 ? result >= _end : result <= _end {
	return nil
	}
	_current = Element._step(after: _current, from: _start, by: _stride)
	return result
	}
	}

	/// A `Sequence` of values formed by striding over a half-open interval.
	@_fixed_layout
	public struct StrideTo<Element : Strideable> : Sequence, CustomReflectable {
	// FIXME: should really be a Collection, as it is multipass

	/// Returns an iterator over the elements of this sequence.
	///
	/// - Complexity: O(1).
	@_inlineable
	public func makeIterator() -> StrideToIterator<Element> {
	return StrideToIterator(_start: _start, end: _end, stride: _stride)
	}

	@_inlineable
	public func _preprocessingPass<R>(
	_ preprocess: () throws -> R
	) rethrows -> R? {
	return try preprocess()
	}

	@_inlineable
	public func _customContainsEquatableElement(
	_ element: Element
	) -> Bool? {
	if element < _start \|\| _end <= element {
	return false
	}
	return nil
	}

	@_inlineable
	@_versioned
	internal init(_start: Element, end: Element, stride: Element.Stride) {
	_precondition(stride != 0, "Stride size must not be zero")
	// At start, striding away from end is allowed; it just makes for an
	// already-empty Sequence.
	self._start = _start
	self._end = end
	self._stride = stride
	}

	@_versioned
	internal let _start: Element

	@_versioned
	internal let _end: Element

	@_versioned
	internal let _stride: Element.Stride

	@_inlineable // FIXME(sil-serialize-all)
	public var customMirror: Mirror {
	return Mirror(self, children: ["from": _start, "to": _end, "by": _stride])
	}

	// FIXME(conditional-conformances): this is O(N) instead of O(1), leaving it
	// here until a proper Collection conformance is possible
	@_inlineable
	public var underestimatedCount: Int {
	var it = self.makeIterator()
	var count = 0
	while it.next() != nil {
	count += 1
	}
	return count
	}
	}

	// FIXME(conditional-conformances): these extra types can easily be turned into
	// conditional extensions to StrideTo type
	% for Self, ElementConstraint, Where in [
	% ('IntegerStrideToCollection', 'BinaryInteger', 'Element.Stride : BinaryInteger'),
	% ('FloatingPointStrideToCollection', 'BinaryFloatingPoint', 'Element.Stride == Element'),
	% ]:
	% ElementIsInteger = ElementConstraint == 'BinaryInteger'

	internal struct ${Self}<
	Element : ${ElementConstraint}
	> : RandomAccessCollection, CustomReflectable
	where ${Where} {

	//===----------------------------------------------------------------------===//
	// This block is copied from StrideTo struct definition //
	//===----------------------------------------------------------------------===//
	@_inlineable
	public func makeIterator() -> StrideToIterator<Element> {
	return StrideToIterator(_start: _start, end: _end, stride: _stride)
	}

	@_inlineable
	public func _customContainsEquatableElement(
	_ element: Element
	) -> Bool? {
	if element < _start \|\| _end <= element {
	return false
	}
	return nil
	}

	@_inlineable
	@_versioned
	internal init(_start: Element, end: Element, stride: Element.Stride) {
	_precondition(stride != 0, "Stride size must not be zero")
	// At start, striding away from end is allowed; it just makes for an
	// already-empty Sequence.
	self._start = _start
	self._end = end
	self._stride = stride
	}

	@_versioned
	internal let _start: Element

	@_versioned
	internal let _end: Element

	@_versioned
	internal let _stride: Element.Stride

	@_inlineable // FIXME(sil-serialize-all)
	public var customMirror: Mirror {
	return Mirror(self, children: ["from": _start, "to": _end, "by": _stride])
	}
	//===----------------------------------------------------------------------===//
	// The end of the copied block
	//===----------------------------------------------------------------------===//

	// RandomAccessCollection conformance
	public typealias Index = Int
	public typealias SubSequence = RandomAccessSlice<${Self}>
	public typealias Indices = CountableRange<Int>

	public var startIndex: Index { return 0 }
	public var endIndex: Index { return count }

	public var count: Int {
	let (start, end, stride) =
	(_stride > 0) ? (_start, _end, _stride) : (_end, _start, -_stride)
	% if ElementIsInteger:
	return Int((start.distance(to: end) - 1) / stride) + 1
	% else:
	let nonExactCount = (start.distance(to: end)) / stride
	return Int(nonExactCount.rounded(.toNearestOrAwayFromZero))
	% end
	}

	public subscript(position: Index) -> Element {
	_failEarlyRangeCheck(position, bounds: startIndex ..< endIndex)
	return _indexToElement(position)
	}

	public subscript(bounds: Range<Index>) -> RandomAccessSlice<${Self}> {
	_failEarlyRangeCheck(bounds, bounds: startIndex ..< endIndex)
	return RandomAccessSlice(base: self, bounds: bounds)
	}

	public func index(after i: Index) -> Index {
	_failEarlyRangeCheck(i, bounds: startIndex-1 ..< endIndex)
	return i+1
	}

	public func index(before i: Index) -> Index {
	_failEarlyRangeCheck(i, bounds: startIndex+1 ... endIndex)
	return i-1
	}

	@inline(__always)
	internal func _indexToElement(_ i: Index) -> Element {
	return _start.advanced(by: Element.Stride(i) * _stride)
	}
	}

	% end

	/// Returns the sequence of values (`self`, `self + stride`, `self +
	/// 2 * stride`, ... last) where last is the last value in the
	/// progression that is less than `end`.
	@_inlineable
	public func stride<T>(
	from start: T, to end: T, by stride: T.Stride
	) -> StrideTo<T> {
	return StrideTo(_start: start, end: end, stride: stride)
	}

	/// An iterator for `StrideThrough<Element>`.
	@_fixed_layout
	public struct StrideThroughIterator<Element : Strideable> : IteratorProtocol {
	@_versioned
	internal let _start: Element

	@_versioned
	internal let _end: Element

	@_versioned
	internal let _stride: Element.Stride

	@_versioned
	internal var _current: (index: Int?, value: Element)

	@_versioned
	internal var _didReturnEnd: Bool = false

	@_inlineable
	@_versioned
	internal init(_start: Element, end: Element, stride: Element.Stride) {
	self._start = _start
	_end = end
	_stride = stride
	_current = (nil, _start)
	}

	/// Advances to the next element and returns it, or `nil` if no next element
	/// exists.
	///
	/// Once `nil` has been returned, all subsequent calls return `nil`.
	@_inlineable
	public mutating func next() -> Element? {
	let result = _current.value
	if _stride > 0 ? result >= _end : result <= _end {
	// This check is needed because if we just changed the above operators
	// to > and <, respectively, we might advance current past the end
	// and throw it out of bounds (e.g. above Int.max) unnecessarily.
	if result == _end && !_didReturnEnd {
	_didReturnEnd = true
	return result
	}
	return nil
	}
	_current = Element._step(after: _current, from: _start, by: _stride)
	return result
	}
	}

	/// A `Sequence` of values formed by striding over a closed interval.
	@_fixed_layout
	public struct StrideThrough<
	Element : Strideable
	> : Sequence, CustomReflectable {
	// FIXME: should really be a CollectionType, as it is multipass

	/// Returns an iterator over the elements of this sequence.
	///
	/// - Complexity: O(1).
	@_inlineable
	public func makeIterator() -> StrideThroughIterator<Element> {
	return StrideThroughIterator(_start: _start, end: _end, stride: _stride)
	}

	@_inlineable
	public func _preprocessingPass<R>(
	_ preprocess: () throws -> R
	) rethrows -> R? {
	return try preprocess()
	}

	@_inlineable
	public func _customContainsEquatableElement(
	_ element: Element
	) -> Bool? {
	if element < _start \|\| _end < element {
	return false
	}
	return nil
	}

	@_inlineable
	@_versioned
	internal init(_start: Element, end: Element, stride: Element.Stride) {
	_precondition(stride != 0, "Stride size must not be zero")
	self._start = _start
	self._end = end
	self._stride = stride
	}

	@_versioned
	internal let _start: Element
	@_versioned
	internal let _end: Element
	@_versioned
	internal let _stride: Element.Stride

	@_inlineable // FIXME(sil-serialize-all)
	public var customMirror: Mirror {
	return Mirror(self,
	children: ["from": _start, "through": _end, "by": _stride])
	}

	// FIXME(conditional-conformances): this is O(N) instead of O(1), leaving it
	// here until a proper Collection conformance is possible
	@_inlineable
	public var underestimatedCount: Int {
	var it = self.makeIterator()
	var count = 0
	while it.next() != nil {
	count += 1
	}
	return count
	}
	}

	// FIXME(conditional-conformances): these extra types can easily be turned into
	// conditional extensions to StrideThrough type
	% for Self, ElementConstraint, Where in [
	% ('IntegerStrideThroughCollection', 'BinaryInteger', 'Element.Stride : BinaryInteger'),
	% ('FloatingPointStrideThroughCollection', 'BinaryFloatingPoint', 'Element.Stride == Element'),
	% ]:
	% ElementIsInteger = ElementConstraint == 'BinaryInteger'

	internal struct ${Self}<
	Element : ${ElementConstraint}
	> : RandomAccessCollection, CustomReflectable
	where ${Where} {

	//===----------------------------------------------------------------------===//
	// This block is copied from StrideThrough struct definition //
	//===----------------------------------------------------------------------===//
	/// Returns an iterator over the elements of this sequence.
	///
	/// - Complexity: O(1).
	@_inlineable
	public func makeIterator() -> StrideThroughIterator<Element> {
	return StrideThroughIterator(_start: _start, end: _end, stride: _stride)
	}

	@_inlineable
	public func _customContainsEquatableElement(
	_ element: Element
	) -> Bool? {
	if element < _start \|\| _end < element {
	return false
	}
	return nil
	}

	@_inlineable
	@_versioned
	internal init(_start: Element, end: Element, stride: Element.Stride) {
	_precondition(stride != 0, "Stride size must not be zero")
	self._start = _start
	self._end = end
	self._stride = stride
	}

	@_versioned
	internal let _start: Element
	@_versioned
	internal let _end: Element
	@_versioned
	internal let _stride: Element.Stride

	@_inlineable // FIXME(sil-serialize-all)
	public var customMirror: Mirror {
	return Mirror(self,
	children: ["from": _start, "through": _end, "by": _stride])
	}
	//===----------------------------------------------------------------------===//
	// The end of the copied block
	//===----------------------------------------------------------------------===//

	// RandomAccessCollection conformance
	public typealias Index = ClosedRangeIndex<Int>
	public typealias IndexDistance = Int
	public typealias SubSequence = RandomAccessSlice<${Self}>

	@_inlineable
	public var startIndex: Index { return ClosedRangeIndex(0) }
	@_inlineable
	public var endIndex: Index { return ClosedRangeIndex() }

	@_inlineable
	public var count: Int {
	let (start, end, stride) =
	(_stride > 0) ? (_start, _end, _stride) : (_end, _start, -_stride)
	% if ElementIsInteger:
	return Int(start.distance(to: end) / stride) + 1
	% else:
	let nonExactCount = start.distance(to: end) / stride
	return Int(nonExactCount.rounded(.toNearestOrAwayFromZero)) + 1
	% end
	}

	public subscript(position: Index) -> Element {
	let offset = Element.Stride(position._dereferenced) * _stride
	return _start.advanced(by: offset)
	}

	public subscript(bounds: Range<Index>) -> RandomAccessSlice<${Self}> {
	return RandomAccessSlice(base: self, bounds: bounds)
	}

	@_inlineable
	public func index(before i: Index) -> Index {
	switch i._value {
	case .inRange(let n):
	_precondition(n > 0, "Incrementing past start index")
	return ClosedRangeIndex(n - 1)
	case .pastEnd:
	_precondition(_end >= _start, "Incrementing past start index")
	return ClosedRangeIndex(count - 1)
	}
	}

	@_inlineable
	public func index(after i: Index) -> Index {
	switch i._value {
	case .inRange(let n):
	return n == (count - 1)
	? ClosedRangeIndex()
	: ClosedRangeIndex(n + 1)
	case .pastEnd:
	_preconditionFailure("Incrementing past end index")
	}
	}
	}

	% end

	/// Returns the sequence of values (`self`, `self + stride`, `self +
	/// 2 * stride`, ... last) where last is the last value in the
	/// progression less than or equal to `end`.
	///
	/// - Note: There is no guarantee that `end` is an element of the sequence.
	@_inlineable
	public func stride<T>(
	from start: T, through end: T, by stride: T.Stride
	) -> StrideThrough<T> {
	return StrideThrough(_start: start, end: end, stride: stride)
	}