# Typed Collections with Self Types in Objective-C.

The latest versions of the Clang compiler extend the Objective-C language with related return types, which allow a limited form of covariance to be expressed. Methods with certain names (alloc, init, etc.) are inferred to return an object of the instance type for the receiver; other methods can participate in this covariance by using the instancetype keyword for the return type annotation.

Typically, this feature is used for convenience constructors which would previously have returned id. However, we can also use it to encode statically-typed collections without full-blown generics.1

## Decorating Types with Protocols

If Objective-C had parametric polymorphism (that is, the ability to abstract over types), then a simple typesafe collection would be trivial:

 1 2 3 4  @protocol OrderedCollection[V] - (V)at:(NSUInteger)index; - (void)put:(V)object; @end

With instancetype, we support a subset of parametric polymorphism: that is, we can abstract over one type (the type of an instance of the implementing class), and we are limited to referring to this type in method return types.2 So, we can approximate something rather close, but slightly less safe and precise:

 1 2 3 4  @protocol OrderedCollection - (instancetype)at:(NSUInteger)index; - (void)put:(id)object; @end

Since we are limited to abstracting over the type of self, the static type of any such collection must actually be the type of its elements decorated by the <OrderedCollection> protocol. So, a collection of strings statically be understood to be a single string, decorated with collection methods:

 1 2 3  NSString *strings = ...; [strings put:@"hello,"]; [strings put:@"world!"];

## Higher Order Messaging

The fact that the static type of such a collection is the product of the type of its elements and a collection trait gives rise serendipitously to the applicability of higher-order-messaging, or HOM. For instance, what does it mean if you send NSString-messages to an object NSString <OrderedCollection>*? It makes sense to treat the collection as a $$\textbf{Functor}$$ and map the message over its elements:

 1 2 3 4 5  for (NSString *upperString in [strings.uppercaseString substringFromIndex:1]) NSLog(@"%@", upperString); // => ELLO, // => ORLD!

## An Implementation

We’ll implement covariant protocols <OrderedCollection, MapCollection>.

### The collection interfaces

 1 2 3 4 5 6 7 8 9  @protocol OrderedCollection - (instancetype)at:(NSUInteger)index; - (void)put:(id)object; @end @protocol MapCollection - (instancetype)at:(id)key; - (void)put:(id)object at:(id)key; @end

### Collection Proxies

We will use proxy objects to implement both the HOM and the checked collection accessors. First, we start with an abstract base CollectionProxy class, in terms of which proxies for both arrays and dictionaries will be expressed:

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159  @interface CollectionProxy : NSObject @property (strong) id target; @property (assign) class elementClass; - (id)initWithTarget:(id)target; + (Class)collectionClass; // Subclasses will provide a technique for mapping an element in one // collection to a new element in another. - (void)appendMappedObject:(id)mapped fromObject:(id)original toBuffer:(id)buffer; // Subclasses may wish to map over an object derivable from object // given in fast enumeration. For instance, dictionaries map over // values, rather than keys. - (id)redirectIteration:(id)object; @end @implementation CollectionProxy @synthesize target, elementClass; - (id)initWithTarget:(id)aTarget { if ((self = [super init])) target = aTarget; return self; } - (id)init { return [self initWithTarget:[self.class.collectionClass new]]; } - (NSMethodSignature *)methodSignatureForSelector:(SEL)sel { if ([self.class.collectionClass instancesRespondToSelector:sel]) return [self.class.collectionClass instanceMethodSignatureForSelector:sel]; return [self.elementClass instanceMethodSignatureForSelector:sel]; } - (BOOL)respondsToSelector:(SEL)aSelector { return [super respondsToSelector:aSelector] || [target respondsToSelector:aSelector] || [self.elementClass instancesRespondToSelector:aSelector]; } - (void)forwardInvocation:(NSInvocation *)invocation { // If the collection itself responds to this selector (like if // someone sent -count), we'll forward the message to it. if ([target respondsToSelector:invocation.selector]) return [invocation invokeWithTarget:target]; // If the invocation returns void, we still want to invoke it, but // we don't want to try to do anything with its results. BOOL returnsValue = strcmp("v", invocation.methodSignature.methodReturnType) != 0; id buffer = returnsValue ? [self.class.collectionClass new] : nil; for (id obj in target) { [invocation retainArguments]; [invocation invokeWithTarget:[self redirectIteration:obj]]; void *outPtr = NULL; if (returnsValue) { [invocation getReturnValue:&outPtr]; // We marshall the return value of the invocation back into our space. id mapped; if ((mapped = objc_unretainedObject(outPtr))) [self appendMappedObject:mapped fromObject:obj toBuffer:buffer]; } } if (returnsValue && [buffer count] > 0) { // Build up a new proxy of the same kind to return. CollectionProxy *proxy = [[self.class alloc] initWithTarget:buffer]; // We marshall the proxy out of our space and set it as the return // value of our invocation. invocation.returnValue = &(const void *){ objc_unretainedPointer(proxy) }; } } // Default behavior + (Class)collectionClass { return nil; } - (void)appendMappedObject:(id)mapped fromObject:(id)original toBuffer:(id)buffer {} - (id)redirectIteration:(id)object { return object; } @end @interface OrderedCollectionProxy : CollectionProxy @end @interface MapCollectionProxy : CollectionProxy @end @implementation OrderedCollectionProxy - (id)initWithTarget:(id)target { if ((self = [super initWithTarget:target]) && [target count]) self.elementClass = [[target lastObject] class]; return self; } + (Class)collectionClass { return [NSMutableArray class]; } - (void)appendMappedObject:(id)mapped fromObject:(id)original toBuffer:(id)buffer { [buffer addObject:mapped]; } - (void)put:(id)object { assert([object isKindOfClass:self.elementClass]); [self.target addObject:object]; } - (instancetype)at:(NSUInteger)index { return [self.target objectAtIndex:index]; } @end @implementation MapCollectionProxy - (id)initWithTarget:(id)target { if ((self = [super initWithTarget:target]) && [target count]) self.elementClass = [[target allValues].lastObject class]; return self; } + (Class)collectionClass { return [NSMutableDictionary class]; } - (void)appendMappedObject:(id)mapped fromObject:(id)key toBuffer:(id)buffer { [buffer setObject:mapped forKey:key]; } - (id)redirectIteration:(id)key { return [self.target objectForKey:key]; } - (void)put:(id)object at:(id)key { assert([object isKindOfClass:self.elementClass]); [self.target setObject:object forKey:key]; } - (instancetype)at:(id)key { return [self.target objectForKey:key]; } @end

### Collection Constructors

To construct a collection of some class, we send a message to that class with a covariant return type; unfortunately, we cannot decorate instancetype with any further protocols. So, ideally +orderedCollection would return instancetype <OrderedCollection>, but this is currently impossible; thus, you will have to provide the type decoration yourself.3

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20  @interface NSObject (Collections) + (instancetype)orderedCollection; + (instancetype)mapCollection; @end @implementation NSObject (Collections) + (instancetype)orderedCollection { CollectionProxy *proxy = [OrderedCollectionProxy new]; proxy.elementClass = self; return proxy } + (instancetype)mapCollection { CollectionProxy *proxy = [MapCollectionProxy new]; proxy.elementClass = self; return proxy; } @end

## See it in action

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16  NSURL *sites = (id)[NSURL mapCollection]; [sites put:[NSURL URLWithString:@"http://www.jonmsterling.com/"] at:@"jon"]; [sites put:[NSURL URLWithString:@"http://www.reddit.com/"] at:@"reddit"]; [sites put:[NSURL URLWithString:@"git://github.com/jonsterling/Foam.git"] at:"foam_repo"]; NSURL *jonsSite = [sites at:@"jon"]; // => http://www.jonmsterling.com/ NSString *schemes = (id)sites.scheme.uppercaseString; /* => { jon: "HTTP://", reddit: "HTTP://", foam_repo: "GIT://" } */

## Further Exercises

These HOMs do not correctly handle methods that return non-object types. It is definitely possible to write a more robust version that will box primitives appropriately, but not within the scope of this post. This will require further inspection of the method signature of the forwarded invocation.

1. Please duplicate rdar://10848469 if you want instancetype to be allowed in argument types.

2. In the context of protocol, instancetype refers to the conforming class; so, instancetype of NSString <OrderedCollection>* is NSString*.

3. Please duplicate rdar://10849187 if you want to be able to decorate instancetype with a protocol list.