swift-collections: OrderedSet.intersection crashes due to out of bounds index

This turned out to be caused by a missing uniqueness check in a couple of OrderedSet mutation operations, leading to a violation of value semantics.

Embarrassingly, this wasn’t caught by the existing tests that check value semantics, because they only checked that iteration over old snapshots still provided consistent results, not that those snapshots were fully self-consistent. D’oh!

The fix is #123; this will ship in a new release very soon.

Big shoutout to @KaiOelfke for providing me with a reproducer!

In a small learning project I can reproduce this or a similar crash in a 100% reliable manner. I cloned the swift-collections repo and added it all into a xcworkspace as recommended by @lorentey.

Calling state.cards._dictionary._checkInvariants() directly after state.cards.insert(card, at: 0) succeeds. But the next SwiftUI view update crashes. Calling po self.cards._dictionary._checkInvariants() immediately before the crash results in a precondition failure.

OrderedCollections/OrderedSet+Invariants.swift:28: Precondition failed: Index 0 not found in hash table (element: FA9A6EA9-7E4C-40B2-A8C0-4D3ACC5660E0)
2021-11-07 16:55:16.885554+0100 SwipePreview[13530:5205563] OrderedCollections/OrderedSet+Invariants.swift:28: Precondition failed: Index 0 not found in hash table (element: FA9A6EA9-7E4C-40B2-A8C0-4D3ACC5660E0)
error: Execution was interrupted, reason: EXC_BREAKPOINT (code=1, subcode=0x18f786a00).

After the insert there’s 30 items. However in the view update the inserted item is not present anymore. There’s only 29 items.

Thanks for taking a look!

1. Yep, the literal type, as described by the debugger is Tagged<AppModels.Product, Foundation.UUID>. Tagged conforms to Hashable whenever it’s RawValue does, and the implementation is synthesized.
2. I do not, knowingly, do any async or concurrent work. I tend to do everything on the main queue until I see a need to do anything else. The code is running within a Composable Architecture Effect which is essentially a Combine publisher. I’ve added a debounce on the main queue, crash still happens. I can’t rule out reads though. The struct that holds the set is shared app state, but there are no mutations happening anywhere else.
3. The set is actually the keys property of an OrderedDictionary. The OrderedDictionary or the type that wraps it is long lived within my code. It sees one big insertion of the 1300 items when they are loaded from the database. Then one single insertion that triggers the crashing code when I diff the new set with a copy of the previous version. The big insertion from the database is manually dispatched to the main queue. There are no removals. The IdentifiedArray is initialized using this initializer which seems to call out to this initializer to create its internal OrderedDictionary.

Ran the app with Adress Sanitizer turned on (and “Detect use of stack after return”). Never done that before, but didn’t see any warnings in the console or in Xcode.

Tried running with the build conditions. Not sure if I did it right though.

Sorry if this is not of much help. Let me know if there’s anything else I can do to attempt to pin-point the issue. I understand it’s very likely that the cause is something I’m doing or any of the layers between me and the corrupted set.

Hi folks, I’ve been seeing a similar issue via the IdentifiedArray type that wraps an OrderedDictionary and the crash log looks really similar as well, with 21 of 23 lines here being the same: https://github.com/pointfreeco/swift-identified-collections/issues/26#issuecomment-943193186

Poking around in the stacktrace a bit and it seems like at some point _UnsafeHashTable._find(_:in:) tries to subscript the elements at an _offset of 31, while the ordered dictionary in question has 31 elements. Interestingly in my case, I can only reproduce this crash with this particular set of data. This is for an app where I’m adding a message to a list, and only this one particular list produces this crash; any time I add a message here it crashes, adding a message to any other thread does not. This is with an n of ~5, so presumably there are other crashing values too; my point here is for some reason only particular bits of data cause the crash.

I’m trying to make a small reproducible test case, which is made a bit difficult by the fact that pretty much the same code does not crash in another code path; i’m adding the reply to the list after it’s accepted by the server. When I relaunch the app and attempt to sync again, it sends back an array with the same exact value, and this time the code does not crash, which has me a bit befuddled. Adding a fresh reply after this initial merge however does cause the same crash, and so I’m not really sure what’s happening here.

I realise this probably isn’t very helpful without a reproducible sample but until I can have that, please do let me know if I can help in any other way.

I have been trying to reproduce this in a smaller sample project to no avail. It is still 100% reproducible in my main project, even using version 1.0.1 of Collections. I’d be willing to send you the code for my entire app through some private means and walk you through how to trigger the issue if you think that’d help!

I have not forgotten about this. Just a little tied up at the moment, as I mentioned.

The instance of Collections that I’m using is a dependency, to a dependency, to a dependency at the moment. If I add my own dependency on Collections in my Package.json, will that version be used by my dependencies as well? Not if it’s pinned to another version, right?

(0.0.7 has the same OrderedSet implementation as main – there is no reason to spend effort on reproducing this there.)