Swift进阶-Array源码分析
2022-03-25 本文已影响0人
顶级蜗牛
Swift进阶-类与结构体
Swift-函数派发
Swift进阶-属性
Swift进阶-指针
Swift进阶-内存管理
Swift进阶-TargetClassMetadata和TargetStructMetadata数据结构源码分析
Swift进阶-Mirror解析
Swift进阶-闭包
Swift进阶-协议
Swift进阶-泛型
Swift进阶-String源码解析
Swift进阶-Array源码解析
一、源码分析Array的内存结构
通过字面量初始化数组背后发生的事情，通过 SIL 来观察一下数组：
var number = [1, 2, 3, 4, 5, 6]
sil
当我们通过字面量的方式创建一个Array的时候就会调用_allocateUninitializedArray；
在swift源码中找到ArrayShared.swift的 _allocateUninitializedArray的声明:
/// 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) {
// builtinCount元素个数
let count = Int(builtinCount)
if count > 0 {
// 如果大于0就创建内存空间
// Doing the actual buffer allocation outside of the array.uninitialized
// semantics function enables stack propagation of the buffer.
// allocWithTailElems_1最终会调用allocObject来分配堆区内存空间，来去存储数组当中的元素
let bufferObject = Builtin.allocWithTailElems_1(
getContiguousArrayStorageType(for: Element.self),
builtinCount, Element.self)
// _adoptStorage其实就是创建array
let (array, ptr) = Array<Element>._adoptStorage(bufferObject, count: count)
return (array, ptr._rawValue)
}
// 如果小于等于0就创建空类型的数组(字面量创建数组会走这种方式)
// For an empty array no buffer allocation is needed.
let (array, ptr) = Array<Element>._allocateUninitialized(count)
return (array, ptr._rawValue)
}
1.如果参数builtinCount元素个数大于0，就创建内存空间；
Builtin.allocWithTailElems_1最终会调用alloc_Object来分配堆区内存空间，来去存储数组当中的元素；
Array<Element>._adoptStorage其实就是创建返回了array和第一个元素首地址。
2.如果参数builtinCount元素个数小于等于0，就创建空类型的数组。
找到Array.swift的_adoptStorage的声明：
/// Returns an Array of `count` uninitialized elements using the
/// given `storage`, and a pointer to uninitialized memory for the
/// first element.
///
/// - Precondition: `storage is _ContiguousArrayStorage`.
@inlinable
@_semantics("array.uninitialized")
internal static func _adoptStorage(
_ storage: __owned _ContiguousArrayStorage<Element>, count: Int
) -> (Array, UnsafeMutablePointer<Element>) {
let innerBuffer = _ContiguousArrayBuffer<Element>(
count: count,
storage: storage)
// 返回的是一个元组，第一个元素是Array，第二个元素是firstElement首地址
return (
Array(
_buffer: _Buffer(_buffer: innerBuffer, shiftedToStartIndex: 0)),
innerBuffer.firstElementAddress)
}
为什么还要返回第一个元素首地址呢？
是因为第一个元素前面还有是属于Array的内存空间，告诉外界我这是首地址方便使用数据。
Array声明的时候就知道_ContiguousArrayBuffer是成员变量：
Array声明
由于_ContiguousArrayBuffer代码比较多，我就不粘贴了。
在ContiguousArrayBuffer.swift找到_ContiguousArrayBuffer的初始化函数：
/// Initialize using the given uninitialized `storage`.
/// The storage is assumed to be uninitialized. The returned buffer has the
/// body part of the storage initialized, but not the elements.
///
/// - Warning: The result has uninitialized elements.
///
/// - Warning: storage may have been stack-allocated, so it's
/// crucial not to call, e.g., `malloc_size` on it.
@inlinable
internal init(count: Int, storage: _ContiguousArrayStorage<Element>) {
_storage = storage
_initStorageHeader(count: count, capacity: count)
}
发现_ContiguousArrayStorage的实例_storage是_ContiguousArrayBuffer的一个成员变量。
于是我又找到ContiguousArrayBuffer.swift里的_ContiguousArrayStorage声明:
// The class that implements the storage for a ContiguousArray<Element>
@_fixed_layout
@usableFromInline
internal final class _ContiguousArrayStorage<
Element
>: __ContiguousArrayStorageBase {
@inlinable
deinit {
_elementPointer.deinitialize(count: countAndCapacity.count)
_fixLifetime(self)
}
#if _runtime(_ObjC)
internal final override func withUnsafeBufferOfObjects<R>(
_ body: (UnsafeBufferPointer<AnyObject>) throws -> R
) rethrows -> R {
_internalInvariant(_isBridgedVerbatimToObjectiveC(Element.self))
let count = countAndCapacity.count
let elements = UnsafeRawPointer(_elementPointer)
.assumingMemoryBound(to: AnyObject.self)
defer { _fixLifetime(self) }
return try body(UnsafeBufferPointer(start: elements, count: count))
}
@objc(countByEnumeratingWithState:objects:count:)
@_effects(releasenone)
internal final override func countByEnumerating(
with state: UnsafeMutablePointer<_SwiftNSFastEnumerationState>,
objects: UnsafeMutablePointer<AnyObject>?, count: Int
) -> Int {
var enumerationState = state.pointee
if enumerationState.state != 0 {
return 0
}
return withUnsafeBufferOfObjects {
objects in
enumerationState.mutationsPtr = _fastEnumerationStorageMutationsPtr
enumerationState.itemsPtr =
AutoreleasingUnsafeMutablePointer(objects.baseAddress)
enumerationState.state = 1
state.pointee = enumerationState
return objects.count
}
}
@inline(__always)
@_effects(readonly)
@nonobjc private func _objectAt(_ index: Int) -> Unmanaged<AnyObject> {
return withUnsafeBufferOfObjects {
objects in
_precondition(
_isValidArraySubscript(index, count: objects.count),
"Array index out of range")
return Unmanaged.passUnretained(objects[index])
}
}
@objc(objectAtIndexedSubscript:)
@_effects(readonly)
final override internal func objectAtSubscript(_ index: Int) -> Unmanaged<AnyObject> {
return _objectAt(index)
}
@objc(objectAtIndex:)
@_effects(readonly)
final override internal func objectAt(_ index: Int) -> Unmanaged<AnyObject> {
return _objectAt(index)
}
@objc internal override final var count: Int {
@_effects(readonly) get {
return withUnsafeBufferOfObjects { $0.count }
}
}
@_effects(releasenone)
@objc internal override final func getObjects(
_ aBuffer: UnsafeMutablePointer<AnyObject>, range: _SwiftNSRange
) {
return withUnsafeBufferOfObjects {
objects in
_precondition(
_isValidArrayIndex(range.location, count: objects.count),
"Array index out of range")
_precondition(
_isValidArrayIndex(
range.location + range.length, count: objects.count),
"Array index out of range")
if objects.isEmpty { return }
// These objects are "returned" at +0, so treat them as pointer values to
// avoid retains. Copy bytes via a raw pointer to circumvent reference
// counting while correctly aliasing with all other pointer types.
UnsafeMutableRawPointer(aBuffer).copyMemory(
from: objects.baseAddress! + range.location,
byteCount: range.length * MemoryLayout<AnyObject>.stride)
}
}
/// If the `Element` is bridged verbatim, invoke `body` on an
/// `UnsafeBufferPointer` to the elements and return the result.
/// Otherwise, return `nil`.
internal final override func _withVerbatimBridgedUnsafeBuffer<R>(
_ body: (UnsafeBufferPointer<AnyObject>) throws -> R
) rethrows -> R? {
var result: R?
try self._withVerbatimBridgedUnsafeBufferImpl {
result = try body($0)
}
return result
}
/// If `Element` is bridged verbatim, invoke `body` on an
/// `UnsafeBufferPointer` to the elements.
internal final func _withVerbatimBridgedUnsafeBufferImpl(
_ body: (UnsafeBufferPointer<AnyObject>) throws -> Void
) rethrows {
if _isBridgedVerbatimToObjectiveC(Element.self) {
let count = countAndCapacity.count
let elements = UnsafeRawPointer(_elementPointer)
.assumingMemoryBound(to: AnyObject.self)
defer { _fixLifetime(self) }
try body(UnsafeBufferPointer(start: elements, count: count))
}
}
/// Bridge array elements and return a new buffer that owns them.
///
/// - Precondition: `Element` is bridged non-verbatim.
override internal func _getNonVerbatimBridgingBuffer() -> _BridgingBuffer {
_internalInvariant(
!_isBridgedVerbatimToObjectiveC(Element.self),
"Verbatim bridging should be handled separately")
let count = countAndCapacity.count
let result = _BridgingBuffer(count)
let resultPtr = result.baseAddress
let p = _elementPointer
for i in 0..<count {
(resultPtr + i).initialize(to: _bridgeAnythingToObjectiveC(p[i]))
}
_fixLifetime(self)
return result
}
#endif
/// Returns `true` if the `proposedElementType` is `Element` or a subclass of
/// `Element`. We can't store anything else without violating type
/// safety; for example, the destructor has static knowledge that
/// all of the elements can be destroyed as `Element`.
@inlinable
internal override func canStoreElements(
ofDynamicType proposedElementType: Any.Type
) -> Bool {
#if _runtime(_ObjC)
return proposedElementType is Element.Type
#else
// FIXME: Dynamic casts don't currently work without objc.
// rdar://problem/18801510
return false
#endif
}
/// A type that every element in the array is.
@inlinable
internal override var staticElementType: Any.Type {
return Element.self
}
@inlinable
internal final var _elementPointer: UnsafeMutablePointer<Element> {
return UnsafeMutablePointer(Builtin.projectTailElems(self, Element.self))
}
}
_ContiguousArrayStorage是继承自__ContiguousArrayStorageBase的，最终在SwiftNativeNSArray.swift找到了__ContiguousArrayStorageBase的声明：
/// Base class of the heap buffer backing arrays.
///
/// NOTE: older runtimes called this _ContiguousArrayStorageBase. The
/// two must coexist, so it was renamed. The old name must not be used
/// in the new runtime.
@usableFromInline
@_fixed_layout
internal class __ContiguousArrayStorageBase
: __SwiftNativeNSArrayWithContiguousStorage {
@usableFromInline
final var countAndCapacity: _ArrayBody
@inlinable
@nonobjc
internal init(_doNotCallMeBase: ()) {
_internalInvariantFailure("creating instance of __ContiguousArrayStorageBase")
}
#if _runtime(_ObjC)
internal override func withUnsafeBufferOfObjects<R>(
_ body: (UnsafeBufferPointer<AnyObject>) throws -> R
) rethrows -> R {
if let result = try _withVerbatimBridgedUnsafeBuffer(body) {
return result
}
_internalInvariantFailure(
"Can't use a buffer of non-verbatim-bridged elements as an NSArray")
}
/// If the stored type is bridged verbatim, invoke `body` on an
/// `UnsafeBufferPointer` to the elements and return the result.
/// Otherwise, return `nil`.
internal func _withVerbatimBridgedUnsafeBuffer<R>(
_ body: (UnsafeBufferPointer<AnyObject>) throws -> R
) rethrows -> R? {
_internalInvariantFailure(
"Concrete subclasses must implement _withVerbatimBridgedUnsafeBuffer")
}
internal func _getNonVerbatimBridgingBuffer() -> _BridgingBuffer {
_internalInvariantFailure(
"Concrete subclasses must implement _getNonVerbatimBridgingBuffer")
}
@objc(mutableCopyWithZone:)
dynamic internal func mutableCopy(with _: _SwiftNSZone?) -> AnyObject {
let arr = Array<AnyObject>(_ContiguousArrayBuffer(self))
return _SwiftNSMutableArray(arr)
}
@objc(indexOfObjectIdenticalTo:)
dynamic internal func index(ofObjectIdenticalTo object: AnyObject) -> Int {
let arr = Array<AnyObject>(_ContiguousArrayBuffer(self))
return arr.firstIndex { $0 === object } ?? NSNotFound
}
#endif
@inlinable
internal func canStoreElements(ofDynamicType _: Any.Type) -> Bool {
_internalInvariantFailure(
"Concrete subclasses must implement canStoreElements(ofDynamicType:)")
}
/// A type that every element in the array is.
@inlinable
internal var staticElementType: Any.Type {
_internalInvariantFailure(
"Concrete subclasses must implement staticElementType")
}
@inlinable
deinit {
_internalInvariant(
self !== _emptyArrayStorage, "Deallocating empty array storage?!")
}
}
整理得出：
struct Array 拥有 struct _ContiguousArrayBuffer这个类型的成员；
struct _ContiguousArrayBuffer拥有 class _ContiguousArrayStorage这个类型的成员；
class _ContiguousArrayStorage继承自class __ContiguousArrayStorageBase这个类。
所以对于Array内存结构可以分析如同下图：
Array内存结构
二、LLDB调试Array内存结构
Array表现起来像是值类型，因为Array它是struct，而在lldb调试的时候编译器帮我们处理，直接从第一个元素地址逐个做偏移取地址上的值。
number这个地址上对堆区地址的引用，通过x/8g格式化输出：
本质上Array是一个引用类型，只是在struct上嵌套了一个class；
又因为Array是struct所以在赋值的时候就会有一个写时复制的特性。
三、Array扩容
var number = [1, 2, 3, 4, 5, 6]
number.append(100)
找到源码里Array.swift的append函数声明:
/// Adds a new element at the end of the array.
///
/// Use this method to append a single element to the end of a mutable array.
///
/// var numbers = [1, 2, 3, 4, 5]
/// numbers.append(100)
/// print(numbers)
/// // Prints "[1, 2, 3, 4, 5, 100]"
///
/// Because arrays increase their allocated capacity using an exponential
/// strategy, appending a single element to an array is an O(1) operation
/// when averaged over many calls to the `append(_:)` method. When an array
/// has additional capacity and is not sharing its storage with another
/// instance, appending an element is O(1). When an array needs to
/// reallocate storage before appending or its storage is shared with
/// another copy, appending is O(*n*), where *n* is the length of the array.
///
/// - Parameter newElement: The element to append to the array.
///
/// - Complexity: O(1) on average, over many calls to `append(_:)` on the
/// same array.
@inlinable
@_semantics("array.append_element")
public mutating func append(_ newElement: __owned Element) {
// Separating uniqueness check and capacity check allows hoisting the
// uniqueness check out of a loop.
_makeUniqueAndReserveCapacityIfNotUnique()
let oldCount = _buffer.mutableCount
_reserveCapacityAssumingUniqueBuffer(oldCount: oldCount)
_appendElementAssumeUniqueAndCapacity(oldCount, newElement: newElement)
_endMutation()
}
_makeUniqueAndReserveCapacityIfNotUnique相当于是创建新的buffer内存空间
_buffer.beginCOWMutation的判断逻辑
/// Returns `true` and puts the buffer in a mutable state if the buffer's
/// storage is uniquely-referenced; otherwise performs no action and
/// returns `false`.
///
/// - Precondition: The buffer must be immutable.
///
/// - Warning: It's a requirement to call `beginCOWMutation` before the buffer
/// is mutated.
@_alwaysEmitIntoClient
internal mutating func beginCOWMutation() -> Bool {
let isUnique: Bool
if !_isClassOrObjCExistential(Element.self) {
isUnique = _storage.beginCOWMutationUnflaggedNative()
} else if !_storage.beginCOWMutationNative() {
return false
} else {
isUnique = _isNative
}
#if INTERNAL_CHECKS_ENABLED && COW_CHECKS_ENABLED
if isUnique {
_native.isImmutable = false
}
#endif
return isUnique
}
其实数组扩容是以2倍的方式
来看看是怎么扩容的：
/// Creates a new buffer, replacing the current buffer.
///
/// If `bufferIsUnique` is true, the buffer is assumed to be uniquely
/// referenced by this array 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`.
@_alwaysEmitIntoClient
internal mutating func _createNewBuffer(
bufferIsUnique: Bool, minimumCapacity: Int, growForAppend: Bool
) {
_internalInvariant(!bufferIsUnique || _buffer.isUniquelyReferenced())
_buffer = _buffer._consumeAndCreateNew(bufferIsUnique: bufferIsUnique,
minimumCapacity: minimumCapacity,
growForAppend: growForAppend)
}
_buffer._consumeAndCreateNew 找到ArrayBuffer.swift的_consumeAndCreateNew函数：
/// 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 __consuming func _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 __consuming func _consumeAndCreateNew(
bufferIsUnique: Bool, minimumCapacity: Int, growForAppend: Bool
) -> _ArrayBuffer {
let newCapacity = _growArrayCapacity(oldCapacity: capacity,
minimumCapacity: minimumCapacity,
growForAppend: growForAppend)
let c = count
_internalInvariant(newCapacity >= c)
let newBuffer = _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.
let dest = 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)
}
_growArrayCapacity函数就是扩容相关代码。
找到ArrayShared.swift的_growArrayCapacity函数：
@inlinable
internal func _growArrayCapacity(_ capacity: Int) -> Int {
return capacity * 2
}
扩容的判断条件
@_alwaysEmitIntoClient
internal func _growArrayCapacity(
oldCapacity: Int, minimumCapacity: Int, growForAppend: Bool
) -> Int {
if growForAppend {
if oldCapacity < minimumCapacity {
// When appending to an array, grow exponentially.
return Swift.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
}
如果是count > capacity 则需要扩容，每次扩容都是以当前的 capacity * 2的方式。
_reserveCapacityAssumingUniqueBuffer 如果数组是空的，_makeMutableAndUnique不会将空的数组缓冲区替换为唯一的缓冲区(它只是将其替换为空的数组singleton)。这个特定的情况是可以的，因为我们将使缓冲区在这个函数中是唯一的，因为我们请求的容量是> 0，因此_copyToNewBuffer将被调用来创建一个新的缓冲区。
@inlinable
@_semantics("array.mutate_unknown")
internal mutating func _reserveCapacityAssumingUniqueBuffer(oldCount: Int) {
// Due to make_mutable hoisting the situation can arise where we hoist
// _makeMutableAndUnique out of loop and use it to replace
// _makeUniqueAndReserveCapacityIfNotUnique that precedes this call. If the
// array was empty _makeMutableAndUnique does not replace the empty array
// buffer by a unique buffer (it just replaces it by the empty array
// singleton).
// This specific case is okay because we will make the buffer unique in this
// function because we request a capacity > 0 and therefore _copyToNewBuffer
// will be called creating a new buffer.
let capacity = _buffer.mutableCapacity
_internalInvariant(capacity == 0 || _buffer.isMutableAndUniquelyReferenced())
if _slowPath(oldCount &+ 1 > capacity) {
_createNewBuffer(bufferIsUnique: capacity > 0,
minimumCapacity: oldCount &+ 1,
growForAppend: true)
}
}
_appendElementAssumeUniqueAndCapacity 附加元素假定唯一和容量
@inlinable
@_semantics("array.mutate_unknown")
internal mutating func _appendElementAssumeUniqueAndCapacity(
_ oldCount: Int,
newElement: __owned Element
) {
_internalInvariant(_buffer.isMutableAndUniquelyReferenced())
_internalInvariant(_buffer.mutableCapacity >= _buffer.mutableCount &+ 1)
_buffer.mutableCount = oldCount &+ 1
(_buffer.mutableFirstElementAddress + oldCount).initialize(to: newElement)
}
