search

pointfreeco / swift-identified-collections

A library of data structures for working with collections of identifiable elements in an ergonomic, performant way.
MIT License
539 stars 46 forks source link

IdentifiedArray Subscript Read crash #26

Closed Antonito closed 2 years ago

Antonito commented 3 years ago

Hello,

I'm migrating an app to TCA and experiencing crashes in IdentifiedArray.subscript.read during an equality check. Unfortunately I haven't been able to reproduce this case in an isolated example yet.

I haven't been able to reproduce the crash in a predictable way with my app either (it seems to appear 'randomly') – but it seems to be triggered by the use Reducer.debug.

Here is my stack trace:

#0  0x0000000188588cf4 in _swift_runtime_on_report ()
#1  0x0000000188608e60 in _swift_stdlib_reportFatalErrorInFile ()
#2  0x000000018823e23c in closure #1 in closure #1 in closure #1 in _assertionFailure(_:_:file:line:flags:) ()
#3  0x000000018823dfdc in closure #1 in closure #1 in _assertionFailure(_:_:file:line:flags:) ()
#4  0x000000018823d8d0 in _assertionFailure(_:_:file:line:flags:) ()
#5  0x000000018828a0b4 in ContiguousArray.subscript.getter ()
#6  0x0000000104a75860 in OrderedDictionary.Elements.subscript.getter at [...]/checkouts/swift-collections/Sources/OrderedCollections/OrderedDictionary/OrderedDictionary+Elements.swift:273
#7  0x0000000104a54260 in IdentifiedArray.subscript.read at [...]/checkouts/swift-identified-collections/Sources/IdentifiedCollections/IdentifiedArray/IdentifiedArray+Collection.swift:17
#8  0x0000000104a54a04 in protocol witness for Collection.subscript.read in conformance IdentifiedArray<τ_0_0, τ_0_1> ()
#9  0x000000018827c408 in protocol witness for IteratorProtocol.next() in conformance IndexingIterator<τ_0_0> ()
#10 0x00000001883b53a8 in Sequence<>.elementsEqual<τ_0_0>(_:) ()
#11 0x0000000105945b38 in static FriendManagerState.== infix(_:_:) at [...]/Sources/FriendProfileState/FriendManagerState.swift:36
#12 0x0000000105945dd8 in protocol witness for static Equatable.== infix(_:_:) in conformance FriendManagerState ()
#13 0x00000001882a1748 in static Optional<τ_0_0>.== infix(_:_:) ()
#14 0x0000000104a4f6bc in static Box<τ_0_0>.isEqual(_:_:) at [...]/checkouts/swift-custom-dump/Sources/CustomDump/Internal/Box.swift:11
#15 0x0000000104a4f764 in protocol witness for static AnyEquatable.isEqual(_:_:) in conformance <τ_0_0> Box<τ_0_0> ()
#16 0x0000000104a4fe24 in open #1 <τ_0_0>(_:) in isMirrorEqual(_:_:) at [...]/checkouts/swift-custom-dump/Sources/CustomDump/Internal/Box.swift:17
#17 0x0000000104a4f8c4 in isMirrorEqual(_:_:) at [...]/checkouts/swift-custom-dump/Sources/CustomDump/Internal/Box.swift:19
#18 0x0000000104a3e8bc in diff<τ_0_0>(_:_:format:) at [...]/checkouts/swift-custom-dump/Sources/CustomDump/Diff.swift:518
#19 0x00000001049219ac in closure #1 in closure #1 in closure #1 in Reducer.debug<τ_0_0, τ_0_1>(_:state:action:actionFormat:environment:) at [...]/checkouts/swift-composable-architecture/Sources/ComposableArchitecture/Debugging/ReducerDebugging.swift:127
#20 0x00000001049235d4 in partial apply for closure #1 in closure #1 in closure #1 in Reducer.debug<τ_0_0, τ_0_1>(_:state:action:actionFormat:environment:) ()
#21 0x0000000104922068 in thunk for @escaping @callee_guaranteed () -> () ()
#22 0x0000000109b40a20 in _dispatch_call_block_and_release ()
#23 0x0000000109b42700 in _dispatch_client_callout ()
#24 0x0000000109b4a83c in _dispatch_lane_serial_drain ()
#25 0x0000000109b4b558 in _dispatch_lane_invoke ()
#26 0x0000000109b57fa0 in _dispatch_workloop_worker_thread ()
#27 0x00000001f33a91b0 in _pthread_wqthread ()

From what I've been able to debug, at some point IdentifiedArray.subscript(position:Int) is called with an invalid position. The _keys and _values elements of _dictionary go out of sync (in my case, _keys contains 14 elements whereas _dictionary only contains 13 – which causes an out of range access).

For performances reason, one of my TCA state is a class, not a struct, and the crash occurs when its equality is checked. I'm using IdentifiedArray in a lot of other places in struct states and haven't experienced any crash – so this might be related, I guess?

Here is a simplified version of my class:

public final class FriendManagerState: Equatable {
  public internal(set) var friends: IdentifiedArrayOf<FriendProfileState>

  public init(
    friends: IdentifiedArrayOf<FriendProfileState>
  ) {
    self.friends = friends
  }

  public static func == (
    lhs: FriendManagerState, rhs: FriendManagerState
  ) -> Bool {
    // This is the method invoked at step 11 of the stacktrace

    // Also crashes with `lhs.friends.elementsEqual(rhs.friends.elements)`
    return lhs.friends == rhs.friends
  }
}

I'm not doing anything fancy with the array, the only methods I'm calling are updateOrInsert, update, append, sort – and everything is performed on a single queue.

Version: 0.3.1 Xcode 13.0 (release) Swift 5.5 (swiftlang-1300.0.31.1 clang-1300.0.29.1) The crash occurs on iOS 15.0 & 15.1, I haven't been able to test on MacOS.

I'm happy to provide more details if needed – also if this turns out to be a TCA issue, I'll gladly move this issue to its repo.

HarshilShah commented 3 years ago

Not sure if it’s the same bug but we’re also seeing a similar crash on updateOrAppend. Here’s the stacktrace:

#0  0x000000018b16f32c in _swift_runtime_on_report ()
#1  0x000000018b1dfe7c in _swift_stdlib_reportFatalErrorInFile ()
#2  0x000000018aec6aa4 in closure #1 in closure #1 in closure #1 in _assertionFailure(_:_:file:line:flags:) ()
#3  0x000000018aec6848 in closure #1 in closure #1 in _assertionFailure(_:_:file:line:flags:) ()
#4  0x000000018aec61c8 in _assertionFailure(_:_:file:line:flags:) ()
#5  0x000000018aec64bc in _fatalErrorMessage(_:_:file:line:flags:) ()
#6  0x000000018b0db8f8 in UnsafeBufferPointer.subscript.read ()
#7  0x000000018b0db768 in protocol witness for Collection.subscript.read in conformance UnsafeBufferPointer<τ_0_0> ()
#8  0x00000001030fed8c in RandomAccessCollection.subscript.getter at [...]/checkouts/swift-collections/Sources/OrderedCollections/Utilities/RandomAccessCollection+Offsets.swift:28
#9  0x00000001030bca30 in _HashTable.UnsafeHandle._find<τ_0_0>(_:in:) at [...]/checkouts/swift-collections/Sources/OrderedCollections/HashTable/_HashTable+UnsafeHandle.swift:299
#10 0x00000001030fceb0 in closure #1 in closure #1 in OrderedSet._find_inlined(_:) at [...]/checkouts/swift-collections/Sources/OrderedCollections/OrderedSet/OrderedSet.swift:396
#11 0x00000001030fcf14 in thunk for @callee_guaranteed (@unowned _HashTable.UnsafeHandle) -> (@unowned Int?, @unowned _HashTable.Bucket, @error @owned Error) ()
#12 0x00000001030fea20 in partial apply for thunk for @callee_guaranteed (@unowned _HashTable.UnsafeHandle) -> (@unowned Int?, @unowned _HashTable.Bucket, @error @owned Error) ()
#13 0x00000001030c2904 in closure #1 in _HashTable.read<τ_0_0>(_:) at [...]/checkouts/swift-collections/Sources/OrderedCollections/HashTable/_HashTable.swift:151
#14 0x00000001030c2fec in partial apply for closure #1 in _HashTable.read<τ_0_0>(_:) ()
#15 0x000000018afb700c in ManagedBuffer.withUnsafeMutablePointers<τ_0_0>(_:) ()
#16 0x00000001030c2828 in _HashTable.read<τ_0_0>(_:) at [...]/checkouts/swift-collections/Sources/OrderedCollections/HashTable/_HashTable.swift:149
#17 0x00000001030fcd20 in closure #1 in OrderedSet._find_inlined(_:) at [...]/checkouts/swift-collections/Sources/OrderedCollections/OrderedSet/OrderedSet.swift:395
#18 0x00000001030fcfac in thunk for @callee_guaranteed (@unowned UnsafeBufferPointer<τ_0_0>) -> (@unowned Int?, @unowned _HashTable.Bucket, @error @owned Error) ()
#19 0x00000001030fe4b4 in partial apply for thunk for @callee_guaranteed (@unowned UnsafeBufferPointer<τ_0_0>) -> (@unowned Int?, @unowned _HashTable.Bucket, @error @owned Error) ()
#20 0x000000018aea9690 in ContiguousArray.withUnsafeBufferPointer<τ_0_0>(_:) ()
#21 0x00000001030fca4c in OrderedSet._find_inlined(_:) at [...]/checkouts/swift-collections/Sources/OrderedCollections/OrderedSet/OrderedSet.swift:391
#22 0x00000001030fc8bc in OrderedSet._find(_:) at [...]/checkouts/swift-collections/Sources/OrderedCollections/OrderedSet/OrderedSet.swift:385
#23 0x00000001030d9e20 in OrderedDictionary.updateValue(_:forKey:) at [...]/checkouts/swift-collections/Sources/OrderedCollections/OrderedDictionary/OrderedDictionary.swift:541
#24 0x00000001030b22b8 in IdentifiedArray.updateOrAppend(_:) at [...]/checkouts/swift-identified-collections/Sources/IdentifiedCollections/IdentifiedArray/IdentifiedArray+Insertions.swift:67

It crashes reliably on an iOS 15 simulator or an iPhone 6s running iOS 15.0.2 (both debug)

KaiOelfke commented 3 years ago

FYI: There's a PR with a fix now: https://github.com/apple/swift-collections/pull/123