| //===--- MinimalCollections.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, |
| collectionTypeName, |
| protocolsForCollectionFeatures |
| ) |
| }% |
| |
| import StdlibUnittest |
| |
| /// State shared by all generators of a MinimalSequence. |
| internal class _MinimalIteratorSharedState<T> { |
| internal init(_ data: [T]) { |
| self.data = data |
| } |
| |
| internal let data: [T] |
| internal var i: Int = 0 |
| internal var underestimatedCount: Int = 0 |
| } |
| |
| //===----------------------------------------------------------------------===// |
| // MinimalIterator |
| //===----------------------------------------------------------------------===// |
| |
| /// An IteratorProtocol that implements the protocol contract in the most |
| /// narrow way possible. |
| /// |
| /// This generator will return `nil` only once. |
| public struct MinimalIterator<T> : IteratorProtocol { |
| public init<S : Sequence>(_ s: S) where S.Iterator.Element == T { |
| self._sharedState = _MinimalIteratorSharedState(Array(s)) |
| } |
| |
| public init(_ data: [T]) { |
| self._sharedState = _MinimalIteratorSharedState(data) |
| } |
| |
| internal init(_ _sharedState: _MinimalIteratorSharedState<T>) { |
| self._sharedState = _sharedState |
| } |
| |
| public func next() -> T? { |
| if _sharedState.i == _sharedState.data.count { |
| return nil |
| } |
| defer { _sharedState.i += 1 } |
| return _sharedState.data[_sharedState.i] |
| } |
| |
| internal let _sharedState: _MinimalIteratorSharedState<T> |
| } |
| |
| // A protocol to identify MinimalIterator. |
| public protocol _MinimalIterator {} |
| extension MinimalIterator : _MinimalIterator {} |
| |
| //===----------------------------------------------------------------------===// |
| // MinimalSequence |
| //===----------------------------------------------------------------------===// |
| |
| public enum UnderestimatedCountBehavior { |
| /// Return the actual number of elements. |
| case precise |
| |
| /// Return the actual number of elements divided by 2. |
| case half |
| |
| /// Return an overestimated count. Useful to test how algorithms reserve |
| /// memory. |
| case overestimate |
| |
| /// Return the provided value. |
| case value(Int) |
| } |
| |
| /// A Sequence that implements the protocol contract in the most |
| /// narrow way possible. |
| /// |
| /// This sequence is consumed when its generator is advanced. |
| public struct MinimalSequence<T> : Sequence, CustomDebugStringConvertible { |
| public init<S : Sequence>( |
| elements: S, |
| underestimatedCount: UnderestimatedCountBehavior = .value(0) |
| ) where S.Iterator.Element == T { |
| let data = Array(elements) |
| self._sharedState = _MinimalIteratorSharedState(data) |
| |
| switch underestimatedCount { |
| case .precise: |
| self._sharedState.underestimatedCount = data.count |
| |
| case .half: |
| self._sharedState.underestimatedCount = data.count / 2 |
| |
| case .overestimate: |
| self._sharedState.underestimatedCount = data.count * 3 + 5 |
| |
| case .value(let count): |
| self._sharedState.underestimatedCount = count |
| } |
| } |
| |
| public let timesMakeIteratorCalled = ResettableValue(0) |
| |
| public func makeIterator() -> MinimalIterator<T> { |
| timesMakeIteratorCalled.value += 1 |
| return MinimalIterator(_sharedState) |
| } |
| |
| public var underestimatedCount: Int { |
| return Swift.max(0, self._sharedState.underestimatedCount - self._sharedState.i) |
| } |
| |
| public var debugDescription: String { |
| return "MinimalSequence(\(_sharedState.data[_sharedState.i..<_sharedState.data.count]))" |
| } |
| |
| internal let _sharedState: _MinimalIteratorSharedState<T> |
| } |
| |
| //===----------------------------------------------------------------------===// |
| // Index invalidation checking |
| //===----------------------------------------------------------------------===// |
| |
| internal enum _CollectionOperation : Equatable { |
| case reserveCapacity(capacity: Int) |
| case append |
| case appendContentsOf(count: Int) |
| case replaceRange(subRange: Range<Int>, replacementCount: Int) |
| case insert(atIndex: Int) |
| case insertContentsOf(atIndex: Int, count: Int) |
| case removeAtIndex(index: Int) |
| case removeLast |
| case removeRange(subRange: Range<Int>) |
| case removeAll(keepCapacity: Bool) |
| |
| internal func _applyTo( |
| elementsLastMutatedStateIds: [Int], |
| endIndexLastMutatedStateId: Int, |
| nextStateId: Int |
| ) -> ([Int], Int) { |
| var newElementsIds = elementsLastMutatedStateIds |
| var newEndIndexId = endIndexLastMutatedStateId |
| switch self { |
| case .reserveCapacity: |
| let invalidIndices = newElementsIds.indices |
| newElementsIds.replaceSubrange( |
| Range(invalidIndices), |
| with: repeatElement(nextStateId, count: invalidIndices.count)) |
| newEndIndexId = nextStateId |
| |
| case .append: |
| newElementsIds.append(nextStateId) |
| newEndIndexId = nextStateId |
| |
| case .appendContentsOf(let count): |
| newElementsIds.append(contentsOf: |
| repeatElement(nextStateId, count: count)) |
| newEndIndexId = nextStateId |
| |
| case .replaceRange(let subRange, let replacementCount): |
| newElementsIds.replaceSubrange( |
| subRange, |
| with: repeatElement(nextStateId, count: replacementCount)) |
| |
| let invalidIndices = subRange.lowerBound..<newElementsIds.endIndex |
| newElementsIds.replaceSubrange( |
| Range(invalidIndices), |
| with: repeatElement(nextStateId, count: invalidIndices.count)) |
| newEndIndexId = nextStateId |
| |
| case .insert(let atIndex): |
| newElementsIds.insert(nextStateId, at: atIndex) |
| |
| let invalidIndices = atIndex..<newElementsIds.endIndex |
| newElementsIds.replaceSubrange( |
| Range(invalidIndices), |
| with: repeatElement(nextStateId, count: invalidIndices.count)) |
| newEndIndexId = nextStateId |
| |
| case .insertContentsOf(let atIndex, let count): |
| newElementsIds.insert( |
| contentsOf: repeatElement(nextStateId, count: count), |
| at: atIndex) |
| |
| let invalidIndices = atIndex..<newElementsIds.endIndex |
| newElementsIds.replaceSubrange( |
| Range(invalidIndices), |
| with: repeatElement(nextStateId, count: invalidIndices.count)) |
| newEndIndexId = nextStateId |
| |
| case .removeAtIndex(let index): |
| newElementsIds.remove(at: index) |
| |
| let invalidIndices = index..<newElementsIds.endIndex |
| newElementsIds.replaceSubrange( |
| Range(invalidIndices), |
| with: repeatElement(nextStateId, count: invalidIndices.count)) |
| newEndIndexId = nextStateId |
| |
| case .removeLast: |
| newElementsIds.removeLast() |
| newEndIndexId = nextStateId |
| |
| case .removeRange(let subRange): |
| newElementsIds.removeSubrange(subRange) |
| |
| let invalidIndices = subRange.lowerBound..<newElementsIds.endIndex |
| newElementsIds.replaceSubrange( |
| Range(invalidIndices), |
| with: repeatElement(nextStateId, count: invalidIndices.count)) |
| newEndIndexId = nextStateId |
| |
| case .removeAll(let keepCapacity): |
| newElementsIds.removeAll(keepingCapacity: keepCapacity) |
| newEndIndexId = nextStateId |
| } |
| return (newElementsIds, newEndIndexId) |
| } |
| } |
| |
| internal func == ( |
| lhs: _CollectionOperation, |
| rhs: _CollectionOperation |
| ) -> Bool { |
| switch (lhs, rhs) { |
| case (.reserveCapacity(let lhsCapacity), .reserveCapacity(let rhsCapacity)): |
| return lhsCapacity == rhsCapacity |
| |
| case (.append, .append): |
| return true |
| |
| case (.appendContentsOf(let lhsCount), .appendContentsOf(let rhsCount)): |
| return lhsCount == rhsCount |
| |
| case ( |
| .replaceRange(let lhsSubRange, let lhsReplacementCount), |
| .replaceRange(let rhsSubRange, let rhsReplacementCount)): |
| |
| return lhsSubRange == rhsSubRange && |
| lhsReplacementCount == rhsReplacementCount |
| |
| case (.insert(let lhsAtIndex), .insert(let rhsAtIndex)): |
| return lhsAtIndex == rhsAtIndex |
| |
| case ( |
| .insertContentsOf(let lhsAtIndex, let lhsCount), |
| .insertContentsOf(let rhsAtIndex, let rhsCount)): |
| |
| return lhsAtIndex == rhsAtIndex && lhsCount == rhsCount |
| |
| case (.removeAtIndex(let lhsIndex), .removeAtIndex(let rhsIndex)): |
| return lhsIndex == rhsIndex |
| |
| case (.removeLast, .removeLast): |
| return true |
| |
| case (.removeRange(let lhsSubRange), .removeRange(let rhsSubRange)): |
| return lhsSubRange == rhsSubRange |
| |
| case (.removeAll(let lhsKeepCapacity), .removeAll(let rhsKeepCapacity)): |
| return lhsKeepCapacity == rhsKeepCapacity |
| |
| default: |
| return false |
| } |
| } |
| |
| public struct _CollectionState : Equatable, Hashable { |
| internal static var _nextUnusedState: Int = 0 |
| internal static var _namedStates: [String : _CollectionState] = [:] |
| |
| internal let _id: Int |
| internal let _elementsLastMutatedStateIds: [Int] |
| internal let _endIndexLastMutatedStateId: Int |
| |
| internal init( |
| id: Int, |
| elementsLastMutatedStateIds: [Int], |
| endIndexLastMutatedStateId: Int) { |
| self._id = id |
| self._elementsLastMutatedStateIds = elementsLastMutatedStateIds |
| self._endIndexLastMutatedStateId = endIndexLastMutatedStateId |
| } |
| |
| public init(newRootStateForElementCount count: Int) { |
| self._id = _CollectionState._nextUnusedState |
| _CollectionState._nextUnusedState += 1 |
| self._elementsLastMutatedStateIds = |
| Array(repeatElement(self._id, count: count)) |
| self._endIndexLastMutatedStateId = self._id |
| } |
| |
| internal init(name: String, elementCount: Int) { |
| if let result = _CollectionState._namedStates[name] { |
| self = result |
| } else { |
| self = _CollectionState(newRootStateForElementCount: elementCount) |
| _CollectionState._namedStates[name] = self |
| } |
| } |
| |
| public var hashValue: Int { |
| return _id.hashValue |
| } |
| } |
| |
| public func == (lhs: _CollectionState, rhs: _CollectionState) -> Bool { |
| return lhs._id == rhs._id |
| } |
| |
| internal struct _CollectionStateTransition { |
| internal let _previousState: _CollectionState |
| internal let _operation: _CollectionOperation |
| internal let _nextState: _CollectionState |
| |
| internal static var _allTransitions: |
| [_CollectionState : Box<[_CollectionStateTransition]>] = [:] |
| |
| internal init( |
| previousState: _CollectionState, |
| operation: _CollectionOperation, |
| nextState: _CollectionState |
| ) { |
| var transitions = |
| _CollectionStateTransition._allTransitions[previousState] |
| if transitions == nil { |
| transitions = Box<[_CollectionStateTransition]>([]) |
| _CollectionStateTransition._allTransitions[previousState] = transitions |
| } |
| if let i = transitions!.value.index(where: { $0._operation == operation }) { |
| self = transitions!.value[i] |
| return |
| } |
| self._previousState = previousState |
| self._operation = operation |
| self._nextState = nextState |
| transitions!.value.append(self) |
| } |
| |
| internal init( |
| previousState: _CollectionState, |
| operation: _CollectionOperation |
| ) { |
| let nextStateId = _CollectionState._nextUnusedState |
| _CollectionState._nextUnusedState += 1 |
| let (newElementStates, newEndIndexState) = operation._applyTo( |
| elementsLastMutatedStateIds: previousState._elementsLastMutatedStateIds, |
| endIndexLastMutatedStateId: previousState._endIndexLastMutatedStateId, |
| nextStateId: nextStateId) |
| let nextState = _CollectionState( |
| id: nextStateId, |
| elementsLastMutatedStateIds: newElementStates, |
| endIndexLastMutatedStateId: newEndIndexState) |
| self = _CollectionStateTransition( |
| previousState: previousState, |
| operation: operation, |
| nextState: nextState) |
| } |
| } |
| |
| % for Index in ['MinimalIndex', 'MinimalStrideableIndex']: |
| |
| //===----------------------------------------------------------------------===// |
| // ${Index} |
| //===----------------------------------------------------------------------===// |
| |
| /// Asserts that the two indices are allowed to participate in a binary |
| /// operation. |
| internal func _expectCompatibleIndices( |
| _ first: ${Index}, |
| _ second: ${Index}, |
| ${TRACE} |
| ) { |
| if first._collectionState._id == second._collectionState._id { |
| // Fast path: the indices are derived from the same state. |
| return |
| } |
| |
| // The indices are derived from different states. Check that they point |
| // to a self-consistent view of the collection. |
| if first._collectionState._id > second._collectionState._id { |
| return _expectCompatibleIndices(second, first) |
| } |
| |
| func lastMutatedStateId( |
| of i: ${Index}, |
| in state: _CollectionState |
| ) -> Int { |
| let offset = i.position |
| if offset == state._elementsLastMutatedStateIds.endIndex { |
| return state._id |
| } |
| return state._elementsLastMutatedStateIds[offset] |
| } |
| |
| let newestCollectionState = second._collectionState |
| let expectedFirstIndexLastMutatedStateId = |
| lastMutatedStateId(of: first, in: newestCollectionState) |
| |
| expectEqual( |
| expectedFirstIndexLastMutatedStateId, |
| first._collectionState._id, |
| "Indices are not compatible:\n" + |
| "first: \(first)\n" + |
| "second: \(second)\n" + |
| "first element last mutated in state id: \(first._collectionState._id)\n" + |
| "expected state id: \(expectedFirstIndexLastMutatedStateId)\n" + |
| "newest collection state: \(newestCollectionState)", |
| stackTrace: ${stackTrace}) |
| |
| // To make writing assertions easier, perform a trap. |
| if expectedFirstIndexLastMutatedStateId != first._collectionState._id { |
| fatalError("Indices are not compatible") |
| } |
| } |
| |
| public struct ${Index} : Comparable { |
| public init( |
| collectionState: _CollectionState, |
| position: Int, |
| startIndex: Int, |
| endIndex: Int |
| ) { |
| expectTrapping( |
| position, |
| in: startIndex...endIndex) |
| self = ${Index}( |
| _collectionState: collectionState, |
| uncheckedPosition: position) |
| } |
| |
| internal init( |
| _collectionState: _CollectionState, |
| uncheckedPosition: Int |
| ) { |
| self._collectionState = _collectionState |
| self.position = uncheckedPosition |
| } |
| |
| public let _collectionState: _CollectionState |
| public let position: Int |
| |
| public static var trapOnRangeCheckFailure = ResettableValue(true) |
| |
| % if 'Strideable' in Index: |
| public var timesAdvancedCalled = ResettableValue(0) |
| public var timesDistanceCalled = ResettableValue(0) |
| % end |
| } |
| |
| public func == (lhs: ${Index}, rhs: ${Index}) -> Bool { |
| _expectCompatibleIndices(lhs, rhs) |
| return lhs.position == rhs.position |
| } |
| |
| public func < (lhs: ${Index}, rhs: ${Index}) -> Bool { |
| _expectCompatibleIndices(lhs, rhs) |
| return lhs.position < rhs.position |
| } |
| |
| % end |
| |
| extension MinimalStrideableIndex : Strideable { |
| public typealias Stride = Int |
| |
| public func distance(to other: MinimalStrideableIndex) -> Int { |
| timesDistanceCalled.value += 1 |
| _expectCompatibleIndices(self, other) |
| return other.position - position |
| } |
| |
| public func advanced(by n: Int) -> MinimalStrideableIndex { |
| timesAdvancedCalled.value += 1 |
| return MinimalStrideableIndex( |
| _collectionState: _collectionState, |
| uncheckedPosition: position + n) |
| } |
| } |
| |
| //===----------------------------------------------------------------------===// |
| // Minimal***[Mutable]?Collection |
| //===----------------------------------------------------------------------===// |
| |
| /* |
| FIXME: swift-3-indexing-model: generate three variants, with Int, Int8 and |
| Int64 distances. |
| |
| public typealias Distance = {Distance} |
| */ |
| |
| % for Traversal in TRAVERSALS: |
| % for Mutable in [ False, True ]: |
| % for RangeReplaceable in [ False, True ]: |
| % for StrideableIndex in [ False, True ]: |
| % Self = 'Minimal' + collectionTypeName(traversal=Traversal, mutable=Mutable, rangeReplaceable=RangeReplaceable) |
| % Self += 'WithStrideableIndex' if StrideableIndex else '' |
| % SelfProtocols = ', '.join(protocolsForCollectionFeatures(traversal=Traversal, mutable=Mutable, rangeReplaceable=RangeReplaceable)) |
| % Index = 'MinimalStrideableIndex' if StrideableIndex else 'MinimalIndex' |
| % # Only generating MinimalRandomAccessCollectionWithStrideableIndex |
| % if not StrideableIndex or ( |
| % StrideableIndex and Traversal == 'RandomAccess' and |
| % not Mutable): |
| |
| /// A minimal implementation of `Collection` with extra checks. |
| public struct ${Self}<T> : ${SelfProtocols} { |
| /// Creates a collection with given contents, but a unique modification |
| /// history. No other instance has the same modification history. |
| public init<S : Sequence>( |
| elements: S, |
| underestimatedCount: UnderestimatedCountBehavior = .value(0) |
| ) where S.Iterator.Element == T { |
| self._elements = Array(elements) |
| |
| self._collectionState = _CollectionState( |
| newRootStateForElementCount: self._elements.count) |
| |
| switch underestimatedCount { |
| case .precise: |
| self.underestimatedCount = _elements.count |
| |
| case .half: |
| self.underestimatedCount = _elements.count / 2 |
| |
| case .overestimate: |
| self.underestimatedCount = _elements.count * 3 + 5 |
| |
| case .value(let count): |
| self.underestimatedCount = count |
| } |
| } |
| |
| % if StrideableIndex: |
| public typealias Indices = CountableRange<${Index}> |
| % end |
| |
| % if RangeReplaceable: |
| public init() { |
| self.underestimatedCount = 0 |
| self._elements = [] |
| self._collectionState = |
| _CollectionState(name: "\(type(of: self))", elementCount: 0) |
| } |
| |
| public init<S : Sequence>(_ elements: S) where S.Iterator.Element == T { |
| self.underestimatedCount = 0 |
| self._elements = Array(elements) |
| self._collectionState = |
| _CollectionState(newRootStateForElementCount: self._elements.count) |
| } |
| % end |
| |
| public let timesMakeIteratorCalled = ResettableValue(0) |
| |
| public func makeIterator() -> MinimalIterator<T> { |
| timesMakeIteratorCalled.value += 1 |
| return MinimalIterator(_elements) |
| } |
| |
| public typealias Index = ${Index} |
| public typealias IndexDistance = Int |
| |
| internal func _index(forPosition i: Int) -> ${Index} { |
| return ${Index}( |
| collectionState: _collectionState, |
| position: i, |
| startIndex: _elements.startIndex, |
| endIndex: _elements.endIndex) |
| } |
| |
| internal func _uncheckedIndex(forPosition i: Int) -> ${Index} { |
| return ${Index}( |
| _collectionState: _collectionState, |
| uncheckedPosition: i) |
| } |
| |
| public let timesStartIndexCalled = ResettableValue(0) |
| |
| public var startIndex: ${Index} { |
| timesStartIndexCalled.value += 1 |
| return _uncheckedIndex(forPosition: _elements.startIndex) |
| } |
| |
| public let timesEndIndexCalled = ResettableValue(0) |
| |
| public var endIndex: ${Index} { |
| timesEndIndexCalled.value += 1 |
| return _uncheckedIndex(forPosition: _elements.endIndex) |
| } |
| |
| public func _failEarlyRangeCheck( |
| _ index: ${Index}, |
| bounds: Range<${Index}> |
| ) { |
| _expectCompatibleIndices( |
| _uncheckedIndex(forPosition: index.position), |
| index) |
| |
| _expectCompatibleIndices( |
| _uncheckedIndex(forPosition: bounds.lowerBound.position), |
| bounds.lowerBound) |
| _expectCompatibleIndices( |
| _uncheckedIndex(forPosition: bounds.upperBound.position), |
| bounds.upperBound) |
| |
| expectTrapping( |
| index.position, |
| in: bounds.lowerBound.position..<bounds.upperBound.position) |
| } |
| |
| public func _failEarlyRangeCheck( |
| _ range: Range<${Index}>, |
| bounds: Range<${Index}> |
| ) { |
| _expectCompatibleIndices( |
| _uncheckedIndex(forPosition: range.lowerBound.position), |
| range.lowerBound) |
| _expectCompatibleIndices( |
| _uncheckedIndex(forPosition: range.upperBound.position), |
| range.upperBound) |
| |
| _expectCompatibleIndices( |
| _uncheckedIndex(forPosition: bounds.lowerBound.position), |
| bounds.lowerBound) |
| _expectCompatibleIndices( |
| _uncheckedIndex(forPosition: bounds.upperBound.position), |
| bounds.upperBound) |
| |
| expectTrapping( |
| range.lowerBound.position..<range.upperBound.position, |
| in: bounds.lowerBound.position..<bounds.upperBound.position) |
| } |
| |
| public func index(after i: ${Index}) -> ${Index} { |
| _failEarlyRangeCheck(i, bounds: startIndex..<endIndex) |
| return _uncheckedIndex(forPosition: i.position + 1) |
| } |
| |
| % if Traversal in ['Bidirectional', 'RandomAccess']: |
| public func index(before i: ${Index}) -> ${Index} { |
| // FIXME: swift-3-indexing-model: perform a range check and use |
| // return _uncheckedIndex(forPosition: i.position - 1) |
| return _index(forPosition: i.position - 1) |
| } |
| % end |
| |
| public func distance(from start: ${Index}, to end: ${Index}) |
| -> IndexDistance { |
| % if Traversal == 'Forward': |
| _precondition(start <= end, |
| "Only BidirectionalCollections can have end come before start") |
| % end |
| // FIXME: swift-3-indexing-model: perform a range check properly. |
| if start != endIndex { |
| _failEarlyRangeCheck(start, bounds: startIndex..<endIndex) |
| } |
| if end != endIndex { |
| _failEarlyRangeCheck(end, bounds: startIndex..<endIndex) |
| } |
| return end.position - start.position |
| } |
| |
| public func index(_ i: Index, offsetBy n: IndexDistance) -> Index { |
| % if Traversal == 'Forward': |
| _precondition(n >= 0, |
| "Only BidirectionalCollections can be advanced by a negative amount") |
| % end |
| // FIXME: swift-3-indexing-model: perform a range check properly. |
| if i != endIndex { |
| _failEarlyRangeCheck(i, bounds: startIndex..<endIndex) |
| } |
| return _index(forPosition: i.position + n) |
| } |
| |
| public subscript(i: ${Index}) -> T { |
| get { |
| _failEarlyRangeCheck(i, bounds: startIndex..<endIndex) |
| return _elements[i.position] |
| } |
| % if Mutable: |
| set { |
| _failEarlyRangeCheck(i, bounds: startIndex..<endIndex) |
| _elements[i.position] = newValue |
| } |
| % end |
| } |
| |
| public subscript(bounds: Range<${Index}>) -> Slice<${Self}<T>> { |
| get { |
| _failEarlyRangeCheck(bounds, bounds: startIndex..<endIndex) |
| return Slice(base: self, bounds: bounds) |
| } |
| % if Mutable: |
| set { |
| _failEarlyRangeCheck(bounds, bounds: startIndex..<endIndex) |
| _writeBackMutableSlice(&self, bounds: bounds, slice: newValue) |
| } |
| % end |
| } |
| |
| % if RangeReplaceable: |
| public mutating func reserveCapacity(_ n: Int) { |
| _willMutate(.reserveCapacity(capacity: n)) |
| _elements.reserveCapacity(n) |
| reservedCapacity = Swift.max(reservedCapacity, n) |
| } |
| |
| public mutating func append(_ x: T) { |
| _willMutate(.append) |
| _elements.append(x) |
| } |
| |
| public mutating func append<S : Sequence>(contentsOf newElements: S) |
| where S.Iterator.Element == T { |
| let oldCount = count |
| _elements.append(contentsOf: newElements) |
| let newCount = count |
| _willMutate(.appendContentsOf(count: newCount - oldCount)) |
| } |
| |
| public mutating func replaceSubrange<C>( |
| _ subRange: Range<${Index}>, |
| with newElements: C |
| ) where C : Collection, C.Iterator.Element == T { |
| let oldCount = count |
| _elements.replaceSubrange( |
| subRange.lowerBound.position..<subRange.upperBound.position, |
| with: newElements) |
| let newCount = count |
| _willMutate(.replaceRange( |
| subRange: subRange.lowerBound.position..<subRange.upperBound.position, |
| replacementCount: |
| subRange.upperBound.position - subRange.lowerBound.position |
| + newCount - oldCount)) |
| } |
| |
| public mutating func insert(_ newElement: T, at i: ${Index}) { |
| _willMutate(.insert(atIndex: i.position)) |
| _elements.insert(newElement, at: i.position) |
| } |
| |
| public mutating func insert<S : Collection>( |
| contentsOf newElements: S, at i: ${Index} |
| ) where S.Iterator.Element == T { |
| let oldCount = count |
| _elements.insert(contentsOf: newElements, at: i.position) |
| let newCount = count |
| |
| if newCount - oldCount != 0 { |
| _willMutate(.insertContentsOf( |
| atIndex: i.position, |
| count: newCount - oldCount)) |
| } |
| } |
| |
| @discardableResult |
| public mutating func remove(at i: ${Index}) -> T { |
| _willMutate(.removeAtIndex(index: i.position)) |
| return _elements.remove(at: i.position) |
| } |
| |
| @discardableResult |
| public mutating func removeLast() -> T { |
| _willMutate(.removeLast) |
| return _elements.removeLast() |
| } |
| |
| public mutating func removeSubrange(_ subRange: Range<${Index}>) { |
| if !subRange.isEmpty { |
| _willMutate(.removeRange( |
| subRange: subRange.lowerBound.position..<subRange.upperBound.position)) |
| } |
| _elements.removeSubrange( |
| subRange.lowerBound.position..<subRange.upperBound.position |
| ) |
| } |
| |
| public mutating func removeAll(keepingCapacity keepCapacity: Bool = false) { |
| _willMutate(.removeAll(keepCapacity: keepCapacity)) |
| // Ignore the value of `keepCapacity`. |
| _elements.removeAll(keepingCapacity: false) |
| } |
| |
| internal mutating func _willMutate(_ operation: _CollectionOperation) { |
| _collectionState = _CollectionStateTransition( |
| previousState: _collectionState, |
| operation: operation)._nextState |
| } |
| % end |
| |
| public var underestimatedCount: Int |
| % if RangeReplaceable: |
| public var reservedCapacity: Int = 0 |
| % end |
| |
| internal var _elements: [T] |
| % if RangeReplaceable: |
| internal var _collectionState: _CollectionState |
| % else: |
| internal let _collectionState: _CollectionState |
| % end |
| } |
| |
| % end |
| % end |
| % end |
| % end |
| % end |
| |
| /// A Sequence that uses as many default implementations as |
| /// `Sequence` can provide. |
| public struct DefaultedSequence<Element> : Sequence { |
| public let base: MinimalSequence<Element> |
| |
| public init(base: MinimalSequence<Element>) { |
| self.base = base |
| } |
| |
| public init<S : Sequence>( |
| elements: S, |
| underestimatedCount: UnderestimatedCountBehavior = .value(0) |
| ) where S.Iterator.Element == Element { |
| self.init(base: MinimalSequence( |
| elements: elements, underestimatedCount: underestimatedCount)) |
| } |
| |
| public func makeIterator() -> MinimalIterator<Element> { |
| return base.makeIterator() |
| } |
| |
| public var underestimatedCount: Int { |
| return base.underestimatedCount |
| } |
| } |
| |
| % for Traversal in TRAVERSALS: |
| % for Mutable in [ False, True ]: |
| % for RangeReplaceable in [ False, True ]: |
| % for StrideableIndex in [ False, True ]: |
| % Self = 'Defaulted' + collectionTypeName(traversal=Traversal, mutable=Mutable, rangeReplaceable=RangeReplaceable) |
| % Self += 'WithStrideableIndex' if StrideableIndex else '' |
| % Base = 'Minimal' + collectionTypeName(traversal=Traversal, mutable=Mutable, rangeReplaceable=RangeReplaceable) |
| % Base += 'WithStrideableIndex' if StrideableIndex else '' |
| % SelfProtocols = ', '.join(protocolsForCollectionFeatures(traversal=Traversal, mutable=Mutable, rangeReplaceable=RangeReplaceable)) |
| % Index = 'MinimalStrideableIndex' if StrideableIndex else 'MinimalIndex' |
| % # Only generating DefaultedRandomAccessCollectionWithStrideableIndex |
| % if not StrideableIndex or ( |
| % StrideableIndex and Traversal == 'RandomAccess' and |
| % not Mutable and not RangeReplaceable): |
| |
| /// A Collection that uses as many default implementations as |
| /// `Collection` can provide. |
| public struct ${Self}<Element> : ${SelfProtocols} { |
| public typealias Base = ${Base}<Element> |
| public typealias Iterator = MinimalIterator<Element> |
| public typealias Index = ${Index} |
| public typealias IndexDistance = Int |
| |
| % if StrideableIndex: |
| public typealias Indices = CountableRange<${Index}> |
| % end |
| |
| % if Mutable or RangeReplaceable: |
| public var base: Base |
| % else: |
| public let base: Base |
| % end |
| |
| public init(base: Base) { |
| self.base = base |
| } |
| |
| public init(_ array: [Element]) { |
| self.base = Base(elements: array) |
| } |
| |
| public init(elements: [Element]) { |
| self.base = Base(elements: elements) |
| } |
| |
| public init<S : Sequence>( |
| elements: S, |
| underestimatedCount: UnderestimatedCountBehavior = .value(0) |
| ) where S.Iterator.Element == Element { |
| self.init(base: |
| ${Base}(elements: elements, underestimatedCount: underestimatedCount)) |
| } |
| |
| public var underestimatedCount: Int { |
| return base.underestimatedCount |
| } |
| |
| public let timesMakeIteratorCalled = ResettableValue(0) |
| |
| public func makeIterator() -> MinimalIterator<Element> { |
| timesMakeIteratorCalled.value += 1 |
| return base.makeIterator() |
| } |
| |
| % if not StrideableIndex: |
| |
| public let timesSuccessorCalled = ResettableValue(0) |
| |
| public func index(after i: ${Index}) -> ${Index} { |
| timesSuccessorCalled.value += 1 |
| return base.index(after: i) |
| } |
| |
| % if Traversal in ['Bidirectional', 'RandomAccess']: |
| public let timesPredecessorCalled = ResettableValue(0) |
| |
| public func index(before i: ${Index}) -> ${Index} { |
| timesPredecessorCalled.value += 1 |
| return base.index(before: i) |
| } |
| % end |
| |
| % if Traversal == 'RandomAccess': |
| public func distance(from start: ${Index}, to end: ${Index}) |
| -> IndexDistance { |
| return base.distance(from: start, to: end) |
| } |
| |
| public func index(_ i: Index, offsetBy n: IndexDistance) -> Index { |
| return base.index(i, offsetBy: n) |
| } |
| % end |
| |
| % end # if not StrideableIndex |
| |
| public let timesStartIndexCalled = ResettableValue(0) |
| |
| public var startIndex: ${Index} { |
| timesStartIndexCalled.value += 1 |
| return base.startIndex |
| } |
| |
| public let timesEndIndexCalled = ResettableValue(0) |
| |
| public var endIndex: ${Index} { |
| timesEndIndexCalled.value += 1 |
| return base.endIndex |
| } |
| |
| public subscript(i: ${Index}) -> Element { |
| get { |
| return base[i] |
| } |
| % if Mutable: |
| set { |
| base[i] = newValue |
| } |
| % end |
| } |
| |
| // FIXME: swift-3-indexing-model: use defaults. |
| // if Self not in ['DefaultedCollection', 'DefaultedBidirectionalCollection', 'DefaultedRandomAccessCollection', 'DefaultedMutableCollection', 'DefaultedRangeReplaceableCollection']: |
| |
| public subscript(bounds: Range<${Index}>) -> Slice<${Self}<Base.Element>> { |
| get { |
| // FIXME: swift-3-indexing-model: range check. |
| return Slice(base: self, bounds: bounds) |
| } |
| % if Mutable: |
| set { |
| _writeBackMutableSlice(&self, bounds: bounds, slice: newValue) |
| } |
| % end |
| } |
| |
| % if RangeReplaceable: |
| public init() { |
| base = Base() |
| } |
| |
| public mutating func replaceSubrange<C>( |
| _ subRange: Range<${Self}<Element>.Index>, |
| with newElements: C |
| ) where C : Collection, C.Iterator.Element == Element { |
| base.replaceSubrange(subRange, with: newElements) |
| } |
| % end |
| } |
| |
| /* |
| FIXME: swift-3-indexing-model: uncomment this. |
| public struct Defaulted${Traversal}RangeReplaceableSlice<Element> |
| : RangeReplaceableCollection { |
| |
| public typealias Self_ = Defaulted${Traversal}RangeReplaceableSlice<Element> |
| public typealias Base = ${Base}<Element> |
| public typealias Iterator = MinimalIterator<Element> |
| public typealias Index = ${Index} |
| |
| public var base: Base |
| public var startIndex: Index |
| public var endIndex: Index |
| |
| public init() { |
| expectSliceType(Self_.self) |
| |
| self.base = Base() |
| self.startIndex = base.startIndex |
| self.endIndex = base.endIndex |
| } |
| |
| public init(base: Base) { |
| self.base = base |
| self.startIndex = base.startIndex |
| self.endIndex = base.endIndex |
| } |
| |
| public init(base: Base, bounds: Range<Index>) { |
| self.base = base |
| self.startIndex = bounds.lowerBound |
| self.endIndex = bounds.upperBound |
| } |
| |
| public init(_ array: [Element]) { |
| self = Defaulted${Traversal}RangeReplaceableSlice( |
| base: Base(elements: array)) |
| } |
| |
| public init(elements: [Element]) { |
| self = Defaulted${Traversal}RangeReplaceableSlice( |
| base: Base(elements: elements)) |
| } |
| |
| public func makeIterator() -> MinimalIterator<Element> { |
| return MinimalIterator(Array(self)) |
| } |
| |
| public subscript(index: Index) -> Element { |
| Index._failEarlyRangeCheck(index, bounds: startIndex..<endIndex) |
| return base[index] |
| } |
| |
| public subscript(bounds: Range<Index>) -> Self_ { |
| Index._failEarlyRangeCheck2( |
| rangeStart: bounds.lowerBound, |
| rangeEnd: bounds.upperBound, |
| boundsStart: startIndex, |
| boundsEnd: endIndex) |
| return Defaulted${Traversal}RangeReplaceableSlice( |
| base: base, bounds: bounds) |
| } |
| |
| public mutating func replaceSubrange< |
| C : Collection |
| >( |
| _ subRange: Range<Index>, |
| with newElements: C |
| ) where C.Iterator.Element == Element { |
| let startOffset = startIndex.position |
| let endOffset = |
| endIndex.position |
| - subRange.count |
| + numericCast(newElements.count) as Int |
| Index._failEarlyRangeCheck2( |
| rangeStart: subRange.lowerBound, |
| rangeEnd: subRange.upperBound, |
| boundsStart: startIndex, |
| boundsEnd: endIndex) |
| base.replaceSubrange(subRange, with: newElements) |
| startIndex = base.startIndex.advanced(by: startOffset) |
| endIndex = base.startIndex.advanced(by: endOffset) |
| } |
| } |
| */ |
| |
| % end |
| % end |
| % end |
| % end |
| % end |
| |
| // ${'Local Variables'}: |
| // eval: (read-only-mode 1) |
| // End: |