update
it turns out the example i provided was not correct, thanks to @Nickolas_Pohilets for pointing it out. the new corrected example provided
basically it is an example that:
- invalidates Set/Dictionary invariants (e.g. duplicated dictionary keys / set elements)
- when the app doesn't do anything "obviously" wrong (foot shooter)
- which is a pure swift and doesn't involve Objective-C / Foundation bridging.
to not pollute the other thread even further:
let's do a spin-off. the bottom of that thread reveals a problem:
Set / Dictionary invariants could be easily broken if Set elements or Dictionary keys contain values with reference semantics or are themselves reference types. it is easy to get oneself into a situation (either by mistake or on purpose) having two or more equivalent elements in a set, or having a dictionary with duplicated keys.
incorrect example (ignore)
class C: Equatable, Hashable, CustomStringConvertible {
var string: String
init(_ string: String) {
self.string = string
}
static func == (lhs: C, rhs: C) -> Bool {
lhs.string == rhs.string
}
func hash(into hasher: inout Hasher) {
hasher.combine(string)
}
var description: String {
string
}
}
func bar() {
let hello = C("hello")
let world = C("world")
var s: Set<C> = [hello, world]
var d: [C: String] = [hello: "hello value", world: "world value"]
print(s)
print(d)
hello.string = "world"
print(s)
print(d)
s.remove(C("world")) // will this remove one or both values?
d[C("world")] = "which value is going to be overridden?"
print(s)
print(d)
}
corrected example
class Ref: CustomStringConvertible {
var string: String
init(_ string: String) {
self.string = string
}
public var description: String {
"\(ObjectIdentifier(self)): " + string
}
}
struct Val: Equatable, Hashable {
var int: Int = 0
let ref: Ref
static func == (a: Self, b: Self) -> Bool {
a.int == b.int && a.ref.string == b.ref.string
}
func hash(into hasher: inout Hasher) {
hasher.combine(int)
hasher.combine(ref.string)
}
}
func test() {
let helloRef = Ref("hello")
let worldRef = Ref("world")
let hello = Val(ref: helloRef)
let world = Val(ref: worldRef)
var s: Set<Val> = [hello, world]
var d: [Val: String] = [hello: "hello value", world: "world value"]
print(s)
print(d)
helloRef.string = "world"
print(s)
print(d)
// thanks @lorentey for pointing out that the check is triggered upon resizing.
// is there an explicit way to trigger the check without resizing?
let newKeys = (1...1000).map { _ in Val(ref: Ref(UUID().uuidString)) }
newKeys.forEach {
s.insert($0) // Fatal error: Duplicate elements of type 'K' were found in a Set.
d[$0] = "XXX" // Fatal error: Duplicate keys of type 'K' were found in a Dictionary.
}
}
we can ask developers: "please don't do that". but mistakes happen and it is too easy to shoot yourself in the foot here without realising. one possible remedy would be to have a debug switch / environment variable, when activated all instances where Set elements / dictionary keys have reference semantics will trap. i believe we should do this.
however, is it possible to address this issue at compile time? Can we only allow "ValueType" types (a special pseudo protocol Âą) to be used as Set elements / Dictionary keys?
Âą protocol ValueType {} // a pseudo protocol
Int, Double, String, etc - implicitly conforms to ValueType
struct PureStruct { // implicitly conform to ValueType as every field are ValueType
let v: Int
let d: Double
}
var dict: [PureStruct: Int] // possible
var s: Set<PureStruct> // possible
(Hashable conformance is also needed here, not showing it to not pollute the example)
struct ImpureStruct {
let v: Int
let c: SomeRefType
}
class SomeClass {
...
}
var dict: [ImpureStruct: Int] // error: Dictionary keys must be ValueType
var s: Set<ImpureStruct> // error: Set elements must be ValueType
var dict: [SomeClass: Int] // error: Dictionary keys must be ValueType
var s: Set<SomeClass> // error: Set elements must be ValueType
extension ImpureStruct: ValueType {
// explicit (or implicit?) COW implementation. not shown
}
extension SomeClass: ValueType {
// explicit (or implicit?) COW implementation. not shown
}
var dict: [ImpureStruct: Int] // now possible
var s: Set<ImpureStruct> // now possible
var dict: [SomeClass: Int] // now possible
var s: Set<SomeClass> // now possible
with this change it won't be possible to shoot yourself into the foot and ruin Set/Dictionary invariants. it would still be possible to use Reference types (or value types containing values with reference semantics) as Set elements and Dictionary keys, just those of those who explicitly opt-in to have "ValueType" semantics, and whenever the references are mutated the COW machinery will kick it and leave the Set/Dictionary values intact.
thoughts?
(original example that invalidates Dictionary/Set invariants corrected above)