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 <OrderedCollection> *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 <NSFastEnumeration>
- (instancetype)at:(NSUInteger)index;
- (void)put:(id)object;
@end

@protocol MapCollection <NSFastEnumeration>
- (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 <MapCollection> *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 <MapCollection> *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.

Want to comment?

I’m @jonsterling on Twitter and App.net.