| //===--- ArrayShared.swift ------------------------------------*- swift -*-===// |
| // |
| // This source file is part of the Swift.org open source project |
| // |
| // Copyright (c) 2014 - 2018 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 |
| // |
| |
| /// This type is used as a result of the _checkSubscript call to associate the |
| /// call with the array access call it guards. |
| @_fixed_layout |
| public struct _DependenceToken { |
| @inlinable |
| public init() { |
| } |
| } |
| |
| /// Returns an Array of `_count` uninitialized elements using the |
| /// given `storage`, and a pointer to uninitialized memory for the |
| /// first element. |
| /// |
| /// This function is referenced by the compiler to allocate array literals. |
| /// |
| /// - Precondition: `storage` is `_ContiguousArrayStorage`. |
| @inline(__always) |
| public // COMPILER_INTRINSIC |
| func _allocateUninitializedArray<Element>(_ builtinCount: Builtin.Word) |
| -> (Array<Element>, Builtin.RawPointer) { |
| let count = Int(builtinCount) |
| if count > 0 { |
| // Doing the actual buffer allocation outside of the array.uninitialized |
| // semantics function enables stack propagation of the buffer. |
| let bufferObject = Builtin.allocWithTailElems_1( |
| _ContiguousArrayStorage<Element>.self, builtinCount, Element.self) |
| |
| let (array, ptr) = Array<Element>._adoptStorage(bufferObject, count: count) |
| return (array, ptr._rawValue) |
| } |
| // For an empty array no buffer allocation is needed. |
| let (array, ptr) = Array<Element>._allocateUninitialized(count) |
| return (array, ptr._rawValue) |
| } |
| |
| // Referenced by the compiler to deallocate array literals on the |
| // error path. |
| @inlinable |
| @_semantics("array.dealloc_uninitialized") |
| public // COMPILER_INTRINSIC |
| func _deallocateUninitializedArray<Element>( |
| _ array: __owned Array<Element> |
| ) { |
| var array = array |
| array._deallocateUninitialized() |
| } |
| |
| |
| |
| // Utility method for collections that wish to implement CustomStringConvertible |
| // and CustomDebugStringConvertible using a bracketed list of elements, |
| // like an array. |
| @inlinable // FIXME(sil-serialize-all) |
| internal func _makeCollectionDescription<C: Collection> |
| (for items: C, withTypeName type: String?) -> String { |
| var result = "" |
| if let type = type { |
| result += "\(type)([" |
| } else { |
| result += "[" |
| } |
| var first = true |
| for item in items { |
| if first { |
| first = false |
| } else { |
| result += ", " |
| } |
| debugPrint(item, terminator: "", to: &result) |
| } |
| result += type != nil ? "])" : "]" |
| return result |
| } |
| |
| extension _ArrayBufferProtocol { |
| @inlinable // FIXME @useableFromInline https://bugs.swift.org/browse/SR-7588 |
| @inline(never) |
| internal mutating func _arrayOutOfPlaceReplace<C: Collection>( |
| _ bounds: Range<Int>, |
| with newValues: __owned C, |
| count insertCount: Int |
| ) where C.Element == Element { |
| |
| let growth = insertCount - bounds.count |
| let newCount = self.count + growth |
| var newBuffer = _forceCreateUniqueMutableBuffer( |
| newCount: newCount, requiredCapacity: newCount) |
| |
| _arrayOutOfPlaceUpdate( |
| &newBuffer, bounds.lowerBound - startIndex, insertCount, |
| { rawMemory, count in |
| var p = rawMemory |
| var q = newValues.startIndex |
| for _ in 0..<count { |
| p.initialize(to: newValues[q]) |
| newValues.formIndex(after: &q) |
| p += 1 |
| } |
| _expectEnd(of: newValues, is: q) |
| } |
| ) |
| } |
| } |
| |
| /// A _debugPrecondition check that `i` has exactly reached the end of |
| /// `s`. This test is never used to ensure memory safety; that is |
| /// always guaranteed by measuring `s` once and re-using that value. |
| @inlinable |
| internal func _expectEnd<C: Collection>(of s: C, is i: C.Index) { |
| _debugPrecondition( |
| i == s.endIndex, |
| "invalid Collection: count differed in successive traversals") |
| } |
| |
| @inlinable |
| internal func _growArrayCapacity(_ capacity: Int) -> Int { |
| return capacity * 2 |
| } |
| |
| //===--- generic helpers --------------------------------------------------===// |
| |
| extension _ArrayBufferProtocol { |
| /// Create a unique mutable buffer that has enough capacity to hold 'newCount' |
| /// elements and at least 'requiredCapacity' elements. Set the count of the new |
| /// buffer to 'newCount'. The content of the buffer is uninitialized. |
| /// The formula used to compute the new buffers capacity is: |
| /// max(requiredCapacity, source.capacity) if newCount <= source.capacity |
| /// max(requiredCapacity, _growArrayCapacity(source.capacity)) otherwise |
| @inline(never) |
| @inlinable // @specializable |
| internal func _forceCreateUniqueMutableBuffer( |
| newCount: Int, requiredCapacity: Int |
| ) -> _ContiguousArrayBuffer<Element> { |
| return _forceCreateUniqueMutableBufferImpl( |
| countForBuffer: newCount, minNewCapacity: newCount, |
| requiredCapacity: requiredCapacity) |
| } |
| |
| /// Create a unique mutable buffer that has enough capacity to hold |
| /// 'minNewCapacity' elements and set the count of the new buffer to |
| /// 'countForNewBuffer'. The content of the buffer uninitialized. |
| /// The formula used to compute the new buffers capacity is: |
| /// max(minNewCapacity, source.capacity) if minNewCapacity <= source.capacity |
| /// max(minNewCapacity, _growArrayCapacity(source.capacity)) otherwise |
| @inline(never) |
| @inlinable // @specializable |
| internal func _forceCreateUniqueMutableBuffer( |
| countForNewBuffer: Int, minNewCapacity: Int |
| ) -> _ContiguousArrayBuffer<Element> { |
| return _forceCreateUniqueMutableBufferImpl( |
| countForBuffer: countForNewBuffer, minNewCapacity: minNewCapacity, |
| requiredCapacity: minNewCapacity) |
| } |
| |
| /// Create a unique mutable buffer that has enough capacity to hold |
| /// 'minNewCapacity' elements and at least 'requiredCapacity' elements and set |
| /// the count of the new buffer to 'countForBuffer'. The content of the buffer |
| /// uninitialized. |
| /// The formula used to compute the new capacity is: |
| /// max(requiredCapacity, source.capacity) if minNewCapacity <= source.capacity |
| /// max(requiredCapacity, _growArrayCapacity(source.capacity)) otherwise |
| @inlinable |
| internal func _forceCreateUniqueMutableBufferImpl( |
| countForBuffer: Int, minNewCapacity: Int, |
| requiredCapacity: Int |
| ) -> _ContiguousArrayBuffer<Element> { |
| _sanityCheck(countForBuffer >= 0) |
| _sanityCheck(requiredCapacity >= countForBuffer) |
| _sanityCheck(minNewCapacity >= countForBuffer) |
| |
| let minimumCapacity = Swift.max(requiredCapacity, |
| minNewCapacity > capacity |
| ? _growArrayCapacity(capacity) : capacity) |
| |
| return _ContiguousArrayBuffer( |
| _uninitializedCount: countForBuffer, minimumCapacity: minimumCapacity) |
| } |
| } |
| |
| extension _ArrayBufferProtocol { |
| /// Initialize the elements of dest by copying the first headCount |
| /// items from source, calling initializeNewElements on the next |
| /// uninitialized element, and finally by copying the last N items |
| /// from source into the N remaining uninitialized elements of dest. |
| /// |
| /// As an optimization, may move elements out of source rather than |
| /// copying when it isUniquelyReferenced. |
| @inline(never) |
| @inlinable // @specializable |
| internal mutating func _arrayOutOfPlaceUpdate( |
| _ dest: inout _ContiguousArrayBuffer<Element>, |
| _ headCount: Int, // Count of initial source elements to copy/move |
| _ newCount: Int, // Number of new elements to insert |
| _ initializeNewElements: |
| ((UnsafeMutablePointer<Element>, _ count: Int) -> ()) = { ptr, count in |
| _sanityCheck(count == 0) |
| } |
| ) { |
| |
| _sanityCheck(headCount >= 0) |
| _sanityCheck(newCount >= 0) |
| |
| // Count of trailing source elements to copy/move |
| let sourceCount = self.count |
| let tailCount = dest.count - headCount - newCount |
| _sanityCheck(headCount + tailCount <= sourceCount) |
| |
| let oldCount = sourceCount - headCount - tailCount |
| let destStart = dest.firstElementAddress |
| let newStart = destStart + headCount |
| let newEnd = newStart + newCount |
| |
| // Check to see if we have storage we can move from |
| if let backing = requestUniqueMutableBackingBuffer( |
| minimumCapacity: sourceCount) { |
| |
| let sourceStart = firstElementAddress |
| let oldStart = sourceStart + headCount |
| |
| // Destroy any items that may be lurking in a _SliceBuffer before |
| // its real first element |
| let backingStart = backing.firstElementAddress |
| let sourceOffset = sourceStart - backingStart |
| backingStart.deinitialize(count: sourceOffset) |
| |
| // Move the head items |
| destStart.moveInitialize(from: sourceStart, count: headCount) |
| |
| // Destroy unused source items |
| oldStart.deinitialize(count: oldCount) |
| |
| initializeNewElements(newStart, newCount) |
| |
| // Move the tail items |
| newEnd.moveInitialize(from: oldStart + oldCount, count: tailCount) |
| |
| // Destroy any items that may be lurking in a _SliceBuffer after |
| // its real last element |
| let backingEnd = backingStart + backing.count |
| let sourceEnd = sourceStart + sourceCount |
| sourceEnd.deinitialize(count: backingEnd - sourceEnd) |
| backing.count = 0 |
| } |
| else { |
| let headStart = startIndex |
| let headEnd = headStart + headCount |
| let newStart = _copyContents( |
| subRange: headStart..<headEnd, |
| initializing: destStart) |
| initializeNewElements(newStart, newCount) |
| let tailStart = headEnd + oldCount |
| let tailEnd = endIndex |
| _copyContents(subRange: tailStart..<tailEnd, initializing: newEnd) |
| } |
| self = Self(_buffer: dest, shiftedToStartIndex: startIndex) |
| } |
| } |
| |
| extension _ArrayBufferProtocol { |
| @inline(never) |
| @usableFromInline |
| internal mutating func _outlinedMakeUniqueBuffer(bufferCount: Int) { |
| |
| if _fastPath( |
| requestUniqueMutableBackingBuffer(minimumCapacity: bufferCount) != nil) { |
| return |
| } |
| |
| var newBuffer = _forceCreateUniqueMutableBuffer( |
| newCount: bufferCount, requiredCapacity: bufferCount) |
| _arrayOutOfPlaceUpdate(&newBuffer, bufferCount, 0) |
| } |
| |
| /// Append items from `newItems` to a buffer. |
| @inlinable |
| internal mutating func _arrayAppendSequence<S: Sequence>( |
| _ newItems: __owned S |
| ) where S.Element == Element { |
| |
| // this function is only ever called from append(contentsOf:) |
| // which should always have exhausted its capacity before calling |
| _sanityCheck(count == capacity) |
| var newCount = self.count |
| |
| // there might not be any elements to append remaining, |
| // so check for nil element first, then increase capacity, |
| // then inner-loop to fill that capacity with elements |
| var stream = newItems.makeIterator() |
| var nextItem = stream.next() |
| while nextItem != nil { |
| |
| // grow capacity, first time around and when filled |
| var newBuffer = _forceCreateUniqueMutableBuffer( |
| countForNewBuffer: newCount, |
| // minNewCapacity handles the exponential growth, just |
| // need to request 1 more than current count/capacity |
| minNewCapacity: newCount + 1) |
| |
| _arrayOutOfPlaceUpdate(&newBuffer, newCount, 0) |
| |
| let currentCapacity = self.capacity |
| let base = self.firstElementAddress |
| |
| // fill while there is another item and spare capacity |
| while let next = nextItem, newCount < currentCapacity { |
| (base + newCount).initialize(to: next) |
| newCount += 1 |
| nextItem = stream.next() |
| } |
| self.count = newCount |
| } |
| } |
| } |