How safe are swift collections when used with invalidated iterators / indices?

Question

I'm not seeing a lot of info in the swift stdlib reference. For example, Dictionary says certain methods (like remove) will invalidate indices, but that's it.

For a language to call itself "safe", it needs a solution to the classic C++ footguns:

1. get pointer to element in a vector, then add more elements (pointer is now invalidated), now use pointer, crash

2. start iterating through a collection. while iterating, remove some elements (either before or after the current iterator position). continue iterating, crash.

(edit: in c++, you're lucky to crash - worse case is memory corruption)

I believe 1 is solved by swift because if a collection stores classes, taking a reference (e.g. strong pointer) to an element will increase the refcount. However, I don't know the answer for 2.

It would be super useful if there was a comparison of footguns in c++ that are/are not solved by swift.

EDIT, due to Robs answer:

It does appear that there's some undocumented snapshot-like behavior going on with Dictionary and/or for loops. The iteration creates a snapshot / hidden copy of it when it starts.

Which gives me both a big "WAT" and "cool, that's sort of safe, I guess", and "how expensive is this copy?".

I don't see this documented either in Generator or in for-loop.

The below code prints two logical snapshots of the dictionary. The first snapshot is userInfo as it was at the start of the iteration loop, and does not reflect any modifications made during the loop.

var userInfo: [String: String] = [
    "first_name" : "Andrei",
    "last_name" : "Puni",
    "job_title" : "Mad scientist"
]

userInfo["added_one"] = "1"  // can modify because it's var

print("first snapshot:")
var hijacked = false
for (key, value) in userInfo {
    if !hijacked {
        userInfo["added_two"] = "2"  // doesn't error     
        userInfo.removeValueForKey("first_name")  // doesn't error
        hijacked = true
    }
    print("- \(key): \(value)")
}

userInfo["added_three"] = "3" // modify again

print("final snapshot:")
for (key, value) in userInfo {
    print("- \(key): \(value)")
}

Answer 1

As you say, #1 is not an issue. You do not have a pointer to the object in Swift. You either have its value or a reference to it. If you have its value, then it's a copy. If you have a reference, then it's protected. So there's no issue here.

But let's consider the second and experiment, be surprised, and then stop being surprised.

var xs = [1,2,3,4]

for x in xs { // (1)
    if x == 2 {
        xs.removeAll() // (2)
    }
    print(x) // Prints "1\n2\n3\n\4\n"
}

xs // [] (3)

Wait, how does it print all the values when we blow away the values at (2). We are very surprised now.

But we shouldn't be. Swift arrays are values. The xs at (1) is a value. Nothing can ever change it. It's not "a pointer to memory that includes an array structure that contains 4 elements." It's the value [1,2,3,4]. At (2), we don't "remove all elements from the thing xs pointed to." We take the thing xs is, create an array that results if you remove all the elements (that would be [] in all cases), and then assign that new array to xs. Nothing bad happens.

So what does the documentation mean by "invalidates all indices?" It means exactly that. If we generated indices, they're no good anymore. Let's see:

var xs = [1,2,3,4]

for i in xs.indices {
    if i == 2 {
        xs.removeAll()
    }
    print(xs[i]) // Prints "1\n2\n" and then CRASH!!!
}

Once xs.removeAll() is called, there's no promise that the old result of xs.indices means anything anymore. You are not permitted to use those indices safely against the collection they came from.

"Invalidates indices" in Swift is not the same as C++'s "invalidates iterators." I'd call that pretty safe, except the fact that using collection indices is always a bit dangerous and so you should avoid indexing collections when you can help it; iterate them instead. Even if you need the indexes for some reason, use enumerate to get them without creating any of the danger of indexing.

(Side note, dict["key"] is not indexing into dict. Dictionaries are a little confusing because their key is not their index. Accessing dictionaries by their DictionaryIndex index is just as dangerous as accessing arrays by their Int index.)

Note also that the above doesn't apply to NSArray. If you modify NSArray while iterating it, you'll get a "mutated collection while iterating" error. I'm only discussing Swift data types.

---

EDIT: for-in is very explicit in how it works:

The generate() method is called on the collection expression to obtain a value of a generator type—that is, a type that conforms to the GeneratorType protocol. The program begins executing a loop by calling the next() method on the stream. If the value returned is not None, it is assigned to the item pattern, the program executes the statements, and then continues execution at the beginning of the loop. Otherwise, the program does not perform assignment or execute the statements, and it is finished executing the for-in statement.

The returned Generator is a struct and contains a collection value. You would not expect any changes to some other value to modify its behavior. Remember: [1,2,3] is no different than 4. They're both values. When you assign them, they make copies. So when you create a Generator over a collection value, you're going to snapshot that value, just like if I created a Generator over the number 4. (This raises an interesting problem, because Generators aren't really values, and so really shouldn't be structs. They should be classes. Swift stdlib has been fixing that. See the new AnyGenerator for instance. But they still contain an array value, and you would never expect changes to some other array value to impact them.)

See also "Structures and Enumerations Are Value Types" which goes into more detail on the importance of value types in Swift. Arrays are just structs.

Yes, that means there's logically copying. Swift has many optimizations to minimize actual copying when it's not needed. In your case, when you mutate the dictionary while it's being iterated, that will force a copy to happen. Mutation is cheap if you're the only consumer of a particular value's backing storage. But it's O(n) if you're not. (This is determined by the Swift builtin isUniquelyReferenced().) Long story short: Swift Collections are Copy-on-Write, and simply passing an array does not cause real memory to be allocated or copied.

You don't get COW for free. Your own structs are not COW. It's something that Swift does in stdlib. (See Mike Ash's great discussion of how you would recreate it.) Passing your own custom structs causes real copies to happen. That said, the majority of the memory in most structs is stored in collections, and those collections are COW, so the cost of copying structs is usually pretty small.

The book doesn't spend a lot of time drilling into value types in Swift (it explains it all; it just doesn't keep saying "hey, and this is what that implies"). On the other hand, it was the constant topic at WWDC. You may be interested particularly in Building Better Apps with Value Types in Swift which is all about this topic. I believe Swift in Practice also discussed it.

---

EDIT2:

@KarlP raises an interesting point in the comments below, and it's worth addressing. None of the value-safety promises we're discussing are related to for-in. They're based on Array. for-in makes no promises at all about what would happen if you mutated a collection while it is being iterated. That wouldn't even be meaningful. for-in doesn't "iterate over collections," it calls next() on Generators. So if your Generator becomes undefined if the collection is changed, then for-in will blow up because the Generator blew up.

That means that the following might be unsafe, depending on how strictly you read the spec:

func nukeFromOrbit<C: RangeReplaceableCollectionType>(var xs: C) {
    var hijack = true
    for x in xs {
        if hijack {
            xs.removeAll()
            hijack = false
        }
        print(x)
    }
}

And the compiler won't help you here. It'll work fine for all of the Swift collections. But if calling next() after mutation for your collection is undefined behavior, then this is undefined behavior.

My opinion is that it would be poor Swift to make a collection that allows its Generator to become undefined in this case. You could even argue that you've broken the Generator spec if you do (it offers no UB "out" unless the generator has been copied or has returned nil). So you could argue that the above code is totally within spec and your generator is broken. Those arguments tend to be a bit messy with a "spec" like Swift's which doesn't dive into all the corner cases.

Does this mean you can write unsafe code in Swift without getting a clear warning? Absolutely. But in the many cases that commonly cause real-world bugs, Swift's built-in behavior does the right thing. And in that, it is safer than some other options.