Proposal: Weak Native Swift Containers


(Riley Testut) #1

In multiple places in my projects, I essentially recreate the “multiple observer” pattern used by NSNotificationCenter. Originally this was implemented by simply maintaining an array of observers, and adding to/removing from it as necessary. However, this had the unintended side effect of maintaining a strong reference to the observers, which in many cases is undesirable (for the same reasons it’s common to mark delegate properties as weak).

Now, I’m using a private NSHashTable instance, and expose the observers as public API by creating a public computed property which essentially returns an array derived from the NSHashTable like so:

public var receivers: [GameControllerReceiverType] {
    // self.privateReceivers.allObjects as! [GameControllerReceiverType] crashes Swift :(
    return self.privateReceivers.allObjects.map({ $0 as! GameControllerReceiverType })
}

This workaround works, but is undesirable for a number of reasons. Most notably:

• NSHashTable is not a native Swift collection, and is also not in the Foundation Swift port, so it is not portable to other systems.
• It also has not yet been annotated with generics, so it loses the nice type safety of other Swift collections. Because of this, I have to map the objects to the appropriate type before returning the allObjects array, which runs in O(n) time instead of O(1).
• It’s repetitive. For every type that wants to implement this pattern, they must maintain both a public computed method and a private NSHashTable instance. This gets worse when this should be part of a protocol; there’s no way to enforce that each type conforming to it has a NSHashTable, while also keeping that information private from the consumer of the API.

I think native swift collections with support for weak references for their contents would be very useful, and in more places than just listed above. I don’t think Array could be easily extended to support it (what happens if a value is released? does everything shift down? do they keep their indices?), but Set and Dictionary (where the keys and/or values could be weak, akin to NSMapTable) would be good candidates IMO.

Thoughts?


(Dmitri Gribenko) #2

Seems like an interesting direction to me, using value types as keys and
weak references in a dictionary-like data structure seems like a fequent
use case. A proposal in this area should include not just the API, but
also a discussion of the implementation strategy.

Dmitri

···

On Thu, Dec 10, 2015 at 2:55 PM, Riley Testut via swift-evolution < swift-evolution@swift.org> wrote:

I think native swift collections with support for weak references for
their contents would be very useful, and in more places than just listed
above. I don’t think Array could be easily extended to support it (what
happens if a value is released? does everything shift down? do they keep
their indices?), but Set and Dictionary (where the keys and/or values could
be weak, akin to NSMapTable) would be good candidates IMO.

--
main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if
(j){printf("%d\n",i);}}} /*Dmitri Gribenko <gribozavr@gmail.com>*/


(Greg Parker) #3

Containers of weak references are valuable, but I suspect they will need to be completely distinct from Array and Set and Dictionary. The problem is that a weak reference can become nil at any time. This subverts the value semantics of Swift's current containers and defeats assumptions that typical container algorithms make. (For example, a typical sorting algorithm assumes that comparison results between two elements are consistent over time, but that isn't true if a weak reference disappears while a sort is in progress.)

Note that Foundation does not support weak references in NSDictionary or NSSet.

···

On Dec 10, 2015, at 2:55 PM, Riley Testut via swift-evolution <swift-evolution@swift.org> wrote:

I think native swift collections with support for weak references for their contents would be very useful, and in more places than just listed above. I don’t think Array could be easily extended to support it (what happens if a value is released? does everything shift down? do they keep their indices?), but Set and Dictionary (where the keys and/or values could be weak, akin to NSMapTable) would be good candidates IMO.

--
Greg Parker gparker@apple.com Runtime Wrangler


(Tommy van der Vorst) #4

Hi Riley,

Have you tried using an array of structs that in turn hold weak references to your objects? Something like this should work:

public class Weak<T: AnyObject>: NSObject {
  public private(set) weak var value: T?

  public init(_ value: T?) {
    self.value = value
  }
}

let weakFoo: [Weak<Foo>] = [Weak<Foo>(foo), ...]

Comes with the overhead of one extra object instantiated per element, but perhaps this is acceptable for your use case.

/T

···

Op 10 dec. 2015, om 23:55 heeft Riley Testut via swift-evolution <swift-evolution@swift.org> het volgende geschreven:

In multiple places in my projects, I essentially recreate the “multiple observer” pattern used by NSNotificationCenter. Originally this was implemented by simply maintaining an array of observers, and adding to/removing from it as necessary. However, this had the unintended side effect of maintaining a strong reference to the observers, which in many cases is undesirable (for the same reasons it’s common to mark delegate properties as weak).

Now, I’m using a private NSHashTable instance, and expose the observers as public API by creating a public computed property which essentially returns an array derived from the NSHashTable like so:

public var receivers: [GameControllerReceiverType] {
    // self.privateReceivers.allObjects as! [GameControllerReceiverType] crashes Swift :frowning:
    return self.privateReceivers.allObjects.map({ $0 as! GameControllerReceiverType })
}

This workaround works, but is undesirable for a number of reasons. Most notably:

• NSHashTable is not a native Swift collection, and is also not in the Foundation Swift port, so it is not portable to other systems.
• It also has not yet been annotated with generics, so it loses the nice type safety of other Swift collections. Because of this, I have to map the objects to the appropriate type before returning the allObjects array, which runs in O(n) time instead of O(1).
• It’s repetitive. For every type that wants to implement this pattern, they must maintain both a public computed method and a private NSHashTable instance. This gets worse when this should be part of a protocol; there’s no way to enforce that each type conforming to it has a NSHashTable, while also keeping that information private from the consumer of the API.

I think native swift collections with support for weak references for their contents would be very useful, and in more places than just listed above. I don’t think Array could be easily extended to support it (what happens if a value is released? does everything shift down? do they keep their indices?), but Set and Dictionary (where the keys and/or values could be weak, akin to NSMapTable) would be good candidates IMO.

Thoughts?

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Riley Testut) #5

Using box types solves the portability problems, but it still means O(n) access for clients who want to access the non-boxed values directly. Additionally, these objects aren’t automatically removed from the collection when their values are nil-ed out, which is unfortunate.

Side note: this is the route I originally tried to take, but unfortunately the Swift doesn’t work well with weak references to protocol types…

···

On Dec 10, 2015, at 3:01 PM, Tommy van der Vorst <tommy@pixelspark.nl> wrote:

Hi Riley,

Have you tried using an array of structs that in turn hold weak references to your objects? Something like this should work:

public class Weak<T: AnyObject>: NSObject {
  public private(set) weak var value: T?

  public init(_ value: T?) {
    self.value = value
  }
}

let weakFoo: [Weak<Foo>] = [Weak<Foo>(foo), ...]

Comes with the overhead of one extra object instantiated per element, but perhaps this is acceptable for your use case.

/T

Op 10 dec. 2015, om 23:55 heeft Riley Testut via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> het volgende geschreven:

In multiple places in my projects, I essentially recreate the “multiple observer” pattern used by NSNotificationCenter. Originally this was implemented by simply maintaining an array of observers, and adding to/removing from it as necessary. However, this had the unintended side effect of maintaining a strong reference to the observers, which in many cases is undesirable (for the same reasons it’s common to mark delegate properties as weak).

Now, I’m using a private NSHashTable instance, and expose the observers as public API by creating a public computed property which essentially returns an array derived from the NSHashTable like so:

public var receivers: [GameControllerReceiverType] {
    // self.privateReceivers.allObjects as! [GameControllerReceiverType] crashes Swift :(
    return self.privateReceivers.allObjects.map({ $0 as! GameControllerReceiverType })
}

This workaround works, but is undesirable for a number of reasons. Most notably:

• NSHashTable is not a native Swift collection, and is also not in the Foundation Swift port, so it is not portable to other systems.
• It also has not yet been annotated with generics, so it loses the nice type safety of other Swift collections. Because of this, I have to map the objects to the appropriate type before returning the allObjects array, which runs in O(n) time instead of O(1).
• It’s repetitive. For every type that wants to implement this pattern, they must maintain both a public computed method and a private NSHashTable instance. This gets worse when this should be part of a protocol; there’s no way to enforce that each type conforming to it has a NSHashTable, while also keeping that information private from the consumer of the API.

I think native swift collections with support for weak references for their contents would be very useful, and in more places than just listed above. I don’t think Array could be easily extended to support it (what happens if a value is released? does everything shift down? do they keep their indices?), but Set and Dictionary (where the keys and/or values could be weak, akin to NSMapTable) would be good candidates IMO.

Thoughts?

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution


(John McCall) #6

Using box types solves the portability problems, but it still means O(n) access for clients who want to access the non-boxed values directly. Additionally, these objects aren’t automatically removed from the collection when their values are nil-ed out, which is unfortunate.

Side note: this is the route I originally tried to take, but unfortunately the Swift doesn’t work well with weak references to protocol types…

Really? Please file a bug about this; I’ve been working in this area recently.

(Or just point out the radar number if you filed one there already.)

John.

···

On Dec 10, 2015, at 3:31 PM, Riley Testut via swift-evolution <swift-evolution@swift.org> wrote:

On Dec 10, 2015, at 3:01 PM, Tommy van der Vorst <tommy@pixelspark.nl <mailto:tommy@pixelspark.nl>> wrote:

Hi Riley,

Have you tried using an array of structs that in turn hold weak references to your objects? Something like this should work:

public class Weak<T: AnyObject>: NSObject {
  public private(set) weak var value: T?

  public init(_ value: T?) {
    self.value = value
  }
}

let weakFoo: [Weak<Foo>] = [Weak<Foo>(foo), ...]

Comes with the overhead of one extra object instantiated per element, but perhaps this is acceptable for your use case.

/T

Op 10 dec. 2015, om 23:55 heeft Riley Testut via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> het volgende geschreven:

In multiple places in my projects, I essentially recreate the “multiple observer” pattern used by NSNotificationCenter. Originally this was implemented by simply maintaining an array of observers, and adding to/removing from it as necessary. However, this had the unintended side effect of maintaining a strong reference to the observers, which in many cases is undesirable (for the same reasons it’s common to mark delegate properties as weak).

Now, I’m using a private NSHashTable instance, and expose the observers as public API by creating a public computed property which essentially returns an array derived from the NSHashTable like so:

public var receivers: [GameControllerReceiverType] {
    // self.privateReceivers.allObjects as! [GameControllerReceiverType] crashes Swift :frowning:
    return self.privateReceivers.allObjects.map({ $0 as! GameControllerReceiverType })
}

This workaround works, but is undesirable for a number of reasons. Most notably:

• NSHashTable is not a native Swift collection, and is also not in the Foundation Swift port, so it is not portable to other systems.
• It also has not yet been annotated with generics, so it loses the nice type safety of other Swift collections. Because of this, I have to map the objects to the appropriate type before returning the allObjects array, which runs in O(n) time instead of O(1).
• It’s repetitive. For every type that wants to implement this pattern, they must maintain both a public computed method and a private NSHashTable instance. This gets worse when this should be part of a protocol; there’s no way to enforce that each type conforming to it has a NSHashTable, while also keeping that information private from the consumer of the API.

I think native swift collections with support for weak references for their contents would be very useful, and in more places than just listed above. I don’t think Array could be easily extended to support it (what happens if a value is released? does everything shift down? do they keep their indices?), but Set and Dictionary (where the keys and/or values could be weak, akin to NSMapTable) would be good candidates IMO.

Thoughts?

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution


(Riley Testut) #7

I'm not sure how NSHashTable and NSMapTable are implemented under the hood, but assumedly the native Swift implementation would be somewhat similar. I'm not opposed to figuring out the best way to accomplish this, but if it's already been implemented and works well, no use going through all that work again :-)

I agree they should be distinct types, but I'm debating how explicit that should be to the user. On one hand, there could be a "WeakSet" or "WeakDictionary" type, that is completely separate, explicit, and public, or we could go a more "magical" route and have a private implementation of Set/Dictionary that conforms to all the same protocols as Set/Dictionary (similar to the different implementations of Array depending on what the backing store is), and is used when a weak set is needed.

Or, it could be in the middle, and we could convert a Set/Dictionary into a weak variant, such as by accessing a ".weak" property (akin to the ".lazy" property implemented by CollectionType). I think all these solutions have their pros and cons, and it would be worth discussing the best way to approach this problem.

···

On Dec 10, 2015, at 4:53 PM, Greg Parker <gparker@apple.com> wrote:

On Dec 10, 2015, at 2:55 PM, Riley Testut via swift-evolution <swift-evolution@swift.org> wrote:

I think native swift collections with support for weak references for their contents would be very useful, and in more places than just listed above. I don’t think Array could be easily extended to support it (what happens if a value is released? does everything shift down? do they keep their indices?), but Set and Dictionary (where the keys and/or values could be weak, akin to NSMapTable) would be good candidates IMO.

Containers of weak references are valuable, but I suspect they will need to be completely distinct from Array and Set and Dictionary. The problem is that a weak reference can become nil at any time. This subverts the value semantics of Swift's current containers and defeats assumptions that typical container algorithms make. (For example, a typical sorting algorithm assumes that comparison results between two elements are consistent over time, but that isn't true if a weak reference disappears while a sort is in progress.)

Note that Foundation does not support weak references in NSDictionary or NSSet.

--
Greg Parker gparker@apple.com Runtime Wrangler


(Chris Lattner) #8

It should work with protocols, but they must be class bound.

-Chris

···

On Dec 10, 2015, at 4:08 PM, John McCall via swift-evolution <swift-evolution@swift.org> wrote:

On Dec 10, 2015, at 3:31 PM, Riley Testut via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:
Using box types solves the portability problems, but it still means O(n) access for clients who want to access the non-boxed values directly. Additionally, these objects aren’t automatically removed from the collection when their values are nil-ed out, which is unfortunate.

Side note: this is the route I originally tried to take, but unfortunately the Swift doesn’t work well with weak references to protocol types…

Really? Please file a bug about this; I’ve been working in this area recently.


(Riley Testut) #9

FWIW, I don’t think it was directly tied to being unable to support weak references to protocol types, but rather was a side-effect (I know I had to change it from “protocol TestProtocol: class” to “protocol TestProtocol: AnyObject” to satisfy some of the compiler errors, but doing that still preventing me from using the protocol directly in certain situations). However, I can no longer reproduce the issue, so it’s possible it was a bug in Swift that has been subsequently fixed.

···

On Dec 10, 2015, at 5:27 PM, Chris Lattner <clattner@apple.com> wrote:

On Dec 10, 2015, at 4:08 PM, John McCall via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

On Dec 10, 2015, at 3:31 PM, Riley Testut via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:
Using box types solves the portability problems, but it still means O(n) access for clients who want to access the non-boxed values directly. Additionally, these objects aren’t automatically removed from the collection when their values are nil-ed out, which is unfortunate.

Side note: this is the route I originally tried to take, but unfortunately the Swift doesn’t work well with weak references to protocol types…

Really? Please file a bug about this; I’ve been working in this area recently.

It should work with protocols, but they must be class bound.

-Chris