[Fix] Update key generation for adding handlers

[Daniel1of1]

Previous strategy was failing with newer swift versions, this is the same issue as #11. [Edit] ~~It seems that Dictionary.keys is somehow not atomic.~~ This is not true, see below [/Edit] I have not checked the diffs to get to the root cause, however this now passes tests and I added a performance test just to check that it does not add any overhead.

[Daniel1of1]

Update:

I quickly saw that my first solution - be8ee36 was too simplistic. It does not take into account removing handlers.

be8ee36 implementation (failure case)

let receiver = Receiver<Int>.make()
let d1 = receiver.listen(h1) // 1
let d2 = receiver.listen(h2) // 2
d1.dispose() // 3
d3 = receiver.listen(h3) // 4

// handler mutations

// 1 - adding h1
_key = _handlers.count // _key = 0
_handlers[_key] = handle
// _handlers = [ 0: h1 ]

// 2 - adding h2
_key = _handlers.count // _key = 1
_handlers[_key] = handle
// _handlers = [ 0: h1 , 1: h2 ]

// 3 - removing h1
_handlers[_key] = nil // _key = 0 as obtained from d1
// _handlers = [ 1: h2 ]

// 4 - adding h3
_key = _handlers.count // _key = 1
_handlers[_key] = handle 
// _handlers = [ 1: h3 ] ❌ 
// expected [ 1: h2, 2: h3 ] or anything that does not overwrite h2

It turns out this is essentially the same reason for the failure of the original implementation (i.e generating a key that already exists), it was just less obvious and I falsely assumed was some kind of race issue (which I thought was odd since it was done inside an atomic apply)

Original implementation (current master): (failure case)

let receiver = Receiver<Int>.make()
let d1 = receiver.listen(h1) // 1
let d2 = receiver.listen(h2) // 2
d1.dispose() // 3
d3 = receiver.listen(h3) // 4

// handler mutations

// 1 - adding h1
_key = (_handlers.keys.map { $0.hashValue }.max() ?? -1) + 1
// _key == ([] ->(hashValue)-> [] -(max)-> nil ?? -1) + 1 == 0
_handlers[_key] = handle
// _handlers = [ 0: h1 ]

// 2 - adding h2 // e.g 0.hashValue == 100
_key = (_handlers.keys.map { $0.hashValue }.max() ?? -1) + 1 
// _key == ([0] ->(hashValue)-> [100] -(max)-> 100) + 1 == 101
_handlers[_key] = handle
// _handlers = [ 0: h1 , 101: h2 ]

// 3 - removing h1 - unlike `be8ee36` this does not have any affect on correctness
_handlers[_key] = nil // _key = 0 as obtained from d1
// _handlers = [ 101: h2 ]

// 4 - adding h3 //  e.g 101.hashValue == 30
_key = (_handlers.keys.map { $0.hashValue }.max() ?? -1) + 1
// [0,101] ->(hashValue)-> [100, 33] -(max)-> 100
// _key == ([0,101] ->(hashValue)-> [100,33] -(max)-> 100) + 1 == 101
_handlers[_key] = handle 
// _handlers = [ 101: h3 ] ❌ 
// expected [ 101: h2, `X`: h3 ] for some X != 101

The new Implementation simply uses Int.random and double checks that there is no value associated with that key.

_key = Int.random(in: Int.min...Int.max)
while _handlers[_key] != nil {
    _key = Int.random(in: Int.min...Int.max)
}
_handlers[_key] = handle 

As mentioned in this comment in #11 by @kevincador (also apologies for stepping on your toes a bit here, I should have reached out before proposing a solution)... _key = (_handlers.keys.max() ?? -1) + 1 solves this. The reason I didn't just dupe this is because I managed to get myself in an infinite loop with this implementation, but can't be sure if this was a locking bug introduced by being attached in the debugger... @kevincador Have you come across this at all? Further after running a performance test on it, keys.max() is an O(n) operation, so I ended up sticking with Int.random and a collision check which should be quite rare for n <<< UInt.max 😊. If that became an issue, you would also have to think about the type of key by which to key the _handlers and move towards something like UDID. Or perhaps have a seat of available/ not available keys to trade time generating one for some space to contain them, which is almost certainly in the realms of premature optimisation.

Thanks for reading 😊

[kevincador]

Nice @Daniel1of1 ! I have an app in prod since Dec. using the solution I proposed quite extensively. But to be honest my implementation was more a guess found by trial and error. You seem to have nailed it way better.

Note: I didn't investigate it yet but iOS 13 will introduce a new framework (https://developer.apple.com/documentation/combine). I don't know if it will replace Receiver (I'd like to have @RuiAAPeres input on this one 😇).

[RuiAAPeres]

Oh wow, thanks for all this work guys! I need to see if this is working as intended. @kevincador are you using Receiver in production?

[kevincador]

Yes, I'm using Receiver in production since 1.0 of Rippple (https://itunes.apple.com/us/app/rippple-tv-movie-comments/id1309894528) launched in early 2018.

[RuiAAPeres]

@kevincador regarding Combine, it doesn't support iOS 12. It's slightly more complex than Receiver as well: it has more functionality.

[RuiAAPeres]

@Daniel1of1 I am checking how ReactiveSwift does it, and I think it would provide a more robust solution: https://github.com/ReactiveCocoa/ReactiveSwift/blob/master/Sources/Bag.swift#L45 What do you think?

[Daniel1of1]

@RuiAAPeres This seems perfectly suitable, I can essentially just lift it from there. And I'll update accordingly. Do you have a preference on whether to wrap the key in a Token type as in ReactiveSwift or not?

[RuiAAPeres]

I am ok with either.

[Daniel1of1]

@RuiAAPeres done