ArrayBuffer.swift

//===--- ArrayBuffer.swift - Dynamic storage for Swift Array --------------===//
//
// 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
//
//===----------------------------------------------------------------------===//
//
// This is the class that implements the storage and object management for
// Swift Array.
//
//===----------------------------------------------------------------------===//

#if _runtime(_ObjC)
import SwiftShims

@usableFromInline
internaltypealias_ArrayBridgeStorage
=_BridgeStorage<__ContiguousArrayStorageBase>

@usableFromInline
@frozen
internalstruct_ArrayBuffer<Element>:_ArrayBufferProtocol{

 /// Create an empty buffer.
@inlinable
internalinit(){
 _storage =_ArrayBridgeStorage(native: _emptyArrayStorage)
}

@inlinable
internalinit(nsArray:AnyObject){
_internalInvariant(_isClassOrObjCExistential(Element.self))
 _storage =_ArrayBridgeStorage(objC: nsArray)
}

 /// Returns an `_ArrayBuffer<U>` containing the same elements.
 ///
 /// - Precondition: The elements actually have dynamic type `U`, and `U`
 /// is a class or `@objc` existential.
@inlinable
 __consuminginternalfunc cast<U>(toBufferOf _:U.Type)->_ArrayBuffer<U>{
_internalInvariant(_isClassOrObjCExistential(Element.self))
_internalInvariant(_isClassOrObjCExistential(U.self))
return_ArrayBuffer<U>(storage: _storage)
}

 /// Returns an `_ArrayBuffer<U>` containing the same elements,
 /// deferring checking each element's `U`-ness until it is accessed.
 ///
 /// - Precondition: `U` is a class or `@objc` existential derived from
 /// `Element`.
@inlinable
 __consuminginternalfunc downcast<U>(
 toBufferWithDeferredTypeCheckOf _:U.Type
)->_ArrayBuffer<U>{
_internalInvariant(_isClassOrObjCExistential(Element.self))
_internalInvariant(_isClassOrObjCExistential(U.self))

 // FIXME: can't check that U is derived from Element pending
 // <rdar://problem/20028320> generic metatype casting doesn't work
 // _internalInvariant(U.self is Element.Type)

return_ArrayBuffer<U>(
 storage:_ArrayBridgeStorage(native: _native._storage, isFlagged:true))
}

@inlinable
internalvarneedsElementTypeCheck:Bool{
 // NSArray's need an element typecheck when the element type isn't AnyObject
return !_isNativeTypeChecked && !(AnyObject.self is Element.Type)
}

 //===--- private --------------------------------------------------------===//
@inlinable
internalinit(storage:_ArrayBridgeStorage){
 _storage = storage
}

@usableFromInline
internalvar_storage:_ArrayBridgeStorage
}

extension_ArrayBuffer{
 /// Adopt the storage of `source`.
@inlinable
internalinit(_buffer source:NativeBuffer, shiftedToStartIndex:Int){
_internalInvariant(shiftedToStartIndex ==0,"shiftedToStartIndex must be 0")
 _storage =_ArrayBridgeStorage(native: source._storage)
}

 /// `true`, if the array is native and does not need a deferred type check.
@inlinable
internalvararrayPropertyIsNativeTypeChecked:Bool{
return _isNativeTypeChecked
}

 /// Returns `true` iff this buffer's storage is uniquely-referenced.
 ///
 /// This function should only be used for internal sanity checks.
 /// To guard a buffer mutation, use `beginCOWMutation`.
@inlinable
internalmutatingfunc isUniquelyReferenced()->Bool{
if !_isClassOrObjCExistential(Element.self){
return _storage.isUniquelyReferencedUnflaggedNative()
}
return _storage.isUniquelyReferencedNative() && _isNative
}

 /// Returns `true` and puts the buffer in a mutable state iff the buffer's
 /// storage is uniquely-referenced.
 ///
 /// - Precondition: The buffer must be immutable.
 ///
 /// - Warning: It's a requirement to call `beginCOWMutation` before the buffer
 /// is mutated.
@_alwaysEmitIntoClient
internalmutatingfunc beginCOWMutation()->Bool{
letisUnique:Bool
if !_isClassOrObjCExistential(Element.self){
 isUnique = _storage.beginCOWMutationUnflaggedNative()
}elseif !_storage.beginCOWMutationNative(){
returnfalse
}else{
 isUnique = _isNative
}
#if INTERNAL_CHECKS_ENABLED
if isUnique {
 _native.isImmutable =false
}
#endif
return isUnique
}

 /// Puts the buffer in an immutable state.
 ///
 /// - Precondition: The buffer must be mutable or the empty array singleton.
 ///
 /// - Warning: After a call to `endCOWMutation` the buffer must not be mutated
 /// until the next call of `beginCOWMutation`.
@_alwaysEmitIntoClient
@inline(__always)
internalmutatingfunc endCOWMutation(){
#if INTERNAL_CHECKS_ENABLED
 _native.isImmutable =true
#endif
 _storage.endCOWMutation()
}

 /// Convert to an NSArray.
 ///
 /// O(1) if the element type is bridged verbatim, O(*n*) otherwise.
@inlinable
internalfunc _asCocoaArray()->AnyObject{
return_fastPath(_isNative)? _native._asCocoaArray(): _nonNative.buffer
}

 /// Creates and returns a new uniquely referenced buffer which is a copy of
 /// this buffer.
 ///
 /// This buffer is consumed, i.e. it's released.
@_alwaysEmitIntoClient
@inline(never)
@_semantics("optimize.sil.specialize.owned2guarantee.never")
internal__consumingfunc _consumeAndCreateNew()->_ArrayBuffer{
return_consumeAndCreateNew(bufferIsUnique:false,
 minimumCapacity: count,
 growForAppend:false)
}

 /// Creates and returns a new uniquely referenced buffer which is a copy of
 /// this buffer.
 ///
 /// If `bufferIsUnique` is true, the buffer is assumed to be uniquely
 /// referenced and the elements are moved - instead of copied - to the new
 /// buffer.
 /// The `minimumCapacity` is the lower bound for the new capacity.
 /// If `growForAppend` is true, the new capacity is calculated using
 /// `_growArrayCapacity`, but at least kept at `minimumCapacity`.
 ///
 /// This buffer is consumed, i.e. it's released.
@_alwaysEmitIntoClient
@inline(never)
@_semantics("optimize.sil.specialize.owned2guarantee.never")
internal__consumingfunc _consumeAndCreateNew(
 bufferIsUnique:Bool, minimumCapacity:Int, growForAppend:Bool
)->_ArrayBuffer{
letnewCapacity=_growArrayCapacity(oldCapacity: capacity,
 minimumCapacity: minimumCapacity,
 growForAppend: growForAppend)
letc= count
_internalInvariant(newCapacity >= c)

letnewBuffer=_ContiguousArrayBuffer<Element>(
 _uninitializedCount: c, minimumCapacity: newCapacity)

if bufferIsUnique {
 // As an optimization, if the original buffer is unique, we can just move
 // the elements instead of copying.
letdest= newBuffer.firstElementAddress
 dest.moveInitialize(from: mutableFirstElementAddress,
 count: c)
 _native.mutableCount =0
}else{
_copyContents(
 subRange:0..<c,
 initializing: newBuffer.mutableFirstElementAddress)
}
return_ArrayBuffer(_buffer: newBuffer, shiftedToStartIndex:0)
}

 /// If this buffer is backed by a uniquely-referenced mutable
 /// `_ContiguousArrayBuffer` that can be grown in-place to allow the self
 /// buffer store minimumCapacity elements, returns that buffer.
 /// Otherwise, returns `nil`.
@inlinable
internalmutatingfunc requestUniqueMutableBackingBuffer(minimumCapacity:Int)
->NativeBuffer?{
if_fastPath(isUniquelyReferenced()){
letb= _native
if_fastPath(b.mutableCapacity >= minimumCapacity){
return b
}
}
returnnil
}

@inlinable
internalmutatingfunc isMutableAndUniquelyReferenced()->Bool{
returnisUniquelyReferenced()
}

 /// If this buffer is backed by a `_ContiguousArrayBuffer`
 /// containing the same number of elements as `self`, return it.
 /// Otherwise, return `nil`.
@inlinable
internalfunc requestNativeBuffer()->NativeBuffer?{
if !_isClassOrObjCExistential(Element.self){
return _native
}
return_fastPath(_storage.isNative)? _native :nil
}

 // We have two versions of type check: one that takes a range and the other
 // checks one element. The reason for this is that the ARC optimizer does not
 // handle loops atm. and so can get blocked by the presence of a loop (over
 // the range). This loop is not necessary for a single element access.
@inline(never)
@usableFromInline
internalfunc _typeCheckSlowPath(_ index:Int){
if_fastPath(_isNative){
letelement:AnyObject=cast(toBufferOf:AnyObject.self)._native[index]
precondition(
 element is Element,
"""
 Down-casted Array element failed to match the target type
 Expected \(Element.self) but found \(type(of: element))
"""
)
}
else{
letelement=_nonNative[index]
precondition(
 element is Element,
"""
 NSArray element failed to match the Swift Array Element type
 Expected \(Element.self) but found \(type(of: element))
"""
)
}
}

@inlinable
internalfunc _typeCheck(_ subRange:Range<Int>){
if !_isClassOrObjCExistential(Element.self){
return
}

if_slowPath(needsElementTypeCheck){
 // Could be sped up, e.g. by using
 // enumerateObjectsAtIndexes:options:usingBlock: in the
 // non-native case.
foriin subRange.lowerBound ..< subRange.upperBound {
_typeCheckSlowPath(i)
}
}
}

 /// Copy the elements in `bounds` from this buffer into uninitialized
 /// memory starting at `target`. Return a pointer "past the end" of the
 /// just-initialized memory.
@inlinable
@discardableResult
 __consuminginternalfunc _copyContents(
 subRange bounds:Range<Int>,
 initializing target:UnsafeMutablePointer<Element>
)->UnsafeMutablePointer<Element>{
_typeCheck(bounds)
if_fastPath(_isNative){
return _native._copyContents(subRange: bounds, initializing: target)
}
letbuffer=UnsafeMutableRawPointer(target)
.assumingMemoryBound(to:AnyObject.self)
letresult= _nonNative._copyContents(
 subRange: bounds,
 initializing: buffer)
returnUnsafeMutableRawPointer(result).assumingMemoryBound(to:Element.self)
}

public__consumingfunc _copyContents(
 initializing buffer:UnsafeMutableBufferPointer<Element>
)->(Iterator,UnsafeMutableBufferPointer<Element>.Index){
 // This customization point is not implemented for internal types.
 // Accidentally calling it would be a catastrophic performance bug.
fatalError("unsupported")
}

 /// Returns a `_SliceBuffer` containing the given sub-range of elements in
 /// `bounds` from this buffer.
@inlinable
internal subscript(bounds:Range<Int>)->_SliceBuffer<Element>{
get{
_typeCheck(bounds)
if_fastPath(_isNative){
return_native[bounds]
}
return_nonNative[bounds].unsafeCastElements(to:Element.self)
}
set{
fatalError("not implemented")
}
}

 /// A pointer to the first element.
 ///
 /// - Precondition: The elements are known to be stored contiguously.
@inlinable
internalvarfirstElementAddress:UnsafeMutablePointer<Element>{
_internalInvariant(_isNative,"must be a native buffer")
return _native.firstElementAddress
}

 /// A mutable pointer to the first element.
 ///
 /// - Precondition: the buffer must be mutable.
@_alwaysEmitIntoClient
internalvarmutableFirstElementAddress:UnsafeMutablePointer<Element>{
_internalInvariant(_isNative,"must be a native buffer")
return _native.mutableFirstElementAddress
}

@inlinable
internalvarfirstElementAddressIfContiguous:UnsafeMutablePointer<Element>?{
return_fastPath(_isNative)? firstElementAddress :nil
}

 /// The number of elements the buffer stores.
 ///
 /// This property is obsolete. It's only used for the ArrayBufferProtocol and
 /// to keep backward compatibility.
 /// Use `immutableCount` or `mutableCount` instead.
@inlinable
internalvarcount:Int{
@inline(__always)
get{
return_fastPath(_isNative)? _native.count : _nonNative.endIndex
}
set{
_internalInvariant(_isNative,"attempting to update count of Cocoa array")
 _native.count = newValue
}
}

 /// The number of elements of the buffer.
 ///
 /// - Precondition: The buffer must be immutable.
@_alwaysEmitIntoClient
internalvarimmutableCount:Int{
return_fastPath(_isNative)? _native.immutableCount : _nonNative.endIndex
}

 /// The number of elements of the buffer.
 ///
 /// - Precondition: The buffer must be mutable.
@_alwaysEmitIntoClient
internalvarmutableCount:Int{
@inline(__always)
get{
_internalInvariant(
 _isNative,
"attempting to get mutating-count of non-native buffer")
return _native.mutableCount
}
@inline(__always)
set{
_internalInvariant(_isNative,"attempting to update count of Cocoa array")
 _native.mutableCount = newValue
}
}

 /// Traps if an inout violation is detected or if the buffer is
 /// native and the subscript is out of range.
 ///
 /// wasNative == _isNative in the absence of inout violations.
 /// Because the optimizer can hoist the original check it might have
 /// been invalidated by illegal user code.
@inlinable
internalfunc _checkInoutAndNativeBounds(_ index:Int, wasNative:Bool){
_precondition(
 _isNative == wasNative,
"inout rules were violated: the array was overwritten")

if_fastPath(wasNative){
 _native._checkValidSubscript(index)
}
}

 /// Traps if an inout violation is detected or if the buffer is
 /// native and typechecked and the subscript is out of range.
 ///
 /// wasNativeTypeChecked == _isNativeTypeChecked in the absence of
 /// inout violations. Because the optimizer can hoist the original
 /// check it might have been invalidated by illegal user code.
@inlinable
internalfunc _checkInoutAndNativeTypeCheckedBounds(
 _ index:Int, wasNativeTypeChecked:Bool
){
_precondition(
 _isNativeTypeChecked == wasNativeTypeChecked,
"inout rules were violated: the array was overwritten")

if_fastPath(wasNativeTypeChecked){
 _native._checkValidSubscript(index)
}
}

 /// Traps unless the given `index` is valid for subscripting, i.e.
 /// `0 ≤ index < count`.
 ///
 /// - Precondition: The buffer must be mutable.
@_alwaysEmitIntoClient
internalfunc _checkValidSubscriptMutating(_ index:Int){
 _native._checkValidSubscriptMutating(index)
}

 /// The number of elements the buffer can store without reallocation.
 ///
 /// This property is obsolete. It's only used for the ArrayBufferProtocol and
 /// to keep backward compatibility.
 /// Use `immutableCapacity` or `mutableCapacity` instead.
@inlinable
internalvarcapacity:Int{
return_fastPath(_isNative)? _native.capacity : _nonNative.endIndex
}

 /// The number of elements the buffer can store without reallocation.
 ///
 /// - Precondition: The buffer must be immutable.
@_alwaysEmitIntoClient
internalvarimmutableCapacity:Int{
return_fastPath(_isNative)? _native.immutableCapacity : _nonNative.count
}

 /// The number of elements the buffer can store without reallocation.
 ///
 /// - Precondition: The buffer must be mutable.
@_alwaysEmitIntoClient
internalvarmutableCapacity:Int{
_internalInvariant(_isNative,"attempting to get mutating-capacity of non-native buffer")
return _native.mutableCapacity
}

@inlinable
@inline(__always)
internalfunc getElement(_ i:Int, wasNativeTypeChecked:Bool)->Element{
if_fastPath(wasNativeTypeChecked){
return_nativeTypeChecked[i]
}
returnunsafeBitCast(_getElementSlowPath(i), to:Element.self)
}

@inline(never)
@inlinable // @specializable
internalfunc _getElementSlowPath(_ i:Int)->AnyObject{
_internalInvariant(
_isClassOrObjCExistential(Element.self),
"Only single reference elements can be indexed here.")
letelement:AnyObject
if _isNative {
 // _checkInoutAndNativeTypeCheckedBounds does no subscript
 // checking for the native un-typechecked case. Therefore we
 // have to do it here.
 _native._checkValidSubscript(i)

 element =cast(toBufferOf:AnyObject.self)._native[i]
precondition(
 element is Element,
"""
 Down-casted Array element failed to match the target type
 Expected \(Element.self) but found \(type(of: element))
"""
)
}else{
 // ObjC arrays do their own subscript checking.
 element =_nonNative[i]
precondition(
 element is Element,
"""
 NSArray element failed to match the Swift Array Element type
 Expected \(Element.self) but found \(type(of: element))
"""
)
}
return element
}

 /// Get or set the value of the ith element.
@inlinable
internal subscript(i:Int)->Element{
get{
returngetElement(i, wasNativeTypeChecked: _isNativeTypeChecked)
}

nonmutating set{
if_fastPath(_isNative){
_native[i]= newValue
}
else{
varrefCopy=self
 refCopy.replaceSubrange(
 i..<(i +1),
 with:1,
 elementsOf:CollectionOfOne(newValue))
}
}
}

 /// Call `body(p)`, where `p` is an `UnsafeBufferPointer` over the
 /// underlying contiguous storage. If no such storage exists, it is
 /// created on-demand.
@inlinable
internalfunc withUnsafeBufferPointer<R>(
 _ body:(UnsafeBufferPointer<Element>)throws->R
)rethrows->R{
if_fastPath(_isNative){
defer{_fixLifetime(self)}
returntrybody(
UnsafeBufferPointer(start: firstElementAddress, count: count))
}
returntryContiguousArray(self).withUnsafeBufferPointer(body)
}

 /// Call `body(p)`, where `p` is an `UnsafeMutableBufferPointer`
 /// over the underlying contiguous storage.
 ///
 /// - Precondition: Such contiguous storage exists or the buffer is empty.
@inlinable
internalmutatingfunc withUnsafeMutableBufferPointer<R>(
 _ body:(UnsafeMutableBufferPointer<Element>)throws->R
)rethrows->R{
_internalInvariant(
 _isNative || count ==0,
"Array is bridging an opaque NSArray; can't get a pointer to the elements"
)
defer{_fixLifetime(self)}
returntrybody(UnsafeMutableBufferPointer(
 start: firstElementAddressIfContiguous, count: count))
}

 /// An object that keeps the elements stored in this buffer alive.
@inlinable
internalvarowner:AnyObject{
return_fastPath(_isNative)? _native._storage : _nonNative.buffer
}

 /// An object that keeps the elements stored in this buffer alive.
 ///
 /// - Precondition: This buffer is backed by a `_ContiguousArrayBuffer`.
@inlinable
internalvarnativeOwner:AnyObject{
_internalInvariant(_isNative,"Expect a native array")
return _native._storage
}

 /// A value that identifies the storage used by the buffer. Two
 /// buffers address the same elements when they have the same
 /// identity and count.
@inlinable
internalvaridentity:UnsafeRawPointer{
if _isNative {
return _native.identity
}
else{
returnUnsafeRawPointer(
Unmanaged.passUnretained(_nonNative.buffer).toOpaque())
}
}

 //===--- Collection conformance -------------------------------------===//
 /// The position of the first element in a non-empty collection.
 ///
 /// In an empty collection, `startIndex == endIndex`.
@inlinable
internalvarstartIndex:Int{
return0
}

 /// The collection's "past the end" position.
 ///
 /// `endIndex` is not a valid argument to `subscript`, and is always
 /// reachable from `startIndex` by zero or more applications of
 /// `index(after:)`.
@inlinable
internalvarendIndex:Int{
return count
}

@usableFromInline
internaltypealiasIndices=Range<Int>

 //===--- private --------------------------------------------------------===//
internaltypealiasStorage=_ContiguousArrayStorage<Element>
@usableFromInline
internaltypealiasNativeBuffer=_ContiguousArrayBuffer<Element>

@inlinable
internalvar_isNative:Bool{
if !_isClassOrObjCExistential(Element.self){
returntrue
}else{
return _storage.isNative
}
}

 /// `true`, if the array is native and does not need a deferred type check.
@inlinable
internalvar_isNativeTypeChecked:Bool{
if !_isClassOrObjCExistential(Element.self){
returntrue
}else{
return _storage.isUnflaggedNative
}
}

 /// Our native representation.
 ///
 /// - Precondition: `_isNative`.
@inlinable
internalvar_native:NativeBuffer{
returnNativeBuffer(
_isClassOrObjCExistential(Element.self)
? _storage.nativeInstance : _storage.unflaggedNativeInstance)
}

 /// Fast access to the native representation.
 ///
 /// - Precondition: `_isNativeTypeChecked`.
@inlinable
internalvar_nativeTypeChecked:NativeBuffer{
returnNativeBuffer(_storage.unflaggedNativeInstance)
}

@inlinable
internalvar_nonNative:_CocoaArrayWrapper{
get{
_internalInvariant(_isClassOrObjCExistential(Element.self))
return_CocoaArrayWrapper(_storage.objCInstance)
}
}
}
#endif