[SR-5633] isKnownUniquelyReferenced(_:) should optionally consider weak/unowned references

[lorentey]

Previous ID	SR-5633
Radar	None
Original Reporter	@lorentey
Type	Bug

Environment

Apple Swift version 4.0 (swiftlang-900.0.54.11 clang-900.0.31) Apple Swift version 4.0-dev (LLVM b5c7bf32a9, Clang 42fb83c55f, Swift 2e5817ebe1) Swift version 4.0-dev (LLVM 98499e0a26, Clang 337d432629, Swift cfb2a87dc5)

Additional Detail from JIRA

| | | |------------------|-----------------| |Votes | 0 | |Component/s | Standard Library | |Labels | Bug, Runtime | |Assignee | None | |Priority | Medium | md5: 3577d4724b9c773e5b7535af4a2c2326

is duplicated by:

• SR-8538 runtime: isKnownUniquelyReferenced should return false if there's any weak/unowned refs (or offer new function with those semantics)

Issue Description:

In Swift 4, the function isKnownUniquelyReferenced‌ returns false for any object that has (or previously had) a weak reference:

class Foo {}
var foo = Foo()
print(isKnownUniquelyReferenced(&foo)   // => true  (OK)
weak var bar: Foo? = foo
print(isKnownUniquelyReferenced(&foo)   // => false (Not OK)
bar = nil
print(isKnownUniquelyReferenced(&foo)   // => false (Extremely not OK)

This is a regression from Swift 3.1, where all three print statements printed true.

IsKnownUniquelyReferenced is documented to only count strong references; but even if for some reason it was changed to also count weak references, it should still report true in the third case, where the object only has a single outstanding reference left.

(That being said, a useful coding technique for COW-enabled tree collection types depends on the uniqueness checks ignoring weak/unowned refs, so ideally the Swift 3 behavior should stay.)

[lorentey]

I submitted a possible fix in PR #11362.

[3391d72f-a29f-4e23-ba0f-4b2ca3af6551]

Weak and unowned references can break algorithms depending on precisely what guarantees they need from uniquely-referenced. I expect something to change here in the future.

(For example, if your algorithm is "it's uniquely referenced therefore no other threads can interfere" then weak and unowned references can break your assumptions. Another thread can read a weak or unowned reference behind your back after the uniquely-referenced check.)

But this is fine for now.

[lorentey]

In the tree-based CoW collection use case I have in mind, storage references aren't visible outside the collection implementation, so the use of weak/unowned references is strictly controlled. I use them in the representation of indices to speed up operations. (E.g., in red-black trees, storing a path of node references inside the index leads to an algorithmic improvement to index(after🙂. The path itself can use unowned(unsafe) references, but for index validation, I also need to include an unowned or weak reference to the root node, along with a mutation counter.)

Indices are special because their use generally† requires the running thread to already have a (strong) copy of the corresponding collection on hand – so a standalone weak ref stored in an index won't get read on its own, unless the weak root node ref in an index supplied to a collection method belongs to a completely different collection instance (in which case the index is invalid, and the resulting trap will nicely prevent any data race). The weak/unowned references in an index are used to speed up operations on a separate strong reference that the thread already has; they aren't used to create new strong references out of thin air.

_{† There are two exceptions: indices need to implement Comparable, and in the == and \< operators, two indices need to be compared without the help of the collection. I've sometimes implemented this by reading their weak root references, which indeed leads to races if the (unique) collection is also being mutated by its separate owner thread. (Thanks for pointing this out!) Thankfully, this is solvable by loosening index validation in this case, and comparing offsets or some other direct value instead.}

Obviously, all this is really subtle and fragile, perhaps even in the context of CoW implementations. However, the current behavior meshes really nicely with the collection model to allow this narrow use case to work, and it gives us considerable performance benefits for certain useful types of collections. If isUnique counted weak/unowned references, I think I'd need to use double indirection to save the technique. I don't yet know the performance impact of that, but I should probably look into it.

[3391d72f-a29f-4e23-ba0f-4b2ca3af6551]

"Not visible outside the implementation" also applies to the stdlib's current uses such as the Array implementation. We'll definitely preserve this capability somewhere. Perhaps we'll deprecate the current function and add new functions that are more explicit about which references they're checking.

[lorentey]

That sounds like an excellent change! 👍

[atrick]

Perhaps we'll deprecate the current function and add new functions that are more explicit about which references they're checking.

Good idea.

@gparker42 and @lorentey, this issue came up again with @weissi's realloc work. Should we have a runtime/stdlib radar for this and do something more sensible before the API is baked in?

[3391d72f-a29f-4e23-ba0f-4b2ca3af6551]

We can repurpose \rdar://problem/27070378\ Race: isUniquelyReferenced doesn't consider the weak refcount

[ole]

I arrived here via a link posted by @belkadan in a forum thread.

For what it's worth, I can't reproduce the behavior in the ticket description anymore. In Swift 5.2 and a current 5.3 beta (on macOS, tested with and without -O), all 3 print statements print "true":

class Foo {}
var foo = Foo()
print(isKnownUniquelyReferenced(&foo))   // => true
weak var bar: Foo? = foo
print(isKnownUniquelyReferenced(&foo))   // => true
bar = nil
print(isKnownUniquelyReferenced(&foo))   // => true

Whether that means the ticket should be closed, I don't know.

[lorentey]

The original issue was resolved in one of the Swift 4 releases! However, this item has pivoted into tracking the addition of new API that allows selecting the desired behavior, and we haven't done that yet.

Detecting outstanding unowned references may not be feasible to implement at this point, but I believe weak references are still detectable.

[ole]

@lorentey OK, thanks.