Permalink
Switch branches/tags
4.1-dont-hardcode-numbers-in-objc-block-sil 5.0-dont-hardcode-numbers-in-objc-block-sil Character-test-patch Compare-types-with-equal-equal SR-2545 TensorFlowLite UnicodeEncoding add-swift-libcxx-and-swift-clang-tools-extra add-test-for-asan-compiler-crash anotherdayanothercommit asyncawait bananaphone builtin-int128 cherr42 codable_test_comment_fix core-team-resolution-2017-05-10 dabrahams-append-contentsOf-replaceRange dcci-build-script-backend demangledmepatatino distributed-test dwa-where-clause-cleanup empty-collection-debugPrecondition external-swift-stdlib _fastCStringContents fix-macos-build-runtime fixmeSC generic-typealias-1-lldb gsb-superclass gyb-nested-expand hoist-to-stringprotocol hoist-to-stringprotocol.1 inhibit-implicit-conversions inline-ASCII-grapheme-fastpaths is-swift-bit-5 latest-emacs-fix-fix marcrasi-const-evaluator-part-1 marcrasi-const-evaluator-part-2 marcrasi-const-evaluator-part-3 marcrasi-last-irgen-attrs marcrasi-static-assert master-llvm-swift5-transition master-next master move-debugging-executables-into-its-own-section no-6-figure-benchmarks owned_fix patatinomio pr-66bbf1369684fc75517cfe6a12718d3cdf6a09d6 pr-94ee6e6c6e2d268f47f17dead77e4feb169c24e6 preservesugar rdar-43033749-fix-batch-mode-no-diags-swift-5.0-branch readme-add-tf-gpu remotemirrorsfixmacho remove-narrow-perf-hack revert-12818-cover-model revert-12843-force-on-named-lazy-member-loading revert-13168-large_type_lldb_workaround revert-13438-re-cover-model revert-13597-master revert-14840-concat_thin revert-14846-rdar-37790062-alt revert-15421-disable_autolinkextract revert-15602-deserialize-clang-importer-witness-tables-4.2 revert-16072-disable_failing_test revert-16149-rdar39629937-master revert-16188-assert-metadata-mangled-name-roundtrip revert-17271-DIOptWritePR revert-17370-raj-cp-allargs revert-17668-master revert-18066-sr8022-workaround revert-18156-generalized-accessors revert-18226-42480588 revert-18315-fix-argument-convention revert-18500-swift-syntax-dependency revert-18624-unbreak_unified_linux_builds revert-19006-error-bridging-integer-type revert-19050-revert-19006-error-bridging-integer-type revert-19097-fluctuation-of-the-pupil revert-19130-run-remote-run revert-19138-revert-19130-run-remote-run revert-19202-rework-type-checking-designated-protocol revert-19253-serialize-generic-typealias revert-19300-explicit-implicit-conversion revert-19447-fix-req-diagnstics-not-to-print-special-names revert-19500-updateValue-but-not-the-key revert-19689-keep-sourcekitd-response-alive-while-variant-lives revert-20129-make-nsobject-hashvalue-final revert-20187-another-42247881 revert-20191-revert-20190-rdar45708367 revert-20444-rdar-45659733-5.0 revert-20561-multi-payload-xi revert-20846-swift-5.0-default-to-gold-linker revert-20956-irgen-invariant-load revert-21199-14 rst-to-markdown runtime-fix-swift-error-box-comparison rxwei-patch-1 sequence=collection shahmishal-patch-1 shahmishal/swift-4.2-branch-update shahmishal/test-swift-4.2-branch silgen-tests-should-build-modules silgen-transform-null-context-3.0 stable static-rangereplaceable-plus stdlib-BidirectionalCollection.removeLast stdlib-default-RangeReplaceableCollection.SubSequence-3.0 stdlib-indexing stdlib-manual stdlib-swift4-build substring-views substring swift-2.2-branch swift-2.2-with-migration-attributes swift-2.3-branch swift-3.0-branch swift-3.0-preview-1-branch swift-3.0-preview-2-branch swift-3.0-preview-3-branch swift-3.0-preview-4-branch swift-3.0-preview-5-branch swift-3.0-preview-5-speculative swift-3.0.1-preview-2-branch swift-3.1-branch swift-4.0-branch-04-18-2017 swift-4.0-branch-06-02-2017 swift-4.0-branch-06-23-2017 swift-4.0-branch-07-11-2017 swift-4.0-branch-10-10-2017 swift-4.0-branch swift-4.1-branch swift-4.2-branch-03-26-2018 swift-4.2-branch-04-20-2018 swift-4.2-branch-04-30-2018 swift-4.2-branch-06-11-2018 swift-4.2-branch swift-4.2-xcode-10-beta-5 swift-5.0-branch-10-15-2018 swift-5.0-branch-11-16-2018 swift-5.0-branch-12-12-2018 swift-5.0-branch swift-master-xcode-10-beta-5 swiftstringview-specialization tensorflow-merge tensorflow the-runtime-stands-alone-5 typelist-existential unicode-rethink unioc update-checkout-swift-5
Nothing to show
Find file Copy path
346 lines (309 sloc) 11 KB
//===--- Filter.swift -----------------------------------------*- 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
//
//===----------------------------------------------------------------------===//
/// A sequence whose elements consist of the elements of some base
/// sequence that also satisfy a given predicate.
///
/// - Note: `s.lazy.filter { ... }`, for an arbitrary sequence `s`,
/// is a `LazyFilterSequence`.
@_fixed_layout // lazy-performance
public struct LazyFilterSequence<Base: Sequence> {
@usableFromInline // lazy-performance
internal var _base: Base
/// The predicate used to determine which elements produced by
/// `base` are also produced by `self`.
@usableFromInline // lazy-performance
internal let _predicate: (Base.Element) -> Bool
/// Creates an instance consisting of the elements `x` of `base` for
/// which `isIncluded(x) == true`.
@inlinable // lazy-performance
public // @testable
init(_base base: Base, _ isIncluded: @escaping (Base.Element) -> Bool) {
self._base = base
self._predicate = isIncluded
}
}
extension LazyFilterSequence {
/// An iterator over the elements traversed by some base iterator that also
/// satisfy a given predicate.
///
/// - Note: This is the associated `Iterator` of `LazyFilterSequence`
/// and `LazyFilterCollection`.
@_fixed_layout // lazy-performance
public struct Iterator {
/// The underlying iterator whose elements are being filtered.
public var base: Base.Iterator { return _base }
@usableFromInline // lazy-performance
internal var _base: Base.Iterator
@usableFromInline // lazy-performance
internal let _predicate: (Base.Element) -> Bool
/// Creates an instance that produces the elements `x` of `base`
/// for which `isIncluded(x) == true`.
@inlinable // lazy-performance
internal init(_base: Base.Iterator, _ isIncluded: @escaping (Base.Element) -> Bool) {
self._base = _base
self._predicate = isIncluded
}
}
}
extension LazyFilterSequence.Iterator: IteratorProtocol, Sequence {
public typealias Element = Base.Element
/// 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`.
///
/// - Precondition: `next()` has not been applied to a copy of `self`
/// since the copy was made.
@inlinable // lazy-performance
public mutating func next() -> Element? {
while let n = _base.next() {
if _predicate(n) {
return n
}
}
return nil
}
}
extension LazyFilterSequence: Sequence {
public typealias Element = Base.Element
/// Returns an iterator over the elements of this sequence.
///
/// - Complexity: O(1).
@inlinable // lazy-performance
public __consuming func makeIterator() -> Iterator {
return Iterator(_base: _base.makeIterator(), _predicate)
}
@inlinable
public func _customContainsEquatableElement(_ element: Element) -> Bool? {
// optimization to check the element first matches the predicate
guard _predicate(element) else { return false }
return _base._customContainsEquatableElement(element)
}
}
extension LazyFilterSequence: LazySequenceProtocol { }
/// A lazy `Collection` wrapper that includes the elements of an
/// underlying collection that satisfy a predicate.
///
/// - Note: The performance of accessing `startIndex`, `first`, any methods
/// that depend on `startIndex`, or of advancing an index depends
/// on how sparsely the filtering predicate is satisfied, and may not offer
/// the usual performance given by `Collection`. Be aware, therefore, that
/// general operations on `LazyFilterCollection` instances may not have the
/// documented complexity.
public typealias LazyFilterCollection<T: Collection> = LazyFilterSequence<T>
extension LazyFilterCollection: Collection {
public typealias SubSequence = LazyFilterCollection<Base.SubSequence>
// Any estimate of the number of elements that pass `_predicate` requires
// iterating the collection and evaluating each element, which can be costly,
// is unexpected, and usually doesn't pay for itself in saving time through
// preventing intermediate reallocations. (SR-4164)
@inlinable // lazy-performance
public var underestimatedCount: Int { return 0 }
/// A type that represents a valid position in the collection.
///
/// Valid indices consist of the position of every element and a
/// "past the end" position that's not valid for use as a subscript.
public typealias Index = Base.Index
/// The position of the first element in a non-empty collection.
///
/// In an empty collection, `startIndex == endIndex`.
///
/// - Complexity: O(*n*), where *n* is the ratio between unfiltered and
/// filtered collection counts.
@inlinable // lazy-performance
public var startIndex: Index {
var index = _base.startIndex
while index != _base.endIndex && !_predicate(_base[index]) {
_base.formIndex(after: &index)
}
return index
}
/// The collection's "past the end" position---that is, the position one
/// greater than the last valid subscript argument.
///
/// `endIndex` is always reachable from `startIndex` by zero or more
/// applications of `index(after:)`.
@inlinable // lazy-performance
public var endIndex: Index {
return _base.endIndex
}
// TODO: swift-3-indexing-model - add docs
@inlinable // lazy-performance
public func index(after i: Index) -> Index {
var i = i
formIndex(after: &i)
return i
}
@inlinable // lazy-performance
public func formIndex(after i: inout Index) {
// TODO: swift-3-indexing-model: _failEarlyRangeCheck i?
var index = i
_precondition(index != _base.endIndex, "Can't advance past endIndex")
repeat {
_base.formIndex(after: &index)
} while index != _base.endIndex && !_predicate(_base[index])
i = index
}
@inline(__always)
@inlinable // lazy-performance
internal func _advanceIndex(_ i: inout Index, step: Int) {
repeat {
_base.formIndex(&i, offsetBy: step)
} while i != _base.endIndex && !_predicate(_base[i])
}
@inline(__always)
@inlinable // lazy-performance
internal func _ensureBidirectional(step: Int) {
// FIXME: This seems to be the best way of checking whether _base is
// forward only without adding an extra protocol requirement.
// index(_:offsetBy:limitedBy:) is chosen becuase it is supposed to return
// nil when the resulting index lands outside the collection boundaries,
// and therefore likely does not trap in these cases.
if step < 0 {
_ = _base.index(
_base.endIndex, offsetBy: step, limitedBy: _base.startIndex)
}
}
@inlinable // lazy-performance
public func distance(from start: Index, to end: Index) -> Int {
// The following line makes sure that distance(from:to:) is invoked on the
// _base at least once, to trigger a _precondition in forward only
// collections.
_ = _base.distance(from: start, to: end)
var _start: Index
let _end: Index
let step: Int
if start > end {
_start = end
_end = start
step = -1
}
else {
_start = start
_end = end
step = 1
}
var count = 0
while _start != _end {
count += step
formIndex(after: &_start)
}
return count
}
@inlinable // lazy-performance
public func index(_ i: Index, offsetBy n: Int) -> Index {
var i = i
let step = n.signum()
// The following line makes sure that index(_:offsetBy:) is invoked on the
// _base at least once, to trigger a _precondition in forward only
// collections.
_ensureBidirectional(step: step)
for _ in 0 ..< abs(numericCast(n)) {
_advanceIndex(&i, step: step)
}
return i
}
@inlinable // lazy-performance
public func formIndex(_ i: inout Index, offsetBy n: Int) {
i = index(i, offsetBy: n)
}
@inlinable // lazy-performance
public func index(
_ i: Index, offsetBy n: Int, limitedBy limit: Index
) -> Index? {
var i = i
let step = n.signum()
// The following line makes sure that index(_:offsetBy:limitedBy:) is
// invoked on the _base at least once, to trigger a _precondition in
// forward only collections.
_ensureBidirectional(step: step)
for _ in 0 ..< abs(numericCast(n)) {
if i == limit {
return nil
}
_advanceIndex(&i, step: step)
}
return i
}
@inlinable // lazy-performance
public func formIndex(
_ i: inout Index, offsetBy n: Int, limitedBy limit: Index
) -> Bool {
if let advancedIndex = index(i, offsetBy: n, limitedBy: limit) {
i = advancedIndex
return true
}
i = limit
return false
}
/// Accesses the element at `position`.
///
/// - Precondition: `position` is a valid position in `self` and
/// `position != endIndex`.
@inlinable // lazy-performance
public subscript(position: Index) -> Element {
return _base[position]
}
@inlinable // lazy-performance
public subscript(bounds: Range<Index>) -> SubSequence {
return SubSequence(_base: _base[bounds], _predicate)
}
@inlinable
public func _customLastIndexOfEquatableElement(_ element: Element) -> Index?? {
guard _predicate(element) else { return .some(nil) }
return _base._customLastIndexOfEquatableElement(element)
}
}
extension LazyFilterCollection: LazyCollectionProtocol { }
extension LazyFilterCollection : BidirectionalCollection
where Base : BidirectionalCollection {
@inlinable // lazy-performance
public func index(before i: Index) -> Index {
var i = i
formIndex(before: &i)
return i
}
@inlinable // lazy-performance
public func formIndex(before i: inout Index) {
// TODO: swift-3-indexing-model: _failEarlyRangeCheck i?
var index = i
_precondition(index != _base.startIndex, "Can't retreat before startIndex")
repeat {
_base.formIndex(before: &index)
} while !_predicate(_base[index])
i = index
}
}
extension LazySequenceProtocol {
/// Returns the elements of `self` that satisfy `isIncluded`.
///
/// - Note: The elements of the result are computed on-demand, as
/// the result is used. No buffering storage is allocated and each
/// traversal step invokes `predicate` on one or more underlying
/// elements.
@inlinable // lazy-performance
public __consuming func filter(
_ isIncluded: @escaping (Elements.Element) -> Bool
) -> LazyFilterSequence<Self.Elements> {
return LazyFilterSequence(_base: self.elements, isIncluded)
}
}
extension LazyFilterSequence {
@available(swift, introduced: 5)
public __consuming func filter(
_ isIncluded: @escaping (Element) -> Bool
) -> LazyFilterSequence<Base> {
return LazyFilterSequence(_base: _base) {
isIncluded($0) && self._predicate($0)
}
}
}