| // RUN: %target-run-simple-swiftgyb |
| // REQUIRES: executable_test |
| |
| import StdlibUnittest |
| import StdlibCollectionUnittest |
| |
| let CopyToNativeArrayBufferTests = TestSuite("CopyToNativeArrayBufferTests") |
| |
| extension Array { |
| func _rawIdentifier() -> Int { |
| return unsafeBitCast(self, to: Int.self) |
| } |
| } |
| |
| CopyToNativeArrayBufferTests.test("Sequence._copyToContiguousArray()") { |
| do { |
| // Call from a static context. |
| let s = |
| MinimalSequence(elements: LifetimeTracked(10)..<LifetimeTracked(27)) |
| |
| expectEqual(0, s.timesMakeIteratorCalled.value) |
| let copy = s._copyToContiguousArray() |
| expectEqual(1, s.timesMakeIteratorCalled.value) |
| expectEqualSequence( |
| Array(10..<27), |
| copy.map { $0.value }) |
| } |
| do { |
| // Call from a generic context. |
| let wrapped = MinimalSequence(elements: LifetimeTracked(10)..<LifetimeTracked(27)) |
| let s = LoggingSequence(wrapping: wrapped) |
| |
| expectEqual(0, wrapped.timesMakeIteratorCalled.value) |
| let copy = s._copyToContiguousArray() |
| expectEqual(1, wrapped.timesMakeIteratorCalled.value) |
| expectEqualSequence( |
| Array(10..<27), |
| copy.map { $0.value }) |
| } |
| } |
| |
| CopyToNativeArrayBufferTests.test("Collection._copyToContiguousArray()") { |
| // Check that collections are handled with the collection-specific API. This |
| // means that we are calling the right default implementation (one for |
| // collections, not the one for sequences). |
| |
| do { |
| // Call from a static context. |
| let c = |
| DefaultedCollection(elements: LifetimeTracked(10)..<LifetimeTracked(27)) |
| |
| expectEqual(0, c.timesMakeIteratorCalled.value) |
| expectEqual(0, c.timesStartIndexCalled.value) |
| let copy = c._copyToContiguousArray() |
| expectEqual(0, c.timesMakeIteratorCalled.value) |
| expectNotEqual(0, c.timesStartIndexCalled.value) |
| expectEqualSequence( |
| Array(10..<27), |
| copy.map { $0.value }) |
| } |
| do { |
| // Call from a generic context. |
| let wrapped = |
| DefaultedCollection(elements: LifetimeTracked(10)..<LifetimeTracked(27)) |
| let s = LoggingSequence(wrapping: wrapped) |
| expectEqual(0, wrapped.timesMakeIteratorCalled.value) |
| expectEqual(0, wrapped.timesStartIndexCalled.value) |
| let copy = s._copyToContiguousArray() |
| expectEqual(0, wrapped.timesMakeIteratorCalled.value) |
| expectNotEqual(0, wrapped.timesStartIndexCalled.value) |
| |
| expectEqualSequence( |
| Array(10..<27), |
| copy.map { $0.value }) |
| } |
| } |
| |
| %{ |
| all_array_types = ['ContiguousArray', 'ArraySlice', 'Array'] |
| }% |
| |
| var ArrayTestSuite = TestSuite("Array") |
| |
| ArrayTestSuite.test("sizeof") { |
| var a = [ 10, 20, 30 ] |
| #if arch(i386) || arch(arm) |
| expectEqual(4, MemoryLayout.size(ofValue: a)) |
| #else |
| expectEqual(8, MemoryLayout.size(ofValue: a)) |
| #endif |
| } |
| |
| ArrayTestSuite.test("valueDestruction") { |
| var a = [LifetimeTracked]() |
| for i in 100...110 { |
| a.append(LifetimeTracked(i)) |
| } |
| } |
| |
| //===----------------------------------------------------------------------===// |
| // Native array tests |
| // FIXME: incomplete. |
| //===----------------------------------------------------------------------===// |
| |
| ArrayTestSuite.test("Native/count/empty") { |
| let a = [LifetimeTracked]() |
| expectEqual(0, a.count) |
| } |
| |
| ArrayTestSuite.test("Native/count") { |
| let a = [ LifetimeTracked(10), LifetimeTracked(20), LifetimeTracked(30) ] |
| expectEqual(3, a.count) |
| } |
| |
| ArrayTestSuite.test("Native/isEmpty/empty") { |
| let a = [LifetimeTracked]() |
| expectTrue(a.isEmpty) |
| } |
| |
| ArrayTestSuite.test("Native/isEmpty") { |
| let a = [ LifetimeTracked(10), LifetimeTracked(20), LifetimeTracked(30) ] |
| expectFalse(a.isEmpty) |
| } |
| |
| % for Kind in ['Array', 'ContiguousArray']: |
| ArrayTestSuite.test("${Kind}/popLast") { |
| // Empty |
| do { |
| var a = ${Kind}<Int>() |
| let popped = a.popLast() |
| expectNil(popped) |
| expectTrue(a.isEmpty) |
| } |
| |
| do { |
| var popped = [Int]() |
| var a: ${Kind}<Int> = [1010, 2020, 3030] |
| while let element = a.popLast() { |
| popped.append(element) |
| } |
| expectEqualSequence([1010, 2020, 3030], popped.reversed()) |
| expectTrue(a.isEmpty) |
| } |
| } |
| % end |
| |
| //===----------------------------------------------------------------------===// |
| // COW(🐄) tests |
| //===----------------------------------------------------------------------===// |
| |
| class COWBox< |
| T: Equatable & CustomStringConvertible> |
| : Equatable, CustomStringConvertible { |
| var value: T |
| |
| init(_ value: T) { |
| self.value = value |
| } |
| |
| var description: String { |
| return "Boxed: \(value.description)" |
| } |
| |
| static func ==(lhs: COWBox, rhs: COWBox) -> Bool { |
| return lhs.value == rhs.value |
| } |
| } |
| |
| ArrayTestSuite.test("COW.Smoke") { |
| var a1 = Array<COWBox<Int>>(repeating: COWBox(0), count: 10) |
| var identity1 = a1._rawIdentifier() |
| |
| a1[0] = COWBox(1) |
| a1[1] = COWBox(2) |
| a1[2] = COWBox(3) |
| |
| var a2 = a1 |
| expectEqual(identity1, a2._rawIdentifier()) |
| |
| a2[3] = COWBox(4) |
| expectNotEqual(identity1, a2._rawIdentifier()) |
| |
| a1[4] = COWBox(5) |
| expectEqual(identity1, a1._rawIdentifier()) |
| |
| _blackHole(a1) |
| _blackHole(a2) |
| } |
| |
| func getCOWFastArray() -> Array<Int> { |
| var a = Array<Int>() |
| a.reserveCapacity(10) |
| a.append(1) |
| a.append(2) |
| a.append(3) |
| return a |
| } |
| |
| func getCOWSlowArray() -> Array<COWBox<Int>> { |
| var a = Array<COWBox<Int>>() |
| a.reserveCapacity(10) |
| a.append(COWBox(1)) |
| a.append(COWBox(2)) |
| a.append(COWBox(3)) |
| return a |
| } |
| |
| ArrayTestSuite.test("COW.Fast.SubscriptWithIndexDoesNotReallocate") { |
| var a = getCOWFastArray() |
| var identity1 = a._rawIdentifier() |
| var startIndex = a.startIndex |
| |
| expectNotEqual(0, a[startIndex]) |
| expectEqual(identity1, a._rawIdentifier()) |
| } |
| |
| ArrayTestSuite.test("COW.Slow.SubscriptWithIndexDoesNotReallocate") { |
| var a = getCOWSlowArray() |
| var identity1 = a._rawIdentifier() |
| var startIndex = a.startIndex |
| |
| expectNotEqual(0, a[startIndex].value) |
| expectEqual(identity1, a._rawIdentifier()) |
| } |
| |
| ArrayTestSuite.test("COW.Fast.RemoveAtDoesNotReallocate") { |
| do { |
| var a = getCOWFastArray() |
| var identity1 = a._rawIdentifier() |
| |
| let index1 = 1 |
| expectEqual(identity1, a._rawIdentifier()) |
| |
| expectEqual(2, a[index1]) |
| |
| let removed = a.remove(at: index1) |
| expectEqual(2, removed) |
| |
| expectEqual(identity1, a._rawIdentifier()) |
| } |
| |
| do { |
| var a1 = getCOWFastArray() |
| var identity1 = a1._rawIdentifier() |
| |
| var a2 = a1 |
| expectEqual(identity1, a1._rawIdentifier()) |
| expectEqual(identity1, a2._rawIdentifier()) |
| |
| var index1 = 1 |
| expectEqual(2, a2[index1]) |
| expectEqual(identity1, a1._rawIdentifier()) |
| expectEqual(identity1, a2._rawIdentifier()) |
| |
| let removed = a2.remove(at: index1) |
| expectEqual(2, removed) |
| |
| expectEqual(identity1, a1._rawIdentifier()) |
| expectNotEqual(identity1, a2._rawIdentifier()) |
| } |
| } |
| |
| ArrayTestSuite.test("COW.Slow.RemoveAtDoesNotReallocate") { |
| do { |
| var a = getCOWSlowArray() |
| var identity1 = a._rawIdentifier() |
| |
| let index1 = 1 |
| expectEqual(identity1, a._rawIdentifier()) |
| |
| expectEqual(2, a[index1].value) |
| |
| let removed = a.remove(at: index1) |
| expectEqual(2, removed.value) |
| |
| expectEqual(identity1, a._rawIdentifier()) |
| } |
| |
| do { |
| var a1 = getCOWSlowArray() |
| var identity1 = a1._rawIdentifier() |
| |
| var a2 = a1 |
| expectEqual(identity1, a1._rawIdentifier()) |
| expectEqual(identity1, a2._rawIdentifier()) |
| |
| var index1 = 1 |
| expectEqual(2, a2[index1].value) |
| expectEqual(identity1, a1._rawIdentifier()) |
| expectEqual(identity1, a2._rawIdentifier()) |
| |
| let removed = a2.remove(at: index1) |
| expectEqual(2, removed.value) |
| |
| expectEqual(identity1, a1._rawIdentifier()) |
| expectNotEqual(identity1, a2._rawIdentifier()) |
| } |
| } |
| |
| ArrayTestSuite.test("COW.Fast.RemoveAllDoesNotReallocate") |
| .skip(.linuxAny(reason: "rdar://problem/34268868")).code { |
| do { |
| var a = getCOWFastArray() |
| let originalCapacity = a.capacity |
| expectEqual(3, a.count) |
| expectEqual(2, a[1]) |
| |
| a.removeAll() |
| var identity1 = a._rawIdentifier() |
| expectLT(a.capacity, originalCapacity) |
| expectEqual(0, a.count) |
| expectEqual(identity1, a._rawIdentifier()) |
| } |
| |
| do { |
| var a = getCOWFastArray() |
| var identity1 = a._rawIdentifier() |
| let originalCapacity = a.capacity |
| expectEqual(3, a.count) |
| expectEqual(2, a[1]) |
| |
| a.removeAll(keepingCapacity: true) |
| expectEqual(identity1, a._rawIdentifier()) |
| expectEqual(originalCapacity, a.capacity) |
| expectEqual(0, a.count) |
| } |
| |
| do { |
| var a1 = getCOWFastArray() |
| var identity1 = a1._rawIdentifier() |
| expectEqual(3, a1.count) |
| expectEqual(2, a1[1]) |
| |
| var a2 = a1 |
| a2.removeAll() |
| var identity2 = a2._rawIdentifier() |
| expectEqual(identity1, a1._rawIdentifier()) |
| expectNotEqual(identity2, identity1) |
| expectEqual(3, a1.count) |
| expectEqual(2, a1[1]) |
| expectEqual(0, a2.count) |
| |
| // Keep variables alive. |
| _blackHole(a1) |
| _blackHole(a2) |
| } |
| |
| do { |
| var a1 = getCOWFastArray() |
| var identity1 = a1._rawIdentifier() |
| let originalCapacity = a1.capacity |
| expectEqual(3, a1.count) |
| expectEqual(2, a1[1]) |
| |
| var a2 = a1 |
| a2.removeAll(keepingCapacity: true) |
| var identity2 = a2._rawIdentifier() |
| expectEqual(identity1, a1._rawIdentifier()) |
| expectNotEqual(identity2, identity1) |
| expectEqual(3, a1.count) |
| expectEqual(2, a1[1]) |
| expectEqual(originalCapacity, a2.capacity) |
| expectEqual(0, a2.count) |
| |
| // Keep variables alive. |
| _blackHole(a1) |
| _blackHole(a2) |
| } |
| } |
| |
| ArrayTestSuite.test("COW.Slow.RemoveAllDoesNotReallocate") |
| .skip(.linuxAny(reason: "rdar://problem/34268868")).code { |
| do { |
| var a = getCOWSlowArray() |
| let originalCapacity = a.capacity |
| expectEqual(3, a.count) |
| expectEqual(2, a[1].value) |
| |
| a.removeAll() |
| var identity1 = a._rawIdentifier() |
| expectLT(a.capacity, originalCapacity) |
| expectEqual(0, a.count) |
| expectEqual(identity1, a._rawIdentifier()) |
| } |
| |
| do { |
| var a = getCOWSlowArray() |
| var identity1 = a._rawIdentifier() |
| let originalCapacity = a.capacity |
| expectEqual(3, a.count) |
| expectEqual(2, a[1].value) |
| |
| a.removeAll(keepingCapacity: true) |
| expectEqual(identity1, a._rawIdentifier()) |
| expectEqual(originalCapacity, a.capacity) |
| expectEqual(0, a.count) |
| } |
| |
| do { |
| var a1 = getCOWSlowArray() |
| var identity1 = a1._rawIdentifier() |
| expectEqual(3, a1.count) |
| expectEqual(2, a1[1].value) |
| |
| var a2 = a1 |
| a2.removeAll() |
| var identity2 = a2._rawIdentifier() |
| expectEqual(identity1, a1._rawIdentifier()) |
| expectNotEqual(identity2, identity1) |
| expectEqual(3, a1.count) |
| expectEqual(2, a1[1].value) |
| expectEqual(0, a2.count) |
| |
| // Keep variables alive. |
| _blackHole(a1) |
| _blackHole(a2) |
| } |
| |
| do { |
| var a1 = getCOWSlowArray() |
| var identity1 = a1._rawIdentifier() |
| let originalCapacity = a1.capacity |
| expectEqual(3, a1.count) |
| expectEqual(2, a1[1].value) |
| |
| var a2 = a1 |
| a2.removeAll(keepingCapacity: true) |
| var identity2 = a2._rawIdentifier() |
| expectEqual(identity1, a1._rawIdentifier()) |
| expectNotEqual(identity2, identity1) |
| expectEqual(3, a1.count) |
| expectEqual(2, a1[1].value) |
| expectEqual(originalCapacity, a2.capacity) |
| expectEqual(0, a2.count) |
| |
| // Keep variables alive. |
| _blackHole(a1) |
| _blackHole(a2) |
| } |
| } |
| |
| ArrayTestSuite.test("COW.Fast.CountDoesNotReallocate") { |
| var a = getCOWFastArray() |
| var identity1 = a._rawIdentifier() |
| |
| expectEqual(3, a.count) |
| expectEqual(identity1, a._rawIdentifier()) |
| } |
| |
| ArrayTestSuite.test("COW.Slow.CountDoesNotReallocate") { |
| var a = getCOWSlowArray() |
| var identity1 = a._rawIdentifier() |
| |
| expectEqual(3, a.count) |
| expectEqual(identity1, a._rawIdentifier()) |
| } |
| |
| ArrayTestSuite.test("COW.Fast.GenerateDoesNotReallocate") { |
| var a = getCOWFastArray() |
| var identity1 = a._rawIdentifier() |
| |
| var iter = a.makeIterator() |
| var copy = Array<Int>() |
| while let value = iter.next() { |
| copy.append(value) |
| } |
| expectEqual(copy, [ 1, 2, 3 ]) |
| expectEqual(identity1, a._rawIdentifier()) |
| } |
| |
| ArrayTestSuite.test("COW.Slow.GenerateDoesNotReallocate") { |
| var a = getCOWSlowArray() |
| var identity1 = a._rawIdentifier() |
| |
| var iter = a.makeIterator() |
| var copy = Array<Int>() |
| while let value = iter.next() { |
| copy.append(value.value) |
| } |
| expectEqual(copy, [ 1, 2, 3 ]) |
| expectEqual(identity1, a._rawIdentifier()) |
| } |
| |
| ArrayTestSuite.test("COW.Fast.EqualityTestDoesNotReallocate") { |
| var a1 = getCOWFastArray() |
| var identity1 = a1._rawIdentifier() |
| |
| var a2 = getCOWFastArray() |
| var identity2 = a2._rawIdentifier() |
| |
| expectEqual(a1, a2) |
| expectEqual(identity1, a1._rawIdentifier()) |
| expectEqual(identity2, a2._rawIdentifier()) |
| |
| a2[1] = 5 |
| expectTrue(a1 != a2) |
| expectEqual(identity1, a1._rawIdentifier()) |
| expectEqual(identity2, a2._rawIdentifier()) |
| } |
| |
| ArrayTestSuite.test("COW.Slow.EqualityTestDoesNotReallocate") { |
| var a1 = getCOWSlowArray() |
| var identity1 = a1._rawIdentifier() |
| |
| var a2 = getCOWSlowArray() |
| var identity2 = a2._rawIdentifier() |
| |
| expectEqual(a1, a2) |
| expectEqual(identity1, a1._rawIdentifier()) |
| expectEqual(identity2, a2._rawIdentifier()) |
| |
| a2[2] = COWBox(5) |
| expectTrue(a1 != a2) |
| expectEqual(identity1, a1._rawIdentifier()) |
| expectEqual(identity2, a2._rawIdentifier()) |
| } |
| |
| //===----------------------------------------------------------------------===// |
| // Index tests |
| //===----------------------------------------------------------------------===// |
| public struct ArrayIndexTest<T: Collection> { |
| public enum Operation { |
| case append(Int) |
| case insert(Int, at: Int) |
| case partition(by: (OpaqueValue<Int>) throws -> Bool) |
| case removeFirst |
| case removeFirstN(Int) |
| case removeLast |
| case removeLastN(Int) |
| case removeAt(Int) |
| case removeAll(Bool) |
| case removeClosedSubrange(ClosedRange<Int>) |
| case removeHalfClosedSubrange(Range<Int>) |
| } |
| |
| public let data: T |
| public let expectedStart: Int |
| public let expectedEnd: Int |
| public let range: Range<Int>? |
| public let operation: Operation |
| public let loc: SourceLoc |
| |
| public init(data: T, expectedStart: Int, expectedEnd: Int, |
| operation: Operation, range: Range<Int>? = nil, |
| file: String = #file, line: UInt = #line) { |
| self.data = data |
| self.expectedStart = expectedStart |
| self.expectedEnd = expectedEnd |
| self.operation = operation |
| self.range = range |
| self.loc = SourceLoc(file, line, comment: "Array index test data") |
| } |
| } |
| |
| let indexTests: [ArrayIndexTest<[Int]>] = [ |
| // Check how partition() affects indices. |
| ArrayIndexTest( |
| data: [ 99, 1010, 99 ], |
| expectedStart: 1, |
| expectedEnd: 2, |
| operation: .partition(by: { $0.value > 100 } ), |
| range: 1..<2 |
| ), |
| ArrayIndexTest( |
| data: [ 99, 1010, 2020, 99 ], |
| expectedStart: 1, |
| expectedEnd: 3, |
| operation: .partition(by: { $0.value > 0} ), |
| range: 1..<3 |
| ), |
| ArrayIndexTest( |
| data: [ 99, 1010, 2020, 99 ], |
| expectedStart: 1, |
| expectedEnd: 3, |
| operation: .partition(by: { $0.value > 3000 }), |
| range: 1..<3 |
| ), |
| // Check how partition(by:) affects indices. |
| ArrayIndexTest( |
| data: [ 10, 2, -33, 44, -5 ], |
| expectedStart: 0, |
| expectedEnd: 5, |
| operation: .partition(by: { $0.value > 0 }) |
| ), |
| ArrayIndexTest( |
| data: [ 10, 2, -33, 44, -5 ], |
| expectedStart: 0, |
| expectedEnd: 5, |
| operation: .partition(by: { $0.value > 100 }) |
| ), |
| // Check how append affects indices. |
| ArrayIndexTest( |
| data: [ 2 ], |
| expectedStart: 0, |
| expectedEnd: 2, |
| operation: .append(1) |
| ), |
| ArrayIndexTest( |
| data: [], |
| expectedStart: 0, |
| expectedEnd: 1, |
| operation: .append(1) |
| ), |
| // FIXME: re-enable when rdar://problem/33358110 is addressed |
| // ArrayIndexTest( |
| // data: [ 42, 2525, 3535, 42 ], |
| // expectedStart: 1, |
| // expectedEnd: 3, |
| // operation: .append(1), |
| // range: 1..<2 |
| // ), |
| // Check how insert(_:at:) affects indices. |
| ArrayIndexTest( |
| data: [ 2 ], |
| expectedStart: 0, |
| expectedEnd: 2, |
| operation: .insert(2, at: 0) |
| ), |
| ArrayIndexTest( |
| data: [ 2 ], |
| expectedStart: 0, |
| expectedEnd: 2, |
| operation: .insert(2, at: 1) |
| ), |
| ArrayIndexTest( |
| data: [ 42, 2525, 3535, 42 ], |
| expectedStart: 1, |
| expectedEnd: 3, |
| operation: .insert(2, at: 1), |
| range: 1..<2 |
| ), |
| // Check how removeLast() affects indices. |
| ArrayIndexTest( |
| data: [ 1 ], |
| expectedStart: 0, |
| expectedEnd: 0, |
| operation: .removeLast |
| ), |
| ArrayIndexTest( |
| data: [ 1, 2 ], |
| expectedStart: 0, |
| expectedEnd: 0, |
| operation: .removeLast |
| ), |
| ArrayIndexTest( |
| data: [ 99, 1010, 99 ], |
| expectedStart: 1, |
| expectedEnd: 1, |
| operation: .removeLast, |
| range: 1..<2 |
| ), |
| ArrayIndexTest( |
| data: [ 99, 1010, 2020, 99 ], |
| expectedStart: 1, |
| expectedEnd: 2, |
| operation: .removeLast, |
| range: 1..<3 |
| ), |
| // Check how remove(at:) affects indices. |
| ArrayIndexTest( |
| data: [ 1 ], |
| expectedStart: 0, |
| expectedEnd: 0, |
| operation: .removeAt(0) |
| ), |
| ArrayIndexTest( |
| data: [ 1, 2 ], |
| expectedStart: 0, |
| expectedEnd: 1, |
| operation: .removeAt(1) |
| ), |
| ArrayIndexTest( |
| data: [ 99, 1010, 99 ], |
| expectedStart: 1, |
| expectedEnd: 1, |
| operation: .removeAt(1), |
| range: 1..<2 |
| ), |
| ArrayIndexTest( |
| data: [ 99, 1010, 2020, 99 ], |
| expectedStart: 1, |
| expectedEnd: 2, |
| operation: .removeAt(1), |
| range: 1..<3 |
| ), |
| // Check how removeAll(keepingCapacity:) affects indices. |
| ArrayIndexTest( |
| data: [ 1, 2, 3 ], |
| expectedStart: 0, |
| expectedEnd: 0, |
| operation: .removeAll(true) |
| ), |
| ArrayIndexTest( |
| data: [ 1, 2 ], |
| expectedStart: 0, |
| expectedEnd: 0, |
| operation: .removeAll(false) |
| ), |
| ArrayIndexTest( |
| data: [ 99, 1010, 99 ], |
| expectedStart: 1, |
| expectedEnd: 1, |
| operation: .removeAll(true), |
| range: 1..<2 |
| ), |
| ArrayIndexTest( |
| data: [ 99, 1010, 2020, 99 ], |
| expectedStart: 0, |
| expectedEnd: 0, |
| operation: .removeAll(false), |
| range: 1..<2 |
| ), |
| // Check how removeFirst() affects indices. |
| ArrayIndexTest( |
| data: [ 1 ], |
| expectedStart: 0, |
| expectedEnd: 0, |
| operation: .removeFirst |
| ), |
| ArrayIndexTest( |
| data: [ 1, 2 ], |
| expectedStart: 0, |
| expectedEnd: 1, |
| operation: .removeFirst |
| ), |
| ArrayIndexTest( |
| data: [ 99, 1010, 99 ], |
| expectedStart: 2, |
| expectedEnd: 2, |
| operation: .removeFirst, |
| range: 1..<2 |
| ), |
| ArrayIndexTest( |
| data: [ 99, 1010, 2020, 99 ], |
| expectedStart: 2, |
| expectedEnd: 3, |
| operation: .removeFirst, |
| range: 1..<3 |
| ), |
| // Check how removeFirst(_:) affects indices. |
| ArrayIndexTest( |
| data: [ 1, 2 ], |
| expectedStart: 0, |
| expectedEnd: 0, |
| operation: .removeFirstN(2) |
| ), |
| ArrayIndexTest( |
| data: [ 1, 2, 3, 4 ], |
| expectedStart: 0, |
| expectedEnd: 2, |
| operation: .removeFirstN(2) |
| ), |
| ArrayIndexTest( |
| data: [ 99, 1010, 99 ], |
| expectedStart: 3, |
| expectedEnd: 3, |
| operation: .removeFirstN(2), |
| range: 1..<3 |
| ), |
| ArrayIndexTest( |
| data: [ 99, 1010, 2020, 99 ], |
| expectedStart: 3, |
| expectedEnd: 4, |
| operation: .removeFirstN(2), |
| range: 1..<4 |
| ), |
| // Check how removeLast() affects indices. |
| ArrayIndexTest( |
| data: [ 1 ], |
| expectedStart: 0, |
| expectedEnd: 0, |
| operation: .removeLast |
| ), |
| ArrayIndexTest( |
| data: [ 1, 2 ], |
| expectedStart: 0, |
| expectedEnd: 1, |
| operation: .removeLast |
| ), |
| ArrayIndexTest( |
| data: [ 99, 1010, 99 ], |
| expectedStart: 1, |
| expectedEnd: 1, |
| operation: .removeLast, |
| range: 1..<2 |
| ), |
| ArrayIndexTest( |
| data: [ 99, 1010, 2020, 99 ], |
| expectedStart: 1, |
| expectedEnd: 1, |
| operation: .removeLast, |
| range: 1..<2 |
| ), |
| // Check how removeSubrange(_:ClosedRange) affects indices. |
| ArrayIndexTest( |
| data: [ 1 ], |
| expectedStart: 0, |
| expectedEnd: 0, |
| operation: .removeHalfClosedSubrange(0..<1) |
| ), |
| ArrayIndexTest( |
| data: [ 1, 2, 3 ], |
| expectedStart: 0, |
| expectedEnd: 1, |
| operation: .removeHalfClosedSubrange(0..<2) |
| ), |
| ArrayIndexTest( |
| data: [ 1, 2, 3 ], |
| expectedStart: 0, |
| expectedEnd: 1, |
| operation: .removeHalfClosedSubrange(0..<3) |
| ), |
| ArrayIndexTest( |
| data: [ 99, 1010, 99 ], |
| expectedStart: 1, |
| expectedEnd: 1, |
| operation: .removeHalfClosedSubrange(1..<2), |
| range: 1..<2 |
| ), |
| ArrayIndexTest( |
| data: [ 99, 1010, 2020, 99 ], |
| expectedStart: 1, |
| expectedEnd: 2, |
| operation: .removeHalfClosedSubrange(1..<2), |
| range: 1..<3 |
| ), |
| ArrayIndexTest( |
| data: [ 99, 1010, 2020, 99 ], |
| expectedStart: 1, |
| expectedEnd: 2, |
| operation: .removeHalfClosedSubrange(2..<4), |
| range: 1..<4 |
| ), |
| // Check how removeSubrange(_:Range) affects indices. |
| ArrayIndexTest( |
| data: [ 1, 2 ], |
| expectedStart: 0, |
| expectedEnd: 0, |
| operation: .removeClosedSubrange(0...1) |
| ), |
| ArrayIndexTest( |
| data: [ 1, 2, 3 ], |
| expectedStart: 0, |
| expectedEnd: 1, |
| operation: .removeClosedSubrange(0...1) |
| ), |
| ArrayIndexTest( |
| data: [ 1, 2, 3 ], |
| expectedStart: 0, |
| expectedEnd: 1, |
| operation: .removeClosedSubrange(0...2) |
| ), |
| ArrayIndexTest( |
| data: [ 99, 1010, 99 ], |
| expectedStart: 1, |
| expectedEnd: 1, |
| operation: .removeClosedSubrange(1...2), |
| range: 1..<3 |
| ), |
| ArrayIndexTest( |
| data: [ 99, 1010, 2020, 99, 44 ], |
| expectedStart: 1, |
| expectedEnd: 2, |
| operation: .removeClosedSubrange(2...3), |
| range: 1..<4 |
| ), |
| ArrayIndexTest( |
| data: [ 99, 1010, 2020, 99, 44 ], |
| expectedStart: 1, |
| expectedEnd: 2, |
| operation: .removeClosedSubrange(1...2), |
| range: 1..<4 |
| ) |
| ] |
| |
| % for Kind in ['Array', 'ContiguousArray', 'ArraySlice']: |
| ArrayTestSuite.test("ArrayIndexTests") { |
| for test in indexTests { |
| let testData = test.data.map(OpaqueValue.init) |
| % if Kind == 'ArraySlice': |
| guard let range = test.range else { continue } |
| var a = testData[range] |
| % else: |
| if test.range != nil { continue } |
| var a = ${Kind}(testData) |
| % end |
| |
| switch test.operation { |
| case let .append(v): |
| a.append(OpaqueValue(v)) |
| case let .insert(v, index): |
| a.insert(OpaqueValue(v), at: index) |
| case let .partition(c): |
| expectDoesNotThrow({ |
| _ = try a.partition(by: c) |
| }) |
| case .removeFirst: |
| a.removeFirst() |
| case let .removeFirstN(n): |
| a.removeFirst(n) |
| case .removeLast: |
| a.removeLast() |
| case let .removeLastN(n): |
| a.removeLast(n) |
| case let .removeAt(index): |
| a.remove(at: index) |
| case let .removeAll(keepCapacity): |
| a.removeAll(keepingCapacity: keepCapacity) |
| case let .removeHalfClosedSubrange(range): |
| a.removeSubrange(range) |
| case let .removeClosedSubrange(range): |
| a.removeSubrange(range) |
| } |
| |
| expectEqual(test.expectedStart, a.startIndex, stackTrace: SourceLocStack().with(test.loc)) |
| expectEqual(test.expectedEnd, a.endIndex, stackTrace: SourceLocStack().with(test.loc)) |
| } |
| } |
| % end |
| |
| //===----------------------------------------------------------------------===// |
| // Array and EvilCollection that changes its size while we are not looking |
| //===----------------------------------------------------------------------===// |
| |
| let evilBoundsError = "EvilCollection: index out of range" |
| |
| final class EvilSequence : Sequence { |
| init(_ growth: Int) { |
| self.growth = growth |
| } |
| |
| var growth: Int |
| var _count: Int = 20 |
| |
| var underestimatedCount: Int { |
| defer { _count += growth } |
| return _count |
| } |
| |
| func makeIterator() -> AnyIterator<LifetimeTracked> { |
| var i = 0 |
| return AnyIterator { |
| if i >= self._count { return nil } |
| let result = LifetimeTracked(i) |
| i += 1 |
| return result |
| } |
| } |
| } |
| |
| final class EvilCollection : Collection { |
| func index(after i: Int) -> Int { |
| return i + 1 |
| } |
| |
| init(_ growth: Int, boundsChecked: Bool) { |
| self.growth = growth |
| self.boundsChecked = boundsChecked |
| } |
| |
| var growth: Int |
| var _count: Int = 20 |
| var boundsChecked: Bool |
| |
| var startIndex : Int { |
| _count += growth |
| return 0 |
| } |
| |
| var endIndex : Int { |
| return _count |
| } |
| |
| subscript(i: Int) -> LifetimeTracked { |
| if boundsChecked { |
| precondition(i >= 0 && i < _count, evilBoundsError) |
| } |
| return LifetimeTracked(i) |
| } |
| |
| // Default implementation will call _failEarlyRangeCheck, |
| // passing in a startIndex that will grow _count faster than |
| // necessary. |
| func formIndex(after i: inout Int) { |
| i += 1 |
| } |
| } |
| |
| for (step, evilBoundsCheck) in [ (1, true), (-1, false), (-1, true) ] { |
| |
| let message = step < 0 && evilBoundsCheck |
| ? evilBoundsError |
| : "invalid Collection: count differed in successive traversals" |
| |
| let constructionMessage = |
| /*_isStdlibInternalChecksEnabled() && !evilBoundsCheck && step <= 0 |
| ? "_UnsafePartiallyInitializedContiguousArrayBuffer has no more capacity" |
| :*/ message |
| |
| // The invalid Collection error is a _debugPreconditon that will only fire |
| // in a Debug assert configuration. |
| let expectedToFail = (step < 0 && evilBoundsCheck) || |
| _isDebugAssertConfiguration() |
| |
| let natureOfEvil = step > 0 ? "Growth" : "Shrinkage" |
| let boundsChecked = evilBoundsCheck ? "BoundsChecked" : "NoBoundsCheck" |
| let testPrefix = "MemorySafety/\(boundsChecked)/Evil\(natureOfEvil)" |
| |
| ArrayTestSuite.test("\(testPrefix)/Infrastructure/EvilSequence") { |
| let evil = EvilSequence(step) |
| let count0 = evil.underestimatedCount |
| let count1 = evil.underestimatedCount |
| expectNotEqual(count0, count1) |
| if step > 0 { |
| expectLE(count0, count1) |
| } |
| else { |
| expectGE(count0, count1) |
| } |
| } |
| |
| let t1 = ArrayTestSuite.test("\(testPrefix)/Infrastructure/EvilCollection") |
| (evilBoundsCheck && _isDebugAssertConfiguration() |
| ? t1.crashOutputMatches(evilBoundsError) : t1) |
| .code { |
| let evil = EvilCollection(step, boundsChecked: evilBoundsCheck) |
| let count0 = evil.count |
| let count1 = evil.count |
| expectNotEqual(count0, count1) |
| if step > 0 { |
| expectLE(count0, count1) |
| } |
| else { |
| expectGE(count0, count1) |
| } |
| if evilBoundsCheck { |
| expectCrashLater() |
| } |
| let x = evil[-1] |
| _blackHole(x) |
| } |
| |
| let t2 = ArrayTestSuite.test("\(testPrefix)/Construction") |
| (_isDebugAssertConfiguration() && expectedToFail |
| ? t2.crashOutputMatches(constructionMessage) : t2) |
| .code { |
| let evil = EvilCollection(step, boundsChecked: evilBoundsCheck) |
| |
| if expectedToFail { |
| expectCrashLater() |
| } |
| |
| let a = Array(evil) |
| _blackHole(a) |
| } |
| |
| for (op, rangeMax) in ["Grow":0, "Shrink":200] { |
| let t3 = ArrayTestSuite.test("\(testPrefix)/replaceSubrange/\(op)Unique") |
| (_isDebugAssertConfiguration() ? t3.crashOutputMatches(message) : t3) |
| .code { |
| let evil = EvilCollection(step, boundsChecked: evilBoundsCheck) |
| var a = Array((0..<200).lazy.map { LifetimeTracked($0) }) |
| if expectedToFail { |
| expectCrashLater() |
| } |
| a.replaceSubrange(0..<rangeMax, with: evil) |
| } |
| |
| let t4 = ArrayTestSuite.test("\(testPrefix)/replaceSubrange/\(op)NonUnique") |
| (_isDebugAssertConfiguration() ? t4.crashOutputMatches(message) : t4) |
| .code { |
| let evil = EvilCollection(step, boundsChecked: evilBoundsCheck) |
| var a = Array((0..<200).lazy.map { LifetimeTracked($0) }) |
| var b = a |
| if expectedToFail { |
| expectCrashLater() |
| } |
| a.replaceSubrange(0..<rangeMax, with: evil) |
| _blackHole(b) |
| } |
| } |
| |
| ArrayTestSuite.test("\(testPrefix)/SequenceMap") |
| .skip(.custom( |
| { _isFastAssertConfiguration() }, |
| reason: "this trap is not guaranteed to happen in -Ounchecked")) |
| .code { |
| let evil = EvilSequence(step) |
| |
| if step < 0 { |
| expectCrashLater() |
| } |
| let a = evil.map { $0 } |
| _blackHole(a) |
| } |
| |
| ArrayTestSuite.test("\(testPrefix)/CollectionMap") |
| .code { |
| let evil = EvilCollection(step, boundsChecked: evilBoundsCheck) |
| |
| if expectedToFail { |
| expectCrashLater() |
| } |
| |
| let a = evil.map { $0 } |
| _blackHole(a) |
| } |
| |
| ArrayTestSuite.test("\(testPrefix)/FilterAll") |
| .code { |
| let evil = EvilCollection(step, boundsChecked: evilBoundsCheck) |
| |
| let a = evil.filter { _ in true } |
| _blackHole(a) |
| } |
| |
| ArrayTestSuite.test("\(testPrefix)/FilterNone") |
| .code { |
| let evil = EvilCollection(step, boundsChecked: evilBoundsCheck) |
| |
| let a = evil.filter { _ in false } |
| _blackHole(a) |
| } |
| } |
| |
| runAllTests() |