ArrayShared.swift

//===--- 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.
///
/// In order for the optimizer see that a call to `_checkSubscript` is semantically
/// associated with an array access, a value of this type is returned and later passed
/// to the accessing function. For example, a typical call to `_getElement` looks like
/// let token = _checkSubscript(index, ...)
/// return _getElement(index, ... , matchingSubscriptCheck: token)
@frozen
publicstruct_DependenceToken{
@inlinable
publicinit(){
}
}

/// 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`.
@inlinable // FIXME(inline-always)
@inline(__always)
@_semantics("array.uninitialized_intrinsic")
public // COMPILER_INTRINSIC
func _allocateUninitializedArray<Element>(_ builtinCount:Builtin.Word)
->(Array<Element>,Builtin.RawPointer){
letcount=Int(builtinCount)
if count >0{
 // Doing the actual buffer allocation outside of the array.uninitialized
 // semantics function enables stack propagation of the buffer.
letbufferObject=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>
){
vararray= array
 array._deallocateUninitialized()
}

#if !INTERNAL_CHECKS_ENABLED
@_alwaysEmitIntoClient
@_semantics("array.finalize_intrinsic")
@_effects(readnone)
public // COMPILER_INTRINSIC
func _finalizeUninitializedArray<Element>(
 _ array:__owned Array<Element>
)->Array<Element>{
varmutableArray= array
 mutableArray._endMutation()
return mutableArray
}
#else
// When asserts are enabled, _endCOWMutation writes to _native.isImmutable
// So we cannot have @_effects(readnone)
@_alwaysEmitIntoClient
@_semantics("array.finalize_intrinsic")
public // COMPILER_INTRINSIC
func _finalizeUninitializedArray<Element>(
 _ array:__owned Array<Element>
)->Array<Element>{
varmutableArray= array
 mutableArray._endMutation()
return mutableArray
}
#endif

extensionCollection{
 // Utility method for collections that wish to implement
 // CustomStringConvertible and CustomDebugStringConvertible using a bracketed
 // list of elements, like an array.
internalfunc _makeCollectionDescription(
 withTypeName type:String?=nil
)->String{
varresult=""
iflet type = type {
 result +="\(type)(["
}else{
 result +="["
}

varfirst=true
foriteminself{
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)
internalmutatingfunc _arrayOutOfPlaceReplace<C:Collection>(
 _ bounds:Range<Int>,
 with newValues:__owned C,
 count insertCount:Int
)where C.Element ==Element{

letgrowth= insertCount - bounds.count
letnewCount=self.count + growth
varnewBuffer=_forceCreateUniqueMutableBuffer(
 newCount: newCount, requiredCapacity: newCount)

_arrayOutOfPlaceUpdate(
&newBuffer, bounds.lowerBound - startIndex, insertCount,
{ rawMemory, count in
varp= rawMemory
varq= newValues.startIndex
for_in0..<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
internalfunc _expectEnd<C:Collection>(of s:C, is i:C.Index){
_debugPrecondition(
 i == s.endIndex,
"invalid Collection: count differed in successive traversals")
}

@inlinable
internalfunc _growArrayCapacity(_ capacity:Int)->Int{
return capacity *2
}

@_alwaysEmitIntoClient
internalfunc _growArrayCapacity(
 oldCapacity:Int, minimumCapacity:Int, growForAppend:Bool
)->Int{
if growForAppend {
if oldCapacity < minimumCapacity {
 // When appending to an array, grow exponentially.
returnSwift.max(minimumCapacity,_growArrayCapacity(oldCapacity))
}
return oldCapacity
}
 // If not for append, just use the specified capacity, ignoring oldCapacity.
 // This means that we "shrink" the buffer in case minimumCapacity is less
 // than oldCapacity.
return minimumCapacity
}

//===--- 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
internalfunc _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
internalfunc _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
internalfunc _forceCreateUniqueMutableBufferImpl(
 countForBuffer:Int, minNewCapacity:Int,
 requiredCapacity:Int
)->_ContiguousArrayBuffer<Element>{
_internalInvariant(countForBuffer >=0)
_internalInvariant(requiredCapacity >= countForBuffer)
_internalInvariant(minNewCapacity >= countForBuffer)

letminimumCapacity=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
internalmutatingfunc _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
_internalInvariant(count ==0)
}
){

_internalInvariant(headCount >=0)
_internalInvariant(newCount >=0)

 // Count of trailing source elements to copy/move
letsourceCount=self.count
lettailCount= dest.count - headCount - newCount
_internalInvariant(headCount + tailCount <= sourceCount)

letoldCount= sourceCount - headCount - tailCount
letdestStart= dest.firstElementAddress
letnewStart= destStart + headCount
letnewEnd= newStart + newCount

 // Check to see if we have storage we can move from
iflet backing =requestUniqueMutableBackingBuffer(
 minimumCapacity: sourceCount){

letsourceStart= firstElementAddress
letoldStart= sourceStart + headCount

 // Destroy any items that may be lurking in a _SliceBuffer before
 // its real first element
letbackingStart= backing.firstElementAddress
letsourceOffset= 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
letbackingEnd= backingStart + backing.count
letsourceEnd= sourceStart + sourceCount
 sourceEnd.deinitialize(count: backingEnd - sourceEnd)
 backing.count =0
}
else{
letheadStart= startIndex
letheadEnd= headStart + headCount
letnewStart=_copyContents(
 subRange: headStart..<headEnd,
 initializing: destStart)
initializeNewElements(newStart, newCount)
lettailStart= headEnd + oldCount
lettailEnd= endIndex
_copyContents(subRange: tailStart..<tailEnd, initializing: newEnd)
}
self=Self(_buffer: dest, shiftedToStartIndex: startIndex)
}
}

extension_ArrayBufferProtocol{
@inline(never)
@usableFromInline
internalmutatingfunc _outlinedMakeUniqueBuffer(bufferCount:Int){

if_fastPath(
requestUniqueMutableBackingBuffer(minimumCapacity: bufferCount)!=nil){
return
}

varnewBuffer=_forceCreateUniqueMutableBuffer(
 newCount: bufferCount, requiredCapacity: bufferCount)
_arrayOutOfPlaceUpdate(&newBuffer, bufferCount,0)
}

 /// Append items from `newItems` to a buffer.
@inlinable
internalmutatingfunc _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
_internalInvariant(count == capacity)
varnewCount=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
varstream= newItems.makeIterator()
varnextItem= stream.next()
while nextItem !=nil{

 // grow capacity, first time around and when filled
varnewBuffer=_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)

letcurrentCapacity=self.capacity
letbase=self.firstElementAddress

 // fill while there is another item and spare capacity
whilelet next = nextItem, newCount < currentCapacity {
(base + newCount).initialize(to: next)
 newCount +=1
 nextItem = stream.next()
}
self.count = newCount
}
}
}