There was an interesting question on StackOverflow this morning: Why doesn't NSOrderedSet inherit from NSSet? It's interesting because the reason is so easy to miss. I thought it would make a good blog post because it turned out to be a nice, real-life example of the Liskov substitution principle (herein abbreviated to LSP).
The (Winding) Answer
When I saw the question, the first thing I thought of was old mate Liskov. I opened up the documentation for
NSSet and went through every method, trying to find one that would have its contract violated by
NSOrderedSet. Every single method looked fine to me. They could all be implemented in
NSOrderedSet without any problems.
Upon closer inspection, there is one little method that violates the LSP in a very subtle way. That method is
mutableCopy. The return value of
mutableCopy would have to be an
NSMutableOrderedSet should inherit from
NSOrderedSet. It turns out that you can't have both.
Let me explain with some code. First, let's look at the correct behaviour of
NSSet* immutable = [NSSet set]; NSMutableSet* mutable = [immutable mutableCopy]; [mutable isKindOfClass:[NSSet class]]; // YES [mutable isKindOfClass:[NSMutableSet class]]; // YES
Now, let's pretend
NSOrderedSet does inherit from
NSMutableOrderedSet inherits from
NSOrderedSet as expected:
NSSet* immutable = [NSOrderedSet orderedSet]; NSMutableSet* mutable = [immutable mutableCopy]; [mutable isKindOfClass:[NSSet class]]; // YES [mutable isKindOfClass:[NSMutableSet class]]; // NO (problem)
The last line of the example above shows the problem. You wouldn't be able to pass an
NSOrderedSet into a function expecting an
NSSet because the behaviour is different. It's a violation of the LSP, which also makes it a backwards compatibility problem.
NSMutableOrderedSet inherited from
NSMutableSet instead? Then we get a different problem:
NSSet* immutable = [NSOrderedSet orderedSet]; NSMutableSet* mutable = [immutable mutableCopy]; [mutable isKindOfClass:[NSSet class]]; // YES [mutable isKindOfClass:[NSMutableSet class]]; // YES [mutable isKindOfClass:[NSOrderedSet class]]; // NO (problem)
NSMutableOrderedSet doesn't inherit from
NSOrderedSet. In Foundation, every mutable class inherits from the immutable class. To break this rule would be a bad design decision. Imagine if you had to allocate a new
NSArray every time you wanted to pass an
NSMutableArray into a function that takes immutable arrays as parameters. That would suck.
Update: Michael Tsai correctly points out another LSP violation. If
NSOrderedSet inherits from
isEqual: can not correctly compare an ordered set to an unordered set, for example:
NSSet* unordered = [NSSet setWithObjects:@"a", @"b", @"c", nil]; NSSet* ordered1 = [NSOrderedSet orderedSetWithObjects:@"a", @"b", @"c", nil]; NSSet* ordered2 = [NSOrderedSet orderedSetWithObjects:@"c", @"b", @"a", nil]; [ordered1 isEqual:ordered2]; //NO, because the order is different // Should this be NO because the order may be different, // or should it be YES for backwards compatibility, because // NSSet never used to care about order? [unordered isEqual:ordered1]; //problem
This all boils down to the fact that
NSMutableOrderedSet can't inherit from both
NSOrderedSet because Objective-C doesn't have multiple inheritance. The usual way to get around this is to make protocols for
NSOrderedSet, because then
NSMutableOrderedSet can implement both protocols.
I guess the Apple developers just thought it was simpler without the extra protocols, and I agree with them. The addition of the new protocols would cascade into the API of other areas. You would have to change method signatures to take
id<NSMutableSet> instead of
NSMutableSet*. It's just cleaner to use
[myOrderedSet set] when you really need to use the object as an
Funnily enough, choosing not to inherit from
NSSet has already caused at least one bug in Core Data. The error message is a dead giveaway:
intersectsSet:]: set argument is not an NSSet. Designing an API always involves trade-offs.