//===----------------------------------------------------------------------===// // // This source file is part of the Swift Collections open source project // // Copyright (c) 2025 - 2026 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 // // SPDX-License-Identifier: Apache-2.0 WITH Swift-exception // //===----------------------------------------------------------------------===// #if !COLLECTIONS_SINGLE_MODULE import InternalCollectionsUtilities #endif /// A value that manages a contiguous block of memory starting with a header /// value and then followed by a contiguous array of elements. Values of this /// type own the underlying memory, and are non-copyable to ensure that /// ownership of that memory is unique. /// /// The number of elements stored after the header must be computable based on /// the information in the header (via the `trailingCount` property), so that /// it is not stored separately. @frozen @safe public struct TrailingArray: ~Copyable where Header: ~Copyable { /// A pointer to the raw, underlying storage. This may point before the /// Header instance in cases where the alignment of Element exceeds that /// of the Header and we have overallocated to compensate. @usableFromInline @unsafe var _storage: UnsafeMutableRawPointer /// Pointer to the header. @_alwaysEmitIntoClient @unsafe var _pointer: UnsafeMutablePointer
{ unsafe Self.headerPointer(fromStorage: _storage) } /// The element type stored within the buffer. public typealias Element = Header.Element /// Allocate storage and initialize only the header, leaving the trailing /// elements uninitialized. This is private because it can compromise /// memory safety. @_alwaysEmitIntoClient private init(_headerOnly header: consuming Header) { let (bytes, alignment) = Self.allocationSize(header: header) unsafe _storage = UnsafeMutableRawPointer.allocate( byteCount: bytes, alignment: alignment) unsafe _pointer.initialize(to: header) } /// Initialize the trailing elements that follow the header at `pointer`. /// /// If `initializer` throws, the output span deinitializes the elements it /// has initialized so far, so the caller only needs to clean up the header. @available(SwiftStdlib 5.1, *) @_alwaysEmitIntoClient @unsafe static func _initializeTrailingElements( after pointer: UnsafeMutablePointer
, initializer: (inout OutputSpan) throws(E) -> Void ) throws(E) { let elements = unsafe _elements(after: pointer) var output = unsafe OutputSpan(buffer: elements, initializedCount: 0) try initializer(&output) let initialized = unsafe output.finalize(for: elements) precondition( elements.count == initialized, "TrailingArray initialization underflow") } /// Allocate an intrusive managed buffer with the given header and calling /// the initializer to fill in the trailing elements. @available(SwiftStdlib 5.1, *) @_alwaysEmitIntoClient public init( header: consuming Header, initializingTrailingElementsWith initializer: (inout OutputSpan) throws(E) -> Void ) throws(E) { let (bytes, alignment) = Self.allocationSize(header: header) let storage = unsafe UnsafeMutableRawPointer.allocate( byteCount: bytes, alignment: alignment) let pointer = unsafe Self.headerPointer(fromStorage: storage) unsafe pointer.initialize(to: header) do throws(E) { try unsafe Self._initializeTrailingElements( after: pointer, initializer: initializer) } catch { // The trailing elements aren't initialized, so don't let `deinit` run. unsafe pointer.deinitialize(count: 1) unsafe storage.deallocate() throw error } unsafe self._storage = storage } /// Allocate an intrusive managed buffer with the given header and /// initializing each trailing element with the given `element`. @_alwaysEmitIntoClient public init(header: consuming Header, repeating element: Element) { self.init(_headerOnly: header) unsafe rawElements.initialize(repeating: element) } /// Deinitialize each of the trailing elements, then the header, then /// deallocate the underlying storage. @_alwaysEmitIntoClient deinit { unsafe rawElements.deinitialize() unsafe _pointer.deinitialize(count: 1) unsafe _storage.deallocate() } /// Take ownership over a pointer to memory containing the header followed /// by the trailing elements. /// /// Once this managed buffer instance is no longer used, this memory will /// be freed. /// - Parameters: /// - pointer: A pointer to the header, which should already have been /// initialized by the caller. /// - storage: A pointer to the storage containing the header and /// pointers. This will usually be `UnsafeMutableRawPointer(pointer)`, /// but may precede `pointer` if the elements have greater alignment /// than the header. @_alwaysEmitIntoClient public init( consuming pointer: UnsafeMutablePointer
, storage: UnsafeMutableRawPointer ) { unsafe self._storage = storage precondition( unsafe self._pointer == pointer, "header pointer does not account for the alignment of the elements" ) } /// Return the pointer to the underlying memory, including ownership over /// that memory. The underlying storage will not be freed by this buffer; /// it is the responsibility of the caller. The header pointer and /// underlying storage are returned separately, to handle cases where /// the alignment of the elements is greater than that of the header. @_alwaysEmitIntoClient public consuming func leakStorage() -> ( pointer: UnsafeMutablePointer
, storage: UnsafeMutableRawPointer ) { let pointer = unsafe self._pointer let storage = unsafe _storage discard self return unsafe (pointer, storage) } /// Access the header portion of the buffer. @_alwaysEmitIntoClient public var header: Header { unsafeAddress { unsafe UnsafePointer(_pointer) } unsafeMutableAddress { unsafe _pointer } } /// The number of trailing elements in the value. @_alwaysEmitIntoClient public var count: Int { header.trailingCount } /// Starting index for accessing the trailing elements. Always 0 @_alwaysEmitIntoClient public var startIndex: Int { 0 } /// Ending index for accessing the trailing elements. Always `count`. @_alwaysEmitIntoClient public var endIndex: Int { count } /// Indices covering all of the trailing elements. Always `0.. { 0 ..< count } /// Access the trailing element at the given index. @_alwaysEmitIntoClient public subscript(index: Int) -> Element { get { precondition(index >= 0 && index < count) return unsafe rawElements[index] } set { precondition(index >= 0 && index < count) unsafe rawElements[index] = newValue } } /// Access the flexible array elements. @_alwaysEmitIntoClient @unsafe var rawElements: UnsafeMutableBufferPointer { unsafe Self._elements(after: _pointer) } @_alwaysEmitIntoClient @unsafe static func _elements( after pointer: UnsafeMutablePointer
) -> UnsafeMutableBufferPointer { unsafe UnsafeMutableBufferPointer( start: UnsafeMutableRawPointer(pointer.advanced(by: 1)) .assumingMemoryBound(to: Element.self), count: pointer.pointee.trailingCount ) } /// Accesses the trailing elements following the header. @available(SwiftStdlib 5.1, *) @_alwaysEmitIntoClient public var elements: Span { @_lifetime(self) get { unsafe _overrideLifetime(rawElements.span, borrowing: self) } } /// Accesses the trailing elements following the header, allowing mutation /// of those elements. @available(SwiftStdlib 5.1, *) @_alwaysEmitIntoClient public var mutableElements: MutableSpan { @_lifetime(self) mutating get { let elements = unsafe self.rawElements.mutableSpan return unsafe _overrideLifetime(elements, mutating: &self) } } /// Execute the given closure, providing it with an unsafe buffer pointer /// referencing the header. @_alwaysEmitIntoClient public mutating func withUnsafeMutablePointerToHeader( _ body: (UnsafeMutablePointer
) throws(E) -> R ) throws(E) -> R { return unsafe try body(_pointer) } /// Execute the given closure, providing it with an unsafe buffer pointer /// referencing the trailing elements. @_alwaysEmitIntoClient public mutating func withUnsafeMutablePointerToElements( _ body: (UnsafeMutableBufferPointer) throws(E) -> R ) throws(E) -> R { return unsafe try body(rawElements) } /// Execute the given closure, providing it with unsafe pointers to the /// header and trailing elements, respectively. @_alwaysEmitIntoClient public mutating func withUnsafeMutablePointers( _ body: (UnsafeMutablePointer
, UnsafeMutableBufferPointer) throws(E) -> R ) throws(E) -> R { return unsafe try body(_pointer, rawElements) } /// Determine the allocation size and alignment needed for the given header /// value along with its trailing elements. /// /// In cases where the element's alignment exceeds that of the header, /// this operation will suggest overallocation so that the elements can be /// properly aligned following the header. @_alwaysEmitIntoClient static func allocationSize(header: borrowing Header) -> (size: Int, alignment: Int) { // The number of bytes needed to contain the header and elements, // assuming that there are no alignment issues. let numBytes = MemoryLayout
.stride + MemoryLayout.stride * header.trailingCount let headerAlignment = MemoryLayout
.alignment let elementAlignment = MemoryLayout.alignment // If the header provides sufficient alignment for the elements, // we're done. if elementAlignment <= headerAlignment { return (numBytes, MemoryLayout
.alignment) } // We may have to slide an allocation by up to the difference between // the element and header alignments to ensure that the elements are // appropriately aligned. return ( numBytes + elementAlignment - headerAlignment, MemoryLayout.alignment) } /// Given storage that is large enough to accommodate padding + the header /// + the elements, return the header pointer from the storage pointer. @_alwaysEmitIntoClient static func headerPointer(fromStorage storage: UnsafeMutableRawPointer) -> UnsafeMutablePointer
{ let headerAlignment = MemoryLayout
.alignment let elementAlignment = MemoryLayout.alignment // Normal case: the header has sufficient alignment to include the // elements, so the storage refers directly to the header. if elementAlignment <= headerAlignment { return unsafe storage.assumingMemoryBound(to: Header.self) } // The header is stored right before the elements, with padding bytes // between the start of the allocation and up to the header. return unsafe storage.advanced(by: MemoryLayout
.stride) .alignedUp(for: Element.self) .advanced(by: -MemoryLayout
.stride) .assumingMemoryBound(to: Header.self) } } extension TrailingArray where Header: ~Copyable, Header.Element: BitwiseCopyable { /// Allocate an intrusive managed buffer with the given header, but leaving the /// trailing elements uninitialized. @_alwaysEmitIntoClient @unsafe public init(header: consuming Header, uninitializedTrailingElements: ()) { self.init(_headerOnly: header) } } extension TrailingArray where Header: Copyable { /// Create a temporary intrusive managed buffer for the given header, whose /// trailing elements are initialized to copies of `element`. That instance /// is provided to the given `body` to operate on for the duration of the /// call. The temporary is allocated on the stack, unless it is very /// large according to `withUnsafeTemporaryAllocation`. @_alwaysEmitIntoClient public static func withTemporaryValue( header: consuming Header, repeating element: Element, body: (inout TrailingArray
) throws(E) -> R ) throws(E) -> R { return unsafe try _withTemporaryValue( header: header, uninitializedTrailingElements: () ) { (value) throws(E) in unsafe value.rawElements.initialize(repeating: element) return try body(&value) } } /// Create a temporary intrusive managed buffer for the given header, whose /// trailing elements are initialized with the given `initializer` function. /// That instance is provided to the given `body` to operate on for the /// duration of the call. The temporary is allocated on the stack, unless /// it is very large according to `withUnsafeTemporaryAllocation`. @available(SwiftStdlib 5.1, *) @_alwaysEmitIntoClient public static func withTemporaryValue( header: consuming Header, initializingTrailingElementsWith initializer: (inout OutputSpan) throws(E) -> Void, body: (inout TrailingArray
) throws(E) -> R ) throws(E) -> R { return unsafe try _withTemporaryValue( header: header, uninitializedTrailingElements: (), initializingTrailingElements: { (pointer) throws(E) in try unsafe _initializeTrailingElements( after: pointer, initializer: initializer) }, body: body) } } extension TrailingArray { /// Create a temporary intrusive managed buffer for the given header, whose /// trailing elements are left uninitialized. That instance is provided to /// the given `body` to operate on for the duration of the /// call. The temporary is allocated on the stack, unless it is very /// large according to `withUnsafeTemporaryAllocation`. @_alwaysEmitIntoClient @unsafe static func _withTemporaryValue( header: Header, uninitializedTrailingElements: (), initializingTrailingElements: ( UnsafeMutablePointer
) throws(E) -> Void = { _ in }, body: (inout TrailingArray
) throws(E) -> R ) throws(E) -> R { let (numBytes, alignment) = allocationSize(header: header) // Allocate temporary storage large enough for the value we need. return try _withUnsafeTemporaryAllocation( byteCount: numBytes, alignment: alignment ) { buffer throws(E) in // Initialize the header within the temporary allocation. let storagePointer = buffer.baseAddress! let headerPointer = unsafe TrailingArray.headerPointer(fromStorage: storagePointer) unsafe headerPointer.initialize(to: header) // Initialize the trailing elements, if requested, before creating the // trailing array, so a throwing initializer doesn't leave behind // a value whose elements aren't initialized. do throws(E) { try initializingTrailingElements(headerPointer) } catch { unsafe headerPointer.deinitialize(count: 1) throw error } /// Create a trailing array over that temporary storage. var managedBuffer: Optional = unsafe TrailingArray( consuming: headerPointer, storage: storagePointer) defer { let buffer = managedBuffer.take()! // Deinitialize the elements and header. unsafe buffer.rawElements.deinitialize() unsafe buffer._pointer.deinitialize(count: 1) // Tell the trailing buffer not to free the storage. let (finalPointer, finalStorage) = unsafe buffer.leakStorage() precondition(unsafe finalPointer == headerPointer) precondition(unsafe finalStorage == storagePointer) } return try body(&managedBuffer!) } } } extension TrailingArray where Header.Element: BitwiseCopyable { /// Create a temporary intrusive managed buffer for the given header, whose /// trailing elements are left uninitialized. That instance is provided to /// the given `body` to operate on for the duration of the /// call. The temporary is allocated on the stack, unless it is very /// large according to `withUnsafeTemporaryAllocation`. @_alwaysEmitIntoClient @unsafe public static func withTemporaryValue( header: consuming Header, uninitializedTrailingElements: (), body: (inout TrailingArray
) throws(E) -> R ) throws(E) -> R { return unsafe try _withTemporaryValue( header: header, uninitializedTrailingElements: () ) { (value) throws(E) in try body(&value) } } }