/src/swift-nio/Sources/_NIODataStructures/_TinyArray.swift

Source
//===----------------------------------------------------------------------===//
//
// This source file is part of the SwiftNIO open source project
//
// Copyright (c) 2023 Apple Inc. and the SwiftNIO project authors
// Licensed under Apache License v2.0
//
// See LICENSE.txt for license information
// See CONTRIBUTORS.txt for the list of SwiftNIO project authors
//
// SPDX-License-Identifier: Apache-2.0
//
//===----------------------------------------------------------------------===//
//===----------------------------------------------------------------------===//
//
// This source file is part of the SwiftCertificates open source project
//
// Copyright (c) 2023 Apple Inc. and the SwiftCertificates project authors
// Licensed under Apache License v2.0
//
// See LICENSE.txt for license information
// See CONTRIBUTORS.txt for the list of SwiftCertificates project authors
//
// SPDX-License-Identifier: Apache-2.0
//
//===----------------------------------------------------------------------===//

/// ``TinyArray`` is a ``RandomAccessCollection`` optimised to store zero or one ``Element``.
/// It supports arbitrary many elements but if only up to one ``Element`` is stored it does **not** allocate separate storage on the heap
/// and instead stores the ``Element`` inline.
public struct _TinyArray<Element> {
    @usableFromInline
    enum Storage {
        case one(Element)
        case arbitrary([Element])
    }

    @usableFromInline
    var storage: Storage
}

// MARK: - TinyArray "public" interface

extension _TinyArray: Equatable where Element: Equatable {}
extension _TinyArray: Hashable where Element: Hashable {}
extension _TinyArray: Sendable where Element: Sendable {}

extension _TinyArray: RandomAccessCollection {
    public typealias Element = Element

    public typealias Index = Int

    @inlinable
    public func makeIterator() -> Iterator {
        Iterator(storage: self.storage)
    }

    public struct Iterator: IteratorProtocol {
        @usableFromInline
        let _storage: Storage
        @usableFromInline
        var _index: Index

        @usableFromInline
        init(storage: Storage) {
            self._storage = storage
            self._index = storage.startIndex
        }

        @inlinable
        public mutating func next() -> Element? {
            if self._index == self._storage.endIndex {
                return nil
            }

            defer {
                self._index &+= 1
            }

            return self._storage[self._index]
        }
    }

    @inlinable
    public subscript(position: Int) -> Element {
        get {
            self.storage[position]
        }
    }

    @inlinable
    public var startIndex: Int {
        self.storage.startIndex
    }

    @inlinable
    public var endIndex: Int {
        self.storage.endIndex
    }
}

extension _TinyArray.Iterator: Sendable where Element: Sendable {}

extension _TinyArray {
    @inlinable
    public init(_ elements: some Sequence<Element>) {
        self.storage = .init(elements)
    }

    @inlinable
    public init(_ elements: some Sequence<Result<Element, some Error>>) throws {
        self.storage = try .init(elements)
    }

    @inlinable
    public init() {
        self.storage = .init()
    }

    @inlinable
    public mutating func append(_ newElement: Element) {
        self.storage.append(newElement)
    }

    @inlinable
    public mutating func append(contentsOf newElements: some Sequence<Element>) {
        self.storage.append(contentsOf: newElements)
    }

    @discardableResult
    @inlinable
    public mutating func remove(at index: Int) -> Element {
        self.storage.remove(at: index)
    }

    @inlinable
    public mutating func removeAll(where shouldBeRemoved: (Element) throws -> Bool) rethrows {
        try self.storage.removeAll(where: shouldBeRemoved)
    }

    @inlinable
    public mutating func sort(by areInIncreasingOrder: (Element, Element) throws -> Bool) rethrows {
        try self.storage.sort(by: areInIncreasingOrder)
    }
}

// MARK: - TinyArray.Storage "private" implementation

extension _TinyArray.Storage: Equatable where Element: Equatable {
    @inlinable
    static func == (lhs: Self, rhs: Self) -> Bool {
        switch (lhs, rhs) {
        case (.one(let lhs), .one(let rhs)):
            return lhs == rhs
        case (.arbitrary(let lhs), .arbitrary(let rhs)):
            // we don't use lhs.elementsEqual(rhs) so we can hit the fast path from Array
            // if both arrays share the same underlying storage: https://github.com/apple/swift/blob/b42019005988b2d13398025883e285a81d323efa/stdlib/public/core/Array.swift#L1775
            return lhs == rhs

        case (.one(let element), .arbitrary(let array)),
            (.arbitrary(let array), .one(let element)):
            guard array.count == 1 else {
                return false
            }
            return element == array[0]

        }
    }
}
extension _TinyArray.Storage: Hashable where Element: Hashable {
    @inlinable
    func hash(into hasher: inout Hasher) {
        // same strategy as Array: https://github.com/apple/swift/blob/b42019005988b2d13398025883e285a81d323efa/stdlib/public/core/Array.swift#L1801
        hasher.combine(count)
        for element in self {
            hasher.combine(element)
        }
    }
}
extension _TinyArray.Storage: Sendable where Element: Sendable {}

extension _TinyArray.Storage: RandomAccessCollection {
    @inlinable
    subscript(position: Int) -> Element {
        get {
            switch self {
            case .one(let element):
                guard position == 0 else {
                    fatalError("index \(position) out of bounds")
                }
                return element
            case .arbitrary(let elements):
                return elements[position]
            }
        }
    }

    @inlinable
    var startIndex: Int {
        0
    }

    @inlinable
    var endIndex: Int {
        switch self {
        case .one: return 1
        case .arbitrary(let elements): return elements.endIndex
        }
    }
}

extension _TinyArray.Storage {
    @inlinable
    init(_ elements: some Sequence<Element>) {
        self = .arbitrary([])
        self.append(contentsOf: elements)
    }

    @inlinable
    init(_ newElements: some Sequence<Result<Element, some Error>>) throws {
        var iterator = newElements.makeIterator()
        guard let firstElement = try iterator.next()?.get() else {
            self = .arbitrary([])
            return
        }
        guard let secondElement = try iterator.next()?.get() else {
            // newElements just contains a single element
            // and we hit the fast path
            self = .one(firstElement)
            return
        }

        var elements: [Element] = []
        elements.reserveCapacity(newElements.underestimatedCount)
        elements.append(firstElement)
        elements.append(secondElement)
        while let nextElement = try iterator.next()?.get() {
            elements.append(nextElement)
        }
        self = .arbitrary(elements)
    }

    @inlinable
    init() {
        self = .arbitrary([])
    }

    @inlinable
    mutating func append(_ newElement: Element) {
        self.append(contentsOf: CollectionOfOne(newElement))
    }

    @inlinable
    mutating func append(contentsOf newElements: some Sequence<Element>) {
        switch self {
        case .one(let firstElement):
            var iterator = newElements.makeIterator()
            guard let secondElement = iterator.next() else {
                // newElements is empty, nothing to do
                return
            }
            var elements: [Element] = []
            elements.reserveCapacity(1 + newElements.underestimatedCount)
            elements.append(firstElement)
            elements.append(secondElement)
            elements.appendRemainingElements(from: &iterator)
            self = .arbitrary(elements)

        case .arbitrary(var elements):
            if elements.isEmpty {
                // if `self` is currently empty and `newElements` just contains a single
                // element, we skip allocating an array and set `self` to `.one(firstElement)`
                var iterator = newElements.makeIterator()
                guard let firstElement = iterator.next() else {
                    // newElements is empty, nothing to do
                    return
                }
                guard let secondElement = iterator.next() else {
                    // newElements just contains a single element
                    // and we hit the fast path
                    self = .one(firstElement)
                    return
                }
                elements.reserveCapacity(elements.count + newElements.underestimatedCount)
                elements.append(firstElement)
                elements.append(secondElement)
                elements.appendRemainingElements(from: &iterator)
                self = .arbitrary(elements)

            } else {
                elements.append(contentsOf: newElements)
                self = .arbitrary(elements)
            }

        }
    }

    @discardableResult
    @inlinable
    mutating func remove(at index: Int) -> Element {
        switch self {
        case .one(let oldElement):
            guard index == 0 else {
                fatalError("index \(index) out of bounds")
            }
            self = .arbitrary([])
            return oldElement

        case .arbitrary(var elements):
            defer {
                self = .arbitrary(elements)
            }
            return elements.remove(at: index)

        }
    }

    @inlinable
    mutating func removeAll(where shouldBeRemoved: (Element) throws -> Bool) rethrows {
        switch self {
        case .one(let oldElement):
            if try shouldBeRemoved(oldElement) {
                self = .arbitrary([])
            }

        case .arbitrary(var elements):
            defer {
                self = .arbitrary(elements)
            }
            return try elements.removeAll(where: shouldBeRemoved)

        }
    }

    @inlinable
    mutating func sort(by areInIncreasingOrder: (Element, Element) throws -> Bool) rethrows {
        switch self {
        case .one:
            // a collection of just one element is always sorted, nothing to do
            break
        case .arbitrary(var elements):
            defer {
                self = .arbitrary(elements)
            }

            try elements.sort(by: areInIncreasingOrder)
        }
    }
}

extension Array {
    @inlinable
    mutating func appendRemainingElements(from iterator: inout some IteratorProtocol<Element>) {
        while let nextElement = iterator.next() {
            append(nextElement)
        }
    }
}

Coverage Report

Created: 2026-10-28 06:59

Line	Count	Source
1		//===----------------------------------------------------------------------===//
2		//
3		// This source file is part of the SwiftNIO open source project
4		//
5		// Copyright (c) 2023 Apple Inc. and the SwiftNIO project authors
6		// Licensed under Apache License v2.0
7		//
8		// See LICENSE.txt for license information
9		// See CONTRIBUTORS.txt for the list of SwiftNIO project authors
10		//
11		// SPDX-License-Identifier: Apache-2.0
12		//
13		//===----------------------------------------------------------------------===//
14		//===----------------------------------------------------------------------===//
15		//
16		// This source file is part of the SwiftCertificates open source project
17		//
18		// Copyright (c) 2023 Apple Inc. and the SwiftCertificates project authors
19		// Licensed under Apache License v2.0
20		//
21		// See LICENSE.txt for license information
22		// See CONTRIBUTORS.txt for the list of SwiftCertificates project authors
23		//
24		// SPDX-License-Identifier: Apache-2.0
25		//
26		//===----------------------------------------------------------------------===//
27
28		/// ``TinyArray`` is a ``RandomAccessCollection`` optimised to store zero or one ``Element``.
29		/// It supports arbitrary many elements but if only up to one ``Element`` is stored it does not allocate separate storage on the heap
30		/// and instead stores the ``Element`` inline.
31		public struct _TinyArray<Element> {
32		@usableFromInline
33		enum Storage {
34		case one(Element)
35		case arbitrary([Element])
36		}
37
38		@usableFromInline
39		var storage: Storage
40		}
41
42		// MARK: - TinyArray "public" interface
43
44		extension _TinyArray: Equatable where Element: Equatable {}
45		extension _TinyArray: Hashable where Element: Hashable {}
46		extension _TinyArray: Sendable where Element: Sendable {}
47
48		extension _TinyArray: RandomAccessCollection {
49		public typealias Element = Element
50
51		public typealias Index = Int
52
53		@inlinable
54	0	public func makeIterator() -> Iterator {
55	0	Iterator(storage: self.storage)
56	0	}
57
58		public struct Iterator: IteratorProtocol {
59		@usableFromInline
60		let _storage: Storage
61		@usableFromInline
62		var _index: Index
63
64		@usableFromInline
65	0	init(storage: Storage) {
66	0	self._storage = storage
67	0	self._index = storage.startIndex
68	0	}
69
70		@inlinable
71	0	public mutating func next() -> Element? {
72	0	if self._index == self._storage.endIndex {
73	0	return nil
74	0	}
75	0
76	0	defer {
77	0	self._index &+= 1
78	0	}
79	0
80	0	return self._storage[self._index]
81	0	}
82		}
83
84		@inlinable
85		public subscript(position: Int) -> Element {
86	0	get {
87	0	self.storage[position]
88	0	}
89		}
90
91		@inlinable
92	0	public var startIndex: Int {
93	0	self.storage.startIndex
94	0	}
95
96		@inlinable
97	0	public var endIndex: Int {
98	0	self.storage.endIndex
99	0	}
100		}
101
102		extension _TinyArray.Iterator: Sendable where Element: Sendable {}
103
104		extension _TinyArray {
105		@inlinable
106	0	public init(_ elements: some Sequence<Element>) {
107	0	self.storage = .init(elements)
108	0	}
109
110		@inlinable
111	0	public init(_ elements: some Sequence<Result<Element, some Error>>) throws {
112	0	self.storage = try .init(elements)
113	0	}
114
115		@inlinable
116	0	public init() {
117	0	self.storage = .init()
118	0	}
119
120		@inlinable
121	0	public mutating func append(_ newElement: Element) {
122	0	self.storage.append(newElement)
123	0	}
124
125		@inlinable
126	0	public mutating func append(contentsOf newElements: some Sequence<Element>) {
127	0	self.storage.append(contentsOf: newElements)
128	0	}
129
130		@discardableResult
131		@inlinable
132	0	public mutating func remove(at index: Int) -> Element {
133	0	self.storage.remove(at: index)
134	0	}
135
136		@inlinable
137	0	public mutating func removeAll(where shouldBeRemoved: (Element) throws -> Bool) rethrows {
138	0	try self.storage.removeAll(where: shouldBeRemoved)
139	0	}
140
141		@inlinable
142	0	public mutating func sort(by areInIncreasingOrder: (Element, Element) throws -> Bool) rethrows {
143	0	try self.storage.sort(by: areInIncreasingOrder)
144	0	}
145		}
146
147		// MARK: - TinyArray.Storage "private" implementation
148
149		extension _TinyArray.Storage: Equatable where Element: Equatable {
150		@inlinable
151	0	static func == (lhs: Self, rhs: Self) -> Bool {
152	0	switch (lhs, rhs) {
153	0	case (.one(let lhs), .one(let rhs)):
154	0	return lhs == rhs
155	0	case (.arbitrary(let lhs), .arbitrary(let rhs)):
156	0	// we don't use lhs.elementsEqual(rhs) so we can hit the fast path from Array
157	0	// if both arrays share the same underlying storage: https://github.com/apple/swift/blob/b42019005988b2d13398025883e285a81d323efa/stdlib/public/core/Array.swift#L1775
158	0	return lhs == rhs
159	0
160	0	case (.one(let element), .arbitrary(let array)),
161	0	(.arbitrary(let array), .one(let element)):
162	0	guard array.count == 1 else {
163	0	return false
164	0	}
165	0	return element == array[0]
166	0
167	0	}
168	0	}
169		}
170		extension _TinyArray.Storage: Hashable where Element: Hashable {
171		@inlinable
172	0	func hash(into hasher: inout Hasher) {
173	0	// same strategy as Array: https://github.com/apple/swift/blob/b42019005988b2d13398025883e285a81d323efa/stdlib/public/core/Array.swift#L1801
174	0	hasher.combine(count)
175	0	for element in self {
176	0	hasher.combine(element)
177	0	}
178	0	}
179		}
180		extension _TinyArray.Storage: Sendable where Element: Sendable {}
181
182		extension _TinyArray.Storage: RandomAccessCollection {
183		@inlinable
184		subscript(position: Int) -> Element {
185	0	get {
186	0	switch self {
187	0	case .one(let element):
188	0	guard position == 0 else {
189	0	fatalError("index \(position) out of bounds")
190	0	}
191	0	return element
192	0	case .arbitrary(let elements):
193	0	return elements[position]
194	0	}
195	0	}
196		}
197
198		@inlinable
199	0	var startIndex: Int {
200	0	0
201	0	}
202
203		@inlinable
204	0	var endIndex: Int {
205	0	switch self {
206	0	case .one: return 1
207	0	case .arbitrary(let elements): return elements.endIndex
208	0	}
209	0	}
210		}
211
212		extension _TinyArray.Storage {
213		@inlinable
214	0	init(_ elements: some Sequence<Element>) {
215	0	self = .arbitrary([])
216	0	self.append(contentsOf: elements)
217	0	}
218
219		@inlinable
220	0	init(_ newElements: some Sequence<Result<Element, some Error>>) throws {
221	0	var iterator = newElements.makeIterator()
222	0	guard let firstElement = try iterator.next()?.get() else {
223	0	self = .arbitrary([])
224	0	return
225	0	}
226	0	guard let secondElement = try iterator.next()?.get() else {
227	0	// newElements just contains a single element
228	0	// and we hit the fast path
229	0	self = .one(firstElement)
230	0	return
231	0	}
232	0
233	0	var elements: [Element] = []
234	0	elements.reserveCapacity(newElements.underestimatedCount)
235	0	elements.append(firstElement)
236	0	elements.append(secondElement)
237	0	while let nextElement = try iterator.next()?.get() {
238	0	elements.append(nextElement)
239	0	}
240	0	self = .arbitrary(elements)
241	0	}
242
243		@inlinable
244	0	init() {
245	0	self = .arbitrary([])
246	0	}
247
248		@inlinable
249	0	mutating func append(_ newElement: Element) {
250	0	self.append(contentsOf: CollectionOfOne(newElement))
251	0	}
252
253		@inlinable
254	0	mutating func append(contentsOf newElements: some Sequence<Element>) {
255	0	switch self {
256	0	case .one(let firstElement):
257	0	var iterator = newElements.makeIterator()
258	0	guard let secondElement = iterator.next() else {
259	0	// newElements is empty, nothing to do
260	0	return
261	0	}
262	0	var elements: [Element] = []
263	0	elements.reserveCapacity(1 + newElements.underestimatedCount)
264	0	elements.append(firstElement)
265	0	elements.append(secondElement)
266	0	elements.appendRemainingElements(from: &iterator)
267	0	self = .arbitrary(elements)
268	0
269	0	case .arbitrary(var elements):
270	0	if elements.isEmpty {
271	0	// if `self` is currently empty and `newElements` just contains a single
272	0	// element, we skip allocating an array and set `self` to `.one(firstElement)`
273	0	var iterator = newElements.makeIterator()
274	0	guard let firstElement = iterator.next() else {
275	0	// newElements is empty, nothing to do
276	0	return
277	0	}
278	0	guard let secondElement = iterator.next() else {
279	0	// newElements just contains a single element
280	0	// and we hit the fast path
281	0	self = .one(firstElement)
282	0	return
283	0	}
284	0	elements.reserveCapacity(elements.count + newElements.underestimatedCount)
285	0	elements.append(firstElement)
286	0	elements.append(secondElement)
287	0	elements.appendRemainingElements(from: &iterator)
288	0	self = .arbitrary(elements)
289	0
290	0	} else {
291	0	elements.append(contentsOf: newElements)
292	0	self = .arbitrary(elements)
293	0	}
294	0
295	0	}
296	0	}
297
298		@discardableResult
299		@inlinable
300	0	mutating func remove(at index: Int) -> Element {
301	0	switch self {
302	0	case .one(let oldElement):
303	0	guard index == 0 else {
304	0	fatalError("index \(index) out of bounds")
305	0	}
306	0	self = .arbitrary([])
307	0	return oldElement
308	0
309	0	case .arbitrary(var elements):
310	0	defer {
311	0	self = .arbitrary(elements)
312	0	}
313	0	return elements.remove(at: index)
314	0
315	0	}
316	0	}
317
318		@inlinable
319	0	mutating func removeAll(where shouldBeRemoved: (Element) throws -> Bool) rethrows {
320	0	switch self {
321	0	case .one(let oldElement):
322	0	if try shouldBeRemoved(oldElement) {
323	0	self = .arbitrary([])
324	0	}
325	0
326	0	case .arbitrary(var elements):
327	0	defer {
328	0	self = .arbitrary(elements)
329	0	}
330	0	return try elements.removeAll(where: shouldBeRemoved)
331	0
332	0	}
333	0	}
334
335		@inlinable
336	0	mutating func sort(by areInIncreasingOrder: (Element, Element) throws -> Bool) rethrows {
337	0	switch self {
338	0	case .one:
339	0	// a collection of just one element is always sorted, nothing to do
340	0	break
341	0	case .arbitrary(var elements):
342	0	defer {
343	0	self = .arbitrary(elements)
344	0	}
345	0
346	0	try elements.sort(by: areInIncreasingOrder)
347	0	}
348	0	}
349		}
350
351		extension Array {
352		@inlinable
353	0	mutating func appendRemainingElements(from iterator: inout some IteratorProtocol<Element>) {
354	0	while let nextElement = iterator.next() {
355	0	append(nextElement)
356	0	}
357	0	}
358		}