NSBlog

Cocoa Unbound

Sat, 04 Sep 2010 21:51:00 GMT

Cocoa Unbound

My recent whining about ridiculous moderation policies on cocoa-dev has borne fruit! Brent Simmons has graciously created cocoa-unbound, a group dedicated to Cocoa discussion but without the foolishness. I've already joined, and I encourage you to do so as well. A well-trafficked mailing list where we can talk about Mac programming without minions of the Mothership getting in our way will be a wonderful resource to have.

Friday Q&A 2010-08-27: Defensive Programming in Cocoa

Fri, 27 Aug 2010 15:19:00 GMT

Friday Q&A 2010-08-27: Defensive Programming in Cocoa

Welcome back to another word-laden edition of Friday Q&A. About a year ago, I wrote a post on defensive programming. That post covered defensive programming in a general sense, and Scott Gould has requested that I write one specific to various standard Cocoa practices, which is what I will be talking about today.

Recap
Defensive coding essentially boils down to constantly asking yourself, "what if it fails?" and coding appropriately. Your code's response to failure can be ranked:

Corrupt/delete user data
Crash/freeze
Fail silently
Display an error
Work around the failure

The goal is to get as far down the list as is possible and reasonable.

When it comes to defensive Cocoa programming, a lot of failures are really just unanticipated changes. What happens if something makes a subclass of your class? What happens if your superclass's dealloc implementation changes? What happens if the behavior of an object changes but remains within the API contract?

Initializers
What better place to start than at the beginning of an object's lifecycle?

I wrote a full post on implementing Cocoa initializers, so I won't go into too much detail here. The main things you need to do to write a defensive initializer are to always ensure that your superclass's initializer gets called (even if it doesn't do anything, it could start doing something later), always assign self to the result, and always check the result for nil. Thus:

    - (id)init
    {
        self = [super init];
        if(self)
        {
            // ... initialize instance variables here
        }
        return self;
    }

Deallocation
When your object is destroyed, it must clean up after itself. Naturally, you need to be careful when doing this.

First, always write your dealloc implementation to tolerate an uninitialized or partially initialized object. It's possible that your initializer, or a superclass initializer, will encounter an error and decide to destroy your object before it's fully formed, and your code should tolerate this. You can take advantage of the fact that Objective-C objects start out zero-filled. For example:

    - (void)dealloc
    {
        // if statement guards against uninitialized object
        if(someStructPointer)
            [someStructPointer->object release];
        
        [super dealloc];
    }

Note that most of the time, you can simply take advantage of the fact that messages to nil do nothing, and not have to write any extra code to handle the case of an uninitialized object.

Setters
The same thing goes for setters, especially those which are overridden from a superclass. The superclass my call the setter with nil to destroy an object rather than directly using release. Always write your code to tolerate this. For example:

    - (void)setFoo: (id)newFoo
    {
        // make sure we don't do something bad if newFoo is nil!
        if(newFoo)
            [[NSNotificationCenter defaultCenter]
             addObserver: self
             selector: @selector(_fooChanged)
             name: FooDidChangeNotification
             object: newFoo];
        [super setFoo: newFoo];
    }

You should always do this even if you're sure it will never get called with nil. It's just good practice, and doesn't hurt.

+initialize
Just as you have to code defensively when initializing your objects, so do you have to for initializing your classes.

The +initialize method is extremely useful for doing basic setup of class-wide data. It's invoked automatically by the runtime the first time any message (such as alloc) is sent to your class.

For example, say you need a global dictionary to hold certain items:

    static NSMutableDictionary *gDictionary;
    
    + (void)initialize
    {
        gDictionary = [[NSMutableDictionary alloc] init];
    }

However, this is dangerous and wrong! The trouble occurs if there's a subclass which doesn't implement +initialize. The runtime still sends the message, and so it ends up invoking your version instead. Suddenly you've leaked the old dictionary and lost all of the data in it. Whoops.

The fix is simple: just check the identify of self before you do your initialization.

    static NSMutableDictionary *gDictionary;
    
    + (void)initialize
    {
        if(self == [MyClass class])
            gDictionary = [[NSMutableDictionary alloc] init];
    }

As a general rule, the first line of any +initialize implementation should always be a check of self to ensure that it's the correct class.

You might be thinking that you didn't write any subclasses and don't plan to, so you don't need to do this. There are two problems with that approach.

First is the obvious one that you might simply be wrong about your future plans. If in a year you change your mind and decide that you do need a subclass, you don't want this code to suddenly break in mysterious and hard-to-debug ways.

Less obvious is the fact that subclasses of your class can be created dynamically at runtime. This is done by Cocoa's key-value observing system, a key component of Cocoa bindings. These dynamic subclasses still cause +initialize to execute, so be prepared for it.

Memory Management
If you have an object pointer instance variable, never assign to that variable except in init, dealloc, and a setter method. In other words, don't write code that does this directly:

    [myObjIvar release];
    myObjIvar = [[self makeNewObj] retain];

If you write that code directly, it's easy to forget a retain or release and cause havoc. It makes your code less dangerous and easier to understand to call through to a setter:

    [self setMyObjIvar: [self makeNewObj]];

That way all of the memory management code is contained in just one place, instead of being scattered all about.

On the subject of setters, if you're writing your own setter, remember that you must either do an if check to make sure that the object you have is genuinely new, or you must do a retain (or copy) before you do a release, to make your code robust against calling the setter with the same object as is already held in the variable. In other words, don't do this:

    - (void)setMyObjIvar: (id)obj
    {
        [myObjIvar release]; // could destroy obj!
        myObjIvar = [obj retain];
    }

Instead, either do this:

    - (void)setMyObjIvar: (id)obj
    {
        if(obj != myObjIvar)
        {
            [myObjIvar release];
            myObjIvar = [obj retain];
        }
    }

Or this:

    - (void)setMyObjIvar: (id)obj
    {
        [obj retain]; // or obj = [obj copy];
        [myObjIvar release];
        myObjIvar = obj;
    }

Which one is better is essentially a matter of taste.

Copying
Object copying is a source of horrors when it comes to subclassing Cocoa objects, due to the two different ways that exist to create a copy of an object in the top-level implementation of copyWithZone:.

The sane way to implement copyWithZone: is to either return [self retain] (only if the object is immutable) or to create a new instance of the object's class and populate it to hold the same values using accessors or direct instance variable access:

    - (id)copyWithZone: (NSZone *)zone
    {
        // note use of [self class] rather than MyClass
        // this is defensive programming against subclassing!
        MyClass *newObj = [[[self class] alloc] init];
        [newObj setFoo: _foo];
        [newObj setBar: _bar];
        return newObj;
    }

The completely insane way to implement copyWithZone: is to use the NSCopyObject function. This function allocates a new object of the same class and returns it. The problem is that it also performs a bitwise copy of all instance variables. These instance variables include things like pointers to objects. It does not retain them, merely copies their value.

Never, ever, ever use NSCopyObject. Easy, right? The problem is that Cocoa uses it, and if you ever subclass Cocoa objects, you have to be aware.

Even worse: you often can't count on the Cocoa implementation using one technique or another. It could use either one, and which one it uses could switch at any time. So if you ever subclass a Cocoa object that implements NSCopying, and you add instance variables, you need to write a copyWithZone: override that handles both cases correctly. Fortunately this is easier than it sounds.

First, let's examine the problem in more detail. Here's an example NSCell subclass:

    @interface MyCell : NSCell
    {
        NSString *_someString;
    }
    
    - (void)setSomeString: (NSString *)newString;
    
    @end

    @implementation MyCell
    
    - (void)setSomeString: (NSString *)newString
    {
        [newString retain];
        [_someString release];
        _someString = newString;
    }
    
    - (void)dealloc
    {
        [_someString release];
        [super dealloc];
    }
    
    @end

Now you write a bit of code that uses it:

    MyCell *cell = [[MyCell alloc] init];
    [cell setSomeString: string];
    MyCels *cell2 = [cell copy];
    [cell release];
    [cell2 release];

You run this and it crashes! Why?

The implementation of -[NSCell copyWithZone:] uses NSCopyObject. This means that it copies the _someString pointer, but does no memory management on it. You end up with two pointers to the string but only one of which is retained. They both get released in dealloc. Crash.

The solution is simple: override copyWithZone: and retain or copy the instance variable:

    - (id)copyWithZone: (NSZone *)zone
    {
        MyCell *newObj = [super copyWithZone: zone];
        [newObj->_someString retain];
        return newObj;
    }

This works, but is brittle. If the NSCell implementation changed to no longer call NSCopyObject, this implementation will fail, because newObj->_someString will be nil. It won't crash, but the copy won't be a proper copy either. And you can't just switch to using [newObj setSomeString: _someString] because that crashes the NSCopyObject case. We need code that works equally well for both.

The answer is to directly assign to the instance variable of the other object and do memory management at the same time, like so:

    - (id)copyWithZone: (NSZone *)zone
    {
        MyCell *newObj = [super copyWithZone: zone];
        newObj->_someString = [_someString retain];
        return newObj;
    }

You'll note that it works for both cases. For the sane case, it retains the string and puts the value into the new object's instance variable. For the NSCopyObject case, it overwrites the existing pointer with a new one, but without releasing the old one.

Note that NSCell is by far the most commonly subclassed class that conforms to NSCopying. If you ever subclass NSCell or one of its subclasses, you must implement copyWithZone:, and you must do it correctly using the above technique. Otherwise you leave yourself open to extremely mysterious crashes and corruption problems. I've been there, it's no fun.

Error Returns
A lot of Cocoa methods take NSError ** parameters to tell you why something went wrong. Always check the retun value from these methods! And always at least log the error if there is one.

Don't do this:

    NSString *string = [NSString stringWithContentsOfFile: path encoding: NSUTF8StringEncoding error: NULL];
    [self corruptImportantDataIfNil: string];

Instead, check string and use the error if it's nil. At the very least, use an assert to nicely stop the current operation rather than continuing with bad data:

    NSError *error;
    NSString *string = [NSString stringWithContentsOfFile: path encoding: NSUTF8StringEncoding error: &error];
    NSAssert(string, @"Could not load string, error: %@", error);
    [self corruptImportantDataIfNil: string];

If possible and reasonable, try to either fail gracefully (maybe try a different, backup source of data) or at least report the error to the user in the GUI and allow the program to continue executing normally.

Always at least check for failure and log the error. Even if subsequent code won't corrupt data in the error case, it's still much easier to figure out why your code isn't working if you can catch the failure as early as possible.

A Note on Checking Errors
This has been repeated in many other places, but bears another mention. Always check the return value of such a method, and not the NSError variable directly. For example, this is wrong:

    NSError *error = nil;
    NSString *string = [NSString stringWithContentsOfFile: path encoding: NSUTF8StringEncoding error: &error];
    NSAssert(!error, @"Could not load string, error: %@", error);

Apple reserves the right to fill your error variable with junk upon success. This is a stupid policy, but it's the policy which is there, so you must take it into account.

Weak References
The standard way to set up an NSTableView using a data source is to create an object to be the data source, implement the required methods, and then hook up the dataSource outlet of the table view. However, if you don't do anything else, this is actually a dangerous setup.

The problem is that the order of object destruction isn't defined. If your data source gets destroyed before the table view, the table view could potentially message the data source after it's been destroyed, causing your program to crash.

To ensure that this never happens, you must zero out the data source in your dealloc. However, simply adding that isn't safe either! It's possible for the table view to be destroyed first, and then your message to it will crash. What to do?

The answer to this conundrum is to retain the table view outlet. Don't rely on direct instance variable twiddling, but rather write a setter for it that retains it. Then you can write your dealloc like this:

    - (void)dealloc
    {
        [tableView setDataSource: nil];
        [tableView release];
        [super dealloc];
    }

This is safe because it ensures that the table view is never destroyed before you zero out the weak reference.

Most weak references are subject to this problem, including most delegate references from Cocoa objects. Most of the time you can get away with ignoring it, but it's much safer to do it right.

For a more comprehensive solution to the problem of weak references, check out MAZeroingWeakRef. By using the MAZeroingWeakProxy class and the Objective-C associated object API, it becomes trivial to create delegate and data source connections which are completely safe.

Categories
Categories are a great feature of Objective-C. It's really handy to be able to add new methods to Cocoa classes that you can then use anywhere in your program. However, it can also be dangerous.

The danger comes when your method name clashes with one that Apple has put in the class. Your method will override the existing one. If they do different things, trouble will ensue. Even worse, your category method could be just fine today, but conflict with a method added by Apple in the next release of the OS.

For example, say you add a map: method to NSArray:

    @interface NSArray (MyAdditions)
    
    - (NSArray *)map: (id (^)(id obj))block;
    
    @end

This is fine now, but if Apple adds their own map: method in 10.7, and it doesn't have identical semantics, you'll be in big trouble.

The only way to avoid this is to ensure that your category methods on Apple classes will never have a name conflict. The most obvious way to ensure this is to add a prefix to the method name:

    - (NSArray *)ma_map: (id (^)(id obj))block;

This is ugly, but effective. As a bonus, it's often easier to find your category methods with Xcode's code completion, since you can just type in your prefix and let Xcode show all of them.

Another way to ensure that you never have a conflict is to give your method an extremely specific name that you can be confident will never be used by Apple. For example:

    - (NSArray *)arrayByMappingMyFooElements: (id (^)(MyFoo *foo))block;

But this can be a dangerous game to play. When in doubt, prefix.

Conclusion
Cocoa is a complex system that can have some hidden gotchas. However, for the most part, all you need to do is be aware of the fact that your application is really just one component in a larger system. Write your application to be a good citizen and cooperate nicely with the other components that get loaded into your process. Be particularly careful when subclassing and when making modifications to framework classes. The cases presented above are just a sampling of useful defensive programming techniques in Cocoa. Keep defensive programming on your mind no matter what you write, and your code will be better for it.

That's it for this round of Friday Q&A. I will probably be taking a few weeks off for (good) personal reasons, so don't panic if two weeks go by and I haven't posted another one. I will resume before too long, but won't make any promises as to when just yet.

As always, if you have ideas for topics that you would like to see covered here, send them to me. I may not get to it right away, but I will certainly put your suggestion on my list for the future.

Friday Q&A 2010-08-12: Implementing NSCoding

Fri, 13 Aug 2010 16:35:00 GMT

Friday Q&A 2010-08-12: Implementing NSCoding

Welcome back to another frightening edition of Friday Q&A. This time around, friend and local OS X coder Jose Vazquez has suggested that I discuss how to implement NSCoding in Objective-C classes.

Serialization
Objects in memory can't be directly saved or moved to other programs. They contain data, such as pointers, which are only valid in the context of your process's memory space. Move the contents of an object into another program and all of those pointers suddenly make no sense. Serialization is the process of converting the non-portable, in-memory representation of an object into a portable stream of bytes that can be stored and moved between processes.

Cocoa offers two built-in serialization methods. The most commonly-used method is property list serialization, implemented in the NSPropertyListSerialization class. Property list serialization is fast and produces output that's easy to understand, but is fairly limited in what it can do. It can only store a limited number of classes which support property list serialization, such as NSDictionary and NSString, and it's not possible to extend the classes it supports.

The other method offered by Cocoa is archiving. Archiving can serialize arbitrary objects connected in arbitrary ways, and reconstitute the entire thing on demand. It's extremely powerful, however it's not completely automatic, and requires the programmer to write some code in order to allow their classes to be archived.

Archiving is split into two pieces. One piece is the actual archiver and unarchiver classes. These are NSKeyedArchiver and NSKeyedUnarchiver (and their non-keyed equivalents). They handle the nuts and bolts of translating a bunch of objects into a bunch of bytes.

The other piece is the NSCoding protocol. This is code that you implement in order to tell the archiver how to encode and decode instances of your class.

NSCoding
The NSCoding protocol is short and simple, containing only two methods:

    @protocol NSCoding
    
    - (void)encodeWithCoder:(NSCoder *)aCoder;
    - (id)initWithCoder:(NSCoder *)aDecoder;
    
    @end

You implement encodeWithCoder: to tell the archiver how to serialize your object into bytes, and initWithCoder: to tell the archiver how to transform the serialized representation into a new object. It is necessary to implement both methods.

Note that the parameter to encodeWithCoder:, although typed as NSCoder, is actually the particular archiver instance (for example, an NSKeyedArchiver) that you're working with. Likewise, the parameter to initWithCoder: is actually the particular unarchiver instance (e.g. NSKeyedUnarchiver) that you're using.

Basic Implementation of NSCoding
To implement encodeWithCoder:, you should go through all of the essential properties of your object and use the various methods on NSCoder to encode them. For object properties, just use encodeObject:forKey:. The key can just be a short string that describes the property being encoded:

    - (void)encodeWithCoder: (NSCoder *)coder
    {
        [coder encodeObject: [self name] forKey: @"name"];
        [coder encodeObject: [self title] forKey: @"title"];
    }

The initWithCoder: implementation is then more or less symmetrical. However, there are a few different ways to implement it, depending on your particular taste.

One way is to implement it as a normal initializer, directly setting your instance variables:

    - (id)initWithCoder: (NSCoder *)coder
    {
        if((self = [self init]))
        {
            _name = [[coder decodeObjectForKey: @"name"] retain];
            _title = [[coder decodeObjectForKey: @"title"] retain];
        }
        return self;
    }

Important note: if you use this style and are not using garbage collection, you must retain the objects that come out of decodeObjectForKey:. It's easy to forget to do this, but this method follows the standard Cocoa memory management rules and returns an object that you do not own. If you don't retain it, it will disappear and you will crash.

Another way is to use setter methods rather than setting the instance variables directly:

    - (id)initWithCoder: (NSCoder *)coder
    {
        if((self = [self init]))
        {
            [self setName: [coder decodeObjectForKey: @"name"]];
            [self setTitle: [coder decodeObjectForKey: @"title"];
        }
        return self;
    }

Whether it's better to use a setter or set the instance variable directly is, of course, a matter of some debate.

Finally, you can implement it in terms of your normal initializer. Decode the objects first, then call through to your normal initializer:

    - (id)initWithCoder: (NSCoder *)coder
    {
        NSString *name = [coder decodeObjectForKey: @"name"];
        NSString *title = [coder decodeObjectForKey: @"title"];
        
        return [self initWithName: name title: title];
    }

Of all the possibilities, this last one probably makes things simplest overall. Among other things, it gives your class a single override point for subclasses that need to implement initializers.

Keyed Versus Unkeyed Archiving
If you look at NSCoder, you'll notice that most methods have one variant that takes a key, and one variant that doesn't. For example:

    - (void)encodeObject:(id)object;
    - (void)encodeObject:(id)objv forKey:(NSString *)key;

So why are there two?

Back in the dark days before Mac OS X 10.2 shipped, the non-keyed variants were all that existed. They require that the exact same sequence of calls be made to encode and decode. Any variation causes an error, because the archiver has no way of knowing what you intended. This caused enormous problems when making changes to a code base over time. If you add a third property that needs to be encoded and you want your code to still be able to read old archives (using a default value for the new property) then you had to jump through many painful hoops.

The keyed variants are enormously more flexible. You can encode and decode in any order. You can encode data and neglect to decode it. When decoding, you can check for the presence of a key and supply a default value or take a different action if it's missing.

Today, there is essentially no reason to support non-keyed archiving. (It can still be useful if you're using NSPortCoder with Distributed Objects, but that is an extremely rare situation.) Therefore, in general, you should write your NSCoding implementation to assume keyed coding, and use NSKeyedArchiver and NSKeyedUnarchiver.

If for some reason you do need to support both, you can simply check [coder allowsKeyedCoding] to see what kind you're dealing with, and take the appropriate actions.

Conditional Encoding
The great thing about NSCoding is that it makes it easy to encode large, complex object graphs. The coder automatically ensures that cyclical references don't cause an infinite loop, and that multiple references to the same object don't result in multiple copies of that object being encoded.

However, sometimes you don't want to encode the entire object graph. Imagine an implementation of a board game, with a class for the board and for the pieces:

    @interface GameBoard : NSObject <NSCoding>
    {
        NSMutableArray *_gamePieces;
    }
    @end

    @interface GamePiece : NSObject <NSCoding>
    {
        GameBoard *_gameBoard; // weak reference to avoid retain cycles
    }
    @end

You want to be able to serialize an entire board and have all of the pieces automatically included. This is easy, of course: just have GameBoard encode its _gamePieces array. You also want to ensure that the GamePiece back reference to the board is preserved. This can be done by simply encoding it and decoding it. Since it's a weak reference, you would decode it and not retain it.

This approach works fine as long as you're serializing an entire board. But perhaps you also want to serialize a single piece by itself. What happens then?

With the simple approach to implementing NSCoding, you'll end up serializing not only the piece, but the board that it's a part of, every other piece on the board, and any other data that's part of the game board. Worse, because the _gameBoard reference is weak, the board will be destroyed after decoding, causing a dangling pointer. Your archives are large and your code sometimes mysteriously crashes when loading them. Not what you want!

In order to solve this problem, NSCoder provides conditional objects. This allows you to encode an object only if something else unconditionally encodes it. If nothing needs the object, then it doesn't get encoded. In that situation, when you decode, you get nil.

Conditional objects are perfect for encoding just one piece of a larger object graph. The GamePiece can use a conditional object when encoding _gameBoard. If you explicitly encode the entire board, then the conditional object will point to it. However, if you encode an individual game piece, then the board will not be encoded, because nothing ever encoded it unconditionally.

Thus, to solve this problem, you simply change -[GamePiece encodeWithCoder:] to look like this:

    - (void)encodeWithCoder: (NSCoder *)coder
    {
        [coder encodeConditionalObject: _gameBoard forKey: @"gameBoard"];
    }

In general, anything that's a weak reference in memory should be a conditional object in your NSCoding implementation.

Encoding Non-Object Data
So far I've talked a lot about encoding objects, but what about all of that non-object data floating around?

For primitives, NSCoder provides a variety of methods to encode various integer and floating-point types. You can simply call encodeInteger:forKey: or encodeDouble:forKey: to save your individual values. For types that aren't supported, for example short, you can simply encode as a bigger compatible type that is supported, like int.

Structs can get more difficult. Non-keyed archiving actually supported encoding and decoding of arbitrary structs, but for some reason this capability was removed in the keyed archivers. Perhaps because it made things too fragile; you couldn't alter the struct without breaking all of your archives.

In general, the best way to handle a struct is to simply encode and decode each field of the struct separately. If that is too unwieldy, then you should consider rewriting the struct as an Objective-C class that supports NSCoding itself, so that you can just directly encode instances of it.

For built-in Cocoa structs like NSRect, use the built-in functions to transform them to NSString. For example, call NSStringFromRect and encode the resulting string, and call NSRectFromString on the decoded object. This is somewhat less efficient, but much easier to code and debug.

The worst part is arrays. There is no built-in support for archiving C arrays. There are a few workarounds you can use, depending on how big your arrays are and how much code you want to write:

Transform your C array into an NSArray containing instances of NSValue, and encode that. You can either construct a temporary NSArray from your C array in your -initWithCoder: implementation, or you can do a complete conversion use the NSArray throughout.

Construct keys dynamically and encode each entry in the array separately. You can write a loop like this:

        for(int i = 0; i < arrayLength; i++)
            [coder encodeInt: intArray[i] forKey: [NSString stringWithFormat: @"intArray%d", i]];

And then a similar loop on decoding.

Encode raw bytes using encodeBytes:length:forKey:. This requires paying special attention to things like endianness and data type issues. (If you have an array of NSInteger or CGFloat, they will not be the same size between machines. If you have an array of any multi-byte values, they may not be in the same format between machines.) How to handle these issues is somewhat beyond the scope of this article, but research on endianness and serializing raw C data should cover it.

For C strings, which are a special case of arrays, the simplest way to handle it is probably to simply convert it to an NSString and encode that. It would also be safe to run a C string through encodeBytes:length:forKey:.

Reading Old Archives
If your code lives long enough, eventually you'll change what you encode and decode. Normally, you still want your code to be able to read old archives despite the changes.

For simple changes, like adding a new property to a class, you often don't need to do anything. Your call to decodeObject:forKey: will return nil. Calls to methods like decodeIntForKey: will return 0. Write your new code to tolerate this, and your job is done.

Sometimes you need to do more. If your changes are complicated enough, you may want to create two separate code paths, one for the old data structure and one for the new. In that case, it's easy to differentiate between the two by adding a version key to your NSCoding implementation. Check the value of the key when decoding, and you'll know which path to take.

Note that adding a version key isn't something that needs to be done ahead of time. You can add it in your new code. The lack of a version key in the old archives will identify them as such. If you encode a simple integer, set the new version as 1, and then trying to get the version of an old archive will conveniently give you 0, and you'll have room to expand further if you need more changes.

If you refactor your code, you might change class names. If these classes are archived, then you have an incompatibility. The old class name exists in the old archive, and when the unarchiver tries to find it at decoding time, it will fail.

This can be worked around by using the -setClass:forClassName: before unarchiving:

    [unarchiver setClass: [NewClass class] forClassName: @"OldClass"];

Reading New Archives With Old Code
You often want to go in reverse as well. Just because you added some new information to your archive format doesn't mean you want to make new archives incompatible with old versions of your software. It's not always possible to maintain backwards compatibility, but if your changes are simple then it can be easy.

If you add a new property to a class, ensure that the existing properties remain consistent amongst each other, and complete in terms of what the old version of your software needs. Then old versions will continue to work with little effort. For example, imagine if you add a title property to a Person class. The old version will only see the old name property, and will lose title, but will otherwise continue to work.

If you completely revamp a class, you might consider archiving both the new properties and a set of compatibility properties intended for old code. New code can read the new properties, and old code can read the old properties and continue to work, at least in some fashion.

Finally, if you rename a class, that will break old versions of the software unless you compensate for it, just as renaming a class will break old archives. To fix this, you can tell the archiver to save your class under its old name using the setClassName:forClass: method:

    [archiver setClassName: @"OldClass" forClass: [NewClass class]];

Backwards compatibility can be difficult, particularly if you add a lot of new data or capabilities. It's also generally much less important than forward compatibility. Consider all of the tradeoffs involved and don't be afraid to break backwards compatibility. Just ensure that, if you do, trying to load a new archive into an old version of your software fails gracefully.

Conclusion
NSCoding is a powerful way to serialize objects so that you can pass them between processes or save it to a file. Implement the NSCoding protocol on your custom objects that you want to serialize, then use NSKeyedArchiver to serialize them and NSKeyedUnarchiver to deserialize them.

That's it for this edition of Friday Q&A. Come back next time for another exciting adventure in the world of Mac programming. Until then, if you have an idea that you would like to see covered here, please send me your suggestions!

Friday Q&A 2010-07-30: Zeroing Weak References to CoreFoundation Objects

Fri, 30 Jul 2010 19:01:00 GMT

Friday Q&A 2010-07-30: Zeroing Weak References to CoreFoundation Objects

It's time for another friendly edition of Friday Q&A. For my last Friday Q&A, I talked about MAZeroingWeakRef and how it's implemented for pure Objective-C objects. For this one, I'm going to discuss the crazy hacks I implemented to make it work with toll-free bridged CoreFoundation objects as well.

Code
Just as before, you can get the code for MAZeroingWeakRef from my public Subversion repository:

    svn co http://mikeash.com/svn/ZeroingWeakRef/

Or click the above link to browse it. If you already have a local copy from last time, be sure to update it, as I have made substantial changes since then.

Prior Reading
This post assumes fairly good knowledge of CoreFoundation and how CF-ObjC bridging works. If you haven't already, you may wish to read or at least refer to Friday Q&A 2010-01-22: Toll Free Bridging Internals.

Recap
A zeroing weak reference is a reference to an object which does not participate in keeping that object alive. When the target object is destroyed, the zeroing weak reference automatically becomes NULL. When a zeroing weak reference's target is requested, the caller is guaranteed to either get a valid reference, or NULL. This is useful for all kinds of things as covered in the previous article.

In order to accomplish this in Cocoa, MAZeroingWeakRef overrides the dealloc method of the target object by dynamically creating a subclass of the target's class, and changing the class of the target. This overridden dealloc method zeroes out MAZeroingWeakRef objects that point to the target.

There is a problem with thread safety and resurrection if you stop there. Imagine one thread calls release on the last strong reference to an object, causing it to then call dealloc. Imagine that between these two, another thread accesses the object through a zeroing weak reference. Since dealloc has not yet been called, it returns a reference to the object. However, because the dealloc call is already set to go, the retain/autorelease dance done by MAZeroingWeakRef can't save the object from being destroyed. Disaster!

This problem is solved by also overriding release. By having release acquire a lock that's also used when retrieving a zeroing weak reference target, it's assured that this resurrection scenario can't occur.

Toll-Free Bridged Objects
This scheme works great for normal Objective-C objects, but fails hard for bridged CoreFoundation objects. Changing out the class of a bridged object causes infinite recursion. The first thing a CoreFoundation function does is check the class of the object it's being called on. If that class doesn't match the official NSCF class, it assumes it's a pure Objective-C class and calls through to the Objective-C equivalent method. The Objective-C equivalent method on an NSCF class just calls the CoreFoundation function. Rinse, lather, repeat, and crash.

The dynamic subclass wouldn't be strictly necessary in this case. I could instead swizzle out the dealloc and release methods on the NSCF class directly, and have them do my dirty work. This is a bit less efficient (since I'm affecting every object of that class, not just weak-referenced ones) but that shouldn't matter.

The trouble is that this doesn't work. If you call CFRelease on such an object, it goes directly to the refcounting and deallocation of that object without ever calling the Objective-C methods. So this solution can only catch one side of things, which is basically useless.

After working through all of this, I hunted around for a solution. Short of patching CFRelease (which I really didn't want to do, not the least of which because this approach won't work on the iPhone, where modifying executable code is forbidden) I couldn't come up with a way.

I nearly gave up on the problem, resigned to simply forbidding weak references to CoreFoundation objects, when I finally happened upon....

The Solution
I had started looking through the CoreFoundation source code (available from opensource.apple.com) trying to find a way to hook into release events when I happened up on this little gem in the code for CFRelease:

    void (*func)(CFTypeRef) = __CFRuntimeClassTable[typeID]->finalize;
    if (NULL != func) {
        func(cf);
    }
    // We recheck lowBits to see if the object has been retained again during
    // the finalization process.  This allows for the finalizer to resurrect,
    // but the main point is to allow finalizers to be able to manage the
    // removal of objects from uniquing caches, which may race with other threads
    // which are allocating (looking up and finding) objects from those caches,
    // which (that thread) would be the thing doing the extra retain in that case.
    if (isAllocator || OSAtomicCompareAndSwap32Barrier(1, 0, (int32_t *)&((CFRuntimeBase *)cf)->_rc)) {
        goto really_free;
    }

The comment about resurrection is key. While I can't intercept the CFRelease to eliminate the race condition, I can detect it and allow the object to resurrect so that I can recover from the situation. I was on my way!

Implementing this solution requires overriding the CoreFoundation finalize function. CoreFoundation has no supported mechanism for this, so I had to get down and dirty with the CF source code and hack my way in. This means that everything I'm doing is not entirely supported and could break, although I believe that this stuff is actually pretty stable.

CoreFoundation Classes
A CoreFoundation class is just a struct that looks like this:

    typedef struct __CFRuntimeClass {	// Version 0 struct
        CFIndex version;
        const char *className;
        void (*init)(CFTypeRef cf);
        CFTypeRef (*copy)(CFAllocatorRef allocator, CFTypeRef cf);
        void (*finalize)(CFTypeRef cf);
        Boolean (*equal)(CFTypeRef cf1, CFTypeRef cf2);
        CFHashCode (*hash)(CFTypeRef cf);
        CFStringRef (*copyFormattingDesc)(CFTypeRef cf, CFDictionaryRef formatOptions);	// str with retain
        CFStringRef (*copyDebugDesc)(CFTypeRef cf);	// str with retain
        void (*reclaim)(CFTypeRef cf);
    } CFRuntimeClass;

It's basically just a table with a few function pointers in it for common operations that all CF objects support. All class-specific functionality is implemented as functions and has no dynamic lookup at all (except for the stuff present in toll-free bridging support).

Overriding the finalize function then becomes easy. First, look up the CFRuntimeClass for the given CF type ID with this function:

    extern CFRuntimeClass * _CFRuntimeGetClassWithTypeID(CFTypeID typeID);

I can then replace the finalize function pointer with my own function. I still need to call through to the original, so I make my own table for the original function pointers, indexed by CF type ID:

    typedef void (*CFFinalizeFptr)(CFTypeRef);
    static CFFinalizeFptr *gCFOriginalFinalizes;
    static size_t gCFOriginalFinalizesSize;

If you'll remember from last time, my utility function CreateCustomSubclass is responsible for creating a dynamic Objective-C subclass for a given object. The original implementation checked to see if the object was a bridged CoreFoundation object and simply asserted if it was. The new implementation handles swizzling out the finalize function pointer to my custom function:

    static Class CreateCustomSubclass(Class class, id obj)
    {
        if(IsTollFreeBridged(class, obj))
        {
            CFTypeID typeID = CFGetTypeID(obj);
            CFRuntimeClass *cfclass = _CFRuntimeGetClassWithTypeID(typeID);
            
            if(typeID >= gCFOriginalFinalizesSize)
            {
                gCFOriginalFinalizesSize = typeID + 1;
                gCFOriginalFinalizes = realloc(gCFOriginalFinalizes, gCFOriginalFinalizesSize * sizeof(*gCFOriginalFinalizes));
            }
            
            do {
                gCFOriginalFinalizes[typeID] = cfclass->finalize;
            } while(!OSAtomicCompareAndSwapPtrBarrier(gCFOriginalFinalizes[typeID], CustomCFFinalize, (void *)&cfclass->finalize));
            return class;
        }
        else
            // original ObjC dynamic subclassing code is here

There's nothing too complicated here. The first part just gets the requisite information. The if statement in the middle handles resizing the table if it's too small. (CF type IDs are small integers, so a flat array indexed by them works nicely.) The last part swizzles out the original function pointer, using an atomic call to ensure that it's thread safe just in case anybody else happens to be trying the same thing at the exact same time.

With this change, it's now critical that IsTollFreeBridged be 100% reliable. The old implementation simply looked for a class name that started with NSCF, and that's not good enough. I came up with a completely reliable test using a private CoreFoundation table of Objective-C classes:

    extern Class *__CFRuntimeObjCClassTable;

This table maps a CF type ID to the NSCF Objective-C class. Checking for bridgedness is then just a matter of getting the type ID of the object in question, getting the bridged class of the type ID, and seeing if the object's class matches it or not:

    static BOOL IsTollFreeBridged(Class class, id obj)
    {
        CFTypeID typeID = CFGetTypeID(obj);
        Class tfbClass = __CFRuntimeObjCClassTable[typeID];
        return class == tfbClass;
    }

The finalize swizzling re-points to CustomCFFinalize. This function simply checks for resurrection by looking at CFGetRetainCount, and then if resurrection has not taken place, it clears out all weak references to the object and calls the original finalize function:

    static void CustomCFFinalize(CFTypeRef cf)
    {
        WhileLocked({
            if(CFGetRetainCount(cf) == 1)
            {
                ClearWeakRefsForObject((id)cf);
                void (*fptr)(CFTypeRef) = gCFOriginalFinalizes[CFGetTypeID(cf)];
                if(fptr)
                    fptr(cf);
            }
        });
    }

Easy! Right? Right...?

Resurrection Comes Back From the Dead
Unfortunately, there's a race condition here. Imagine the following sequence:

Thread 1
1. CFRelease(obj)
2. CFRelease calls CustomCFFinalize
3. Before CustomCFFinalize begins executing, the thread is preempted
Thread 2
1. [ref target] obtains reference to obj
2. obj is retained and autoreleased by MAZeroingWeakRef
3. The enclosing autorelease pool is drained, resulting in CFRelease(obj)
4. CFRelease calls CustomCFFinalize
5. CustomCFFinalize clears weak references and calls the original finalize
6. CustomCFFinalize returns
Thread 1
1. Resumes execution at the beginning of CustomCFFinalize
2. CustomCFFinalize checks the retain count, which is still 1
3. CustomCFFinalize calls the original finalize a second time on the same object
4. A horrible flaming crash occurs

What's worse, CFRelease isn't even safe in the presence of resurrecting finalizers. It checks the object's reference count a second time after the finalizer returns. However, the object could have been resurrected and destroyed in the intervening time, causing a bad memory access. In order to make this safe, we can't allow any possibility that the object is destroyed until CFRetain itself returns.

Thus there is an extremely narrow, difficult-to-hit, but entirely real race condition that could cause this code to crash.

Hack Level Three
In order to solve this problem, I divide CoreFoundation objects into two categories. Some objects are the target of a weak reference, and the rest are not. This serves two purposes. First, it allows me to take a fast path when destroying an object that was never the target of a weak reference. Second, I can track whether a referenced object can still potentially be resurrected or not.

This is implemented by simply keeping a CFMutableSet where referenced objects are stored. Checking the status of an object is simply a matter of testing set membership. Objects are inserted into the set when calling RegisterRef. Objects are removed when the finalize executes with a retain count of 1, which ensures that it can no longer be resurrected.

The new CustomCFFinalize is then split in two. If the object has weak references, it first checks for a retain count of 1 to see whether it's been resurrected:

static void CustomCFFinalize(CFTypeRef cf)
    {
        WhileLocked({
            if(CFSetContainsValue(gCFWeakTargets, cf))
            {
                if(CFGetRetainCount(cf) == 1)
                {

If the retain count is still 1 then the object has not been resurrected. It's still not safe to destroy, however, as multiple threads may be sitting in this spot. Instead, the code clears out all weak references, retains the object to deliberately resurrect it, and then arranges for it to be released later:

                    ClearWeakRefsForObject((id)cf);
                    CFSetRemoveValue(gCFWeakTargets, cf);
                    CFRetain(cf);
                    CallCFReleaseLater(cf);
                }
            }

If the object has no weak references, then simply call through to the original finalize function without any fuss:

            else
            {
                void (*fptr)(CFTypeRef) = gCFOriginalFinalizes[CFGetTypeID(cf)];
                if(fptr)
                    fptr(cf);
            }
        });
    }

Easy enough, right? But how exactly does that CallCFReleaseLater function work?

Using autorelease would do the trick, except that this is pure CF code and there's no guarantee that the caller actually has an autorelease pool in place. A nice idea, but it just doesn't work out.

Some way to hook CFRelease to see when it exits would be ideal. But as discussed before, there's simply no available hook, so that goes out as well.

Ultimately I obtained some serious inspiration from Ed "Master of All Things Arcane" Wynne that it could really be done by using a completely insane technique similar to the cache-cleanup scheme in the Objective-C runtime.

The Crazy Scheme
To restate the problem: I need to call CFRelease on the object sometime after the original call to CFRelease has completed. Since there's no way to arrange this on the thread that made the original call to CFRelease, I make use of a background thread.

How can the background thread know when the original call to CFRelease has completed?

It's possible for one thread to access the PC (program counter, the location of the currently executing instruction) of another thread. Normally this is not very useful, but the Objective-C runtime uses it to see whether it's safe to destroy stale cache data by looking to see if any other threads are in a function that accesses it.

Likewise, this code can check the PC of the original calling thread and see if it's still within CFRelease or not. If it's not, then the call must have finished, so it's now safe to release the object again.

The only way (that I know of) to get the PC of another thread on OS X is to use mach calls, so the first step is to get a reference to the current mach thread. This reference is also "retained" (mach ports are reference counted, just like Objective-C objects) so that it doesn't go invalid in case the thread is destroyed in the mean time:

static void CallCFReleaseLater(CFTypeRef cf)
    {
        mach_port_t thread = pthread_mach_thread_np(pthread_self());
        mach_port_mod_refs(mach_task_self(), thread, MACH_PORT_RIGHT_SEND, 1 ); // "retain"

Next up, send this thread reference and the CF object pointer to a background thread. I use NSOperationQueue to handle the backgrounding. I create an NSInvocationOperation to handle the release (pointing it towards a class method on MAZeroingWeakRef, since it can't deal with pure functions) and add it to the queue. Everything is wrapped in an autorelease pool in case this code is being called from a context which doesn't already have one:

        NSAutoreleasePool *pool = [[NSAutoreleasePool alloc] init];
        SEL sel = @selector(releaseLater:fromThread:);
        NSInvocation *inv = [NSInvocation invocationWithMethodSignature: [MAZeroingWeakRef methodSignatureForSelector: sel]];
        [inv setTarget: [MAZeroingWeakRef class]];
        [inv setSelector: sel];
        [inv setArgument: &cf atIndex: 2];
        [inv setArgument: &thread atIndex: 3];
        
        NSInvocationOperation *op = [[NSInvocationOperation alloc] initWithInvocation: inv];
        [gCFDelayedDestructionQueue addOperation: op];
        [op release];
        [pool release];
    }

The code for releaseLater:fromThread: is based around a loop. It continuously checks the PC of the target thread until that PC has moved out of the target range. Once it's out, it releases the object as well as the thread that was passed in to it. To start with, the loop:

    + (void)releaseLater: (CFTypeRef)cf fromThread: (mach_port_t)thread
    {
        BOOL retry = YES;
        
        while(retry)
        {

Next, fetch the PC of the target thread. (GetPC is a helper function I'll get to in a moment.)

            BLOCK_QUALIFIER void *pc;
            // ensure that the PC is outside our inner code when fetching it,
            // so we don't have to check for all the nested calls
            WhileLocked({
                pc = GetPC(thread);
            });

Now start checking the PC for validity. First see if it contains anything at all. If not, assume a transient error occurred and try again (this may not be the best strategy...):

            if(pc)
            {

Next, see if the PC is within CustomCFFinalize. Since that's called from CFRelease, it's possible that the target is still in there, and we need to wait for it to exit. To do this, check the PC to see if it's between the start of that function and the start of the one following it. (The compiler lays out functions in order in memory, so the beginning of IsTollFreeBridged is right after the end of CustomCFFinalize):

                if(pc < (void *)CustomCFFinalize || pc > (void *)IsTollFreeBridged)
                {

If that test passes, see if the PC is within CFRelease. I don't know the order of functions in CoreFoundation so I can't use that same trick. Instead, I use the dladdr call. This returns the last symbol that comes before the specified address, among other info. I can just check that against _CFRelease (the private function that actually handles the guts of a CFRelease call). If it matches, try again later:

                    Dl_info info;
                    int success = dladdr(pc, &info);
                    if(success)
                    {
                        if(info.dli_saddr != _CFRelease)
                        {

If all the tests pass, then it's good to go. Clear retry to indicate that the test succeeded, call CFRelease, and dispose of the thread reference:

                            retry = NO; // success!
                            CFRelease(cf);
                            mach_port_mod_refs(mach_task_self(), thread, MACH_PORT_RIGHT_SEND, -1 ); // "release"
                        }
                    }
                }
            }
        }
    }

One last thing, the GetPC function. The implementation is highly architecture-specific. The generalized part looks like this:

    static void *GetPC(mach_port_t thread)
    {
        // arch-specific code goes here
        
        kern_return_t ret = thread_get_state(thread, flavor, (thread_state_t)&state, &count);
        if(ret == KERN_SUCCESS)
            return (void *)state.PC_REGISTER;
        else
            return NULL;
    }

The real code in the repository has conditionals that define state, flavor, and the rest for Intel 32/64, PPC 32/64, and ARM.

And that's it!

Odds and Ends
In the previous post, I mentioned the COREFOUNDATION_HACK_LEVEL macro that controls how much hack MAZeroingWeakRef contains. When set to 0, it makes use of no private API. It refuses to reference CoreFoundation objects, and detects them by checking the class name for an NSCF prefix. When set to 1, it only uses private API to make a reliable CoreFoundation object check. Level 1 is now the default.

When I wrote the previous post, I didn't actually know about this subtle resurrection race condition. As such, I've added an extra hack level. Hack level 2 uses private CoreFoundation calls to allow referencing CF objects, but does not eliminate the resurrection race condition I described above. Finally, the newly-added hack level 3 goes into full-on CoreFoundation hackery as described above, and eliminates the race condition by doing the final CFRelease in a background thread.

These can be controlled using the COREFOUNDATION_HACK_LEVEL macro at the top of the file. I recommend level 1 for Mac development (weak references to CoreFoundation objects are not commonly needed) and level 0 for iOS development (Apple gets their underwear in a twist over private API usage). However, if you're adventurous or need weak references to CF objects, you can set it to 3 and everything should still work.... If you do, keep in mind that the really horrible hacks don't activate until you actually create a weak reference to a CF object, so you can enable it just in case you inadvertently reference a CF object, but not worry about it doing anything terrible in the normal case.

Conclusion
In the last post I showed how to create zeroing weak references to Objective-C objects with relative ease. In this post, I show that doing the same to CoreFoundation objects is, if not easy, at least possible. A great deal of mucking about with private APIs is required, but the solution should be fairly robust.

This kind of hackery is extremely challenging but it's also a lot of fun. The CoreFoundation source code is a valuable resource for this kind of thing, but as always you must beware of private symbols which may change in the future. Other low-level open source code like the Objective-C runtime can also be a handy read. Finally, otx is an extremely useful tool for when you need to see how a library works when Apple doesn't provide source.

That's it for this edition of Friday Q&A. Come back in two weeks for more wacky hijinks.

As always, Friday Q&A is driven by user ideas. If you have a topic that you would like to see covered here, please send it in!

Introducing MAZeroingWeakRef

Fri, 16 Jul 2010 20:19:00 GMT

Introducing MAZeroingWeakRef

I'm extremely excited to announce a new library for Cocoa and Cocoa Touch development: MAZeroingWeakRef. In short, it's a library which allows zeroing weak references to be used in retain/release Cocoa code. This has all sorts of uses and should make retain/release coding less painful. While I discussed this in detail in my Friday Q&A post this week, I also want to make a separate announcement for people who don't want to read through all of the horrible details.

A zeroing weak reference is a reference to an object which does not prevent that object from being destroyed (in other words, it's not retained), and which automatically becomes nil once the object is destroyed. To use MAZeroingWeakRef, you simply create one using -initWithTarget::

    MAZeroingWeakRef *ref = [[MAZeroingWeakRef alloc] initWithTarget: object];

You can access the object at any time using the -target method:

    NSLog(@"Target is %@", [ref target]);

As long as the object continues to exist, -target will return it. Once it is destroyed, -target will return nil. -target returns a reference that has been retained and autoreleased, ensuring that the returned object will remain valid as you use it even if the last strong reference to it has been released in another thread while you work.

You can get MAZeroingWeakRef from my public subversion repository:

    svn co http://mikeash.com/svn/ZeroingWeakRef

It's released under a BSD license, so you can use it in your commercial applications with acknowledgement.

MAZeroingWeakRef should compile and run on any OS with the "modern" runtime APIs, which is basically 10.5 and up, and any iOS version. Blocks support is needed to enable the cleanup block functionality (which allows running arbitrary code when the reference is destroyed) but everything else will work without it.

If you use MAZeroingWeakRef on iOS, you may want to set COREFOUNDATION_HACK_LEVEL to 0 in MAZeroingWeakRef.m. This prevents MAZeroingWeakRef from being able to target CoreFoundation bridged objects, but also avoids the use of private API, which Apple can sometimes be unfriendly about. This is not a big disadvantage, as it's extremely rare to have weak references to CF objects.

I hope that this library will prove useful!

Friday Q&A 2010-07-16: Zeroing Weak References in Objective-C

Fri, 16 Jul 2010 20:18:00 GMT

Friday Q&A 2010-07-16: Zeroing Weak References in Objective-C

It's that time of the biweek again. For this week's Friday Q&A, Mike Shields has suggested that I talk about weak references in Objective-C, and specifically zeroing weak references. I've gone a bit further and actually implemented a class that provides zeroing weak references in Objective-C using manual memory management.

Weak References
First, what is a weak reference? Simply put, a weak reference is a reference (pointer, in Objective-C land) to an object which does not participate in keeping that object alive. For example, using memory management, this setter creates a weak reference to the new object:

    - (void)setFoo: (id)newFoo
    {
        _foo = newFoo;
    }

Because the setter does not use retain, the reference does not keep the new object alive. It will stay alive as long as it's retained by other references, of course. But once those go away, the object will be deallocated even if _foo still points to it.

Weak references are common in Cocoa in order to deal with retain cycles. Delegates in Cocoa are almost always weak references for exactly this reason.

Zeroing Weak References
Weak references are useful for things like avoiding retain cycles, but their utility is limited due to their inherent danger. With a plain weak reference in Objective-C, when the target object is destroyed, you're left with a dangling pointer. If your code tries to use that pointer, it will crash or worse.

Zeroing weak references eliminate this danger. They work just like a regular weak reference, except that when the target object is destroyed, they automatically become nil. At any time you access an object through a zeroing weak reference, you're guaranteed to either access a valid, live object, or get nil. As long as your code can handle nil, then you're perfectly safe.

Because of this safety, a zeroing weak reference can be useful for much more than the unsafe kind. One example is an object cache. An object cache using weak references can refer to objects as long as they're alive, and then let them deallocate when no longer needed. If a client requests an object that's still alive, it can obtain it without having to create a new object. If the object has already been destroyed, the cache can safely create a new object.

They can be used for much more mundane purposes as well, for any case where you want to keep a reference to an object but don't want to keep that object in memory beyond its normal lifetime. For example, you might track a window but not want to keep it in memory after it's closed. You could deal with this by setting up a notification observer and seeing when the window goes away, but a zeroing weak reference is a much simpler way to do it. As another example, a zeroing weak reference to self used in a block can prevent a retain cycle while ensuring that your program doesn't crash if the block is called after self is deallocated. Even a standard delegate pointer is made better with a zeroing weak reference, as it eliminates rare but annoying bugs which can appear if the delegate is deallocated before the object that points to it.

If you're using garbage collection in Objective-C, then good news! The Objective-C garbage collector already supports zeroing weak references using the type modifier __weak. You can just declare any instance variable like so:

    __weak id _foo;

And it's automatically a zeroing weak reference. The compiler takes care of emitting the appropriate read/write barriers so that access is always safe.

What if you aren't using garbage collection, though? While it would be great if we all could, many of us can't for various reasons, one of the most common being that garbage collection simply isn't supported on iOS. Well, until now you've been out of luck when it comes to zeroing weak references with manual memory management in Objective-C.

Introducing MAZeroingWeakRef
Those of us who use manual memory management can now benefit from zeroing weak references! MAZeroingWeakRef implements the following interface:

    @interface MAZeroingWeakRef : NSObject
    {
        id _target;
    }
    
    + (id)refWithTarget: (id)target;
    
    - (id)initWithTarget: (id)target;
    
    - (void)setCleanupBlock: (void (^)(id target))block;
    
    - (id)target;
    
    @end

Usage is extremely simple. Initialize it with a target object. Retrieve the target object when you need to use it. The -target method will either return the target object (retained/autoreleased to guarantee that it will stay alive until you're done with it) or, if the target has already been destroyed, it will return nil.

The -setCleanupBlock: method exists for more advanced uses. Normally a zeroing weak reference is a passive object. You can query its target at any time, and it either gives you an object or nil. But sometimes you want to take some additional action when the reference is zeroed out, such as unregistering a notification observer. The block passed to -setCleanupBlock: runs when the reference is zeroed out, allowin gyou to set up additional actions like that.

As an example, here's how to write the standard delegate pattern using MAZeroingWeakRef:

    // instance variable
    MAZeroingWeakRef *_delegateRef;
    
    // setter
    - (void)setDelegate: (id)newDelegate
    {
        [_delegateRef release];
        _delegateRef = [[MAZeroingWeakRef alloc] initWithTarget: newDelegate];
    }
    
    - (void)doSomethingAndCallDelegate
    {
        [self _doSomething];
        
        id delegate = [_delegateRef target];
        if([delegate respondsToSelector: @selector(someDelegateMethod)])
            [delegate someDelegateMethod];
    }

This is only slightly harder than using normal, dangerous weak references, and provides complete safety. (If you use this pattern, remember that you must now release _delegateRef in -dealloc!)

MAZeroingWeakRef is completely thread safe, both in terms of accessing it from multiple threads, and in terms of having the target object be destroyed in one thread while the weak reference is accessed from another thread.

How Does it Work?
The concept of how a zeroing weak reference works is pretty straightforward. Track all such references to a target. When an object is destroyed, zero out all of those references before calling dealloc. Wrap everything in a lock so that it's thread safe.

The details of how to accomplish each step can get tricky, though.

Tracking all zeroing weak references to a target isn't too tough. A global CFMutableDictionary maps targets to CFMutableSet objects which hold the zeroing weak references to each target. I use the CF classes so that I can customize the memory management; I don't want the targets or weak references to be retained.

Zeroing all of the weak references before calling dealloc gets a little trickier....

The answer to that is to use dynamic subclassing, as done in the implementation of Key-Value Observing. When an object is targeted by a zeroing weak reference, a new subclass of that object's class is created. The -dealloc method of the new subclass takes care of zeroing out all of the weak references and then calls through to super so that the normal chain of deallocations can occur. The new subclass also overrides -release to take a lock so that everything is thread safe. (Without that override, it would be possible for one thread to release an object with a retain count of 1 at the same time that another thread retrieved the object from a MAZeroingWeakRef. The retrieval would then try to resurrect the object after it had already been marked for destruction, which is illegal.)

Of course you don't want to make a new subclass for every single targeted object, but only one subclass is necessary per target class. A small table of overridden classes ensures that no more than one new subclass is created for each normal class.

As the final step, the class of the target object is set to be the new subclass, ensuring that the new methods take effect.

CoreFoundation Trickiness
The above strategy runs into a snag with toll-free bridged classes like NSCFString. Because of the way they're implemented, changing the class of such an object causes infinite recursion and a crash the moment that something tries to use them. The CoreFoundation code sees the changed class, assumes it's a pure Objective-C class, and calls through to the equivalent Objective-C method. The NSCF method then calls back to CoreFoundation. A crash rapidly ensues.

While I did figure out a solution to this problem, it is so hairy and complicated that I will save it for a separate article to be posted in two weeks.

Code
As usual, you can get the code for MAZeroingWeakRef from my public Subversion repository:

    svn co http://mikeash.com/svn/ZeroingWeakRef/

Or just click the link above to browse the code.

I will be walking through a somewhat abbreviated version of MAZeroingWeakRef. Due to the crazy nature of the CoreFoundation workaround I mentioned above, I will skip over those parts and only discuss the sane Objective-C bits this week. There is a macro called COREFOUNDATION_HACK_LEVEL which allows control over how much CoreFoundation hackery is enabled. At level 2 you get full-on hackery with full support for weak references to CoreFoundation objects. With level 1, some less important private symbols are referenced and used to reliably decide whether an object is bridged or not, and the code simply asserts if trying to create a weak reference to a bridged object. At level 0, the code asserts when trying to create a weak reference to a bridged object, and checks for bridging simply by looking for a prefix of NSCF in the class name. For this week, I will be discussing the code as if it were compiled with level 0.

Globals
MAZeroingWeakRef makes use of some global variables for various housekeeping uses. First off is a mutex:

    static pthread_mutex_t gMutex;

This is used to protect the other global data structures, as well as the table of zeroing weak references that's attached to each target object.

Next up, a CFMutableDictionary is needed to map the target objects to the weak references which target them:

    static CFMutableDictionaryRef gObjectWeakRefsMap; // maps (non-retained) objects to CFMutableSetRefs containing weak refs

Next, an NSMutableSet is used to track the dynamic subclasses that are created, and an NSMutableDictionary is used to map from normal classes to their dynamic subclasses:

    static NSMutableSet *gCustomSubclasses;
    static NSMutableDictionary *gCustomSubclassMap; // maps regular classes to their custom subclasses

Finally, implement +initialize to set up all of these variables. The only tricky business here is that it uses a recursive mutex rather than a regular one. There are cases where the critical section can be re-entered, such as creating a MAZeroingWeakRef pointing to another MAZeroingWeakRef, and using a recursive mutex allows that to function.

    + (void)initialize
    {
        if(self == [MAZeroingWeakRef class])
        {
            CFStringCreateMutable(NULL, 0);
            pthread_mutexattr_t mutexattr;
            pthread_mutexattr_init(&mutexattr);
            pthread_mutexattr_settype(&mutexattr, PTHREAD_MUTEX_RECURSIVE);
            pthread_mutex_init(&gMutex, &mutexattr);
            pthread_mutexattr_destroy(&mutexattr);
            
            gCustomSubclasses = [[NSMutableSet alloc] init];
            gCustomSubclassMap = [[NSMutableDictionary alloc] init];
        }
    }

I also write a quick helper to execute a block of code while holding the lock:

    static void WhileLocked(void (^block)(void))
    {
        pthread_mutex_lock(&gMutex);
        block();
        pthread_mutex_unlock(&gMutex);
    }

And three more helpers to deal with adding a weak reference to an object's CFMutableSet, removing a weak reference from an object, and clearing out all weak references to an object:

    static void AddWeakRefToObject(id obj, MAZeroingWeakRef *ref)
    {
        CFMutableSetRef set = (void *)CFDictionaryGetValue(gObjectWeakRefsMap, obj);
        if(!set)
        {
            set = CFSetCreateMutable(NULL, 0, NULL);
            CFDictionarySetValue(gObjectWeakRefsMap, obj, set);
            CFRelease(set);
        }
        CFSetAddValue(set, ref);
    }
    
    static void RemoveWeakRefFromObject(id obj, MAZeroingWeakRef *ref)
    {
        CFMutableSetRef set = (void *)CFDictionaryGetValue(gObjectWeakRefsMap, obj);
        CFSetRemoveValue(set, ref);
    }
    
    static void ClearWeakRefsForObject(id obj)
    {
        CFMutableSetRef set = (void *)CFDictionaryGetValue(gObjectWeakRefsMap, obj);
        [(NSSet *)set makeObjectsPerformSelector: @selector(_zeroTarget)];
        CFDictionaryRemoveValue(gObjectWeakRefsMap, obj);
    }

Implementation of MAZeroingWeakRef
With those basics in place, I'll now take a top-down approach to the rest of the implementation.

First, the convenience constructor and initializer. Mostly straightforward:

    + (id)refWithTarget: (id)target
    {
        return [[[self alloc] initWithTarget: target] autorelease];
    }
    
    - (id)initWithTarget: (id)target
    {
        if((self = [self init]))
        {
            _target = target;
            RegisterRef(self, target);
        }
        return self;
    }

The only tricky bit is that call to RegisterRef. That's an internal utility function which takes care of connecting the weak reference object to the target object, subclassing the target's class if necessary, and changing the target's class to be the custom subclass.

The dealloc implementation similarly calls a utility function to remove the weak reference object:

    - (void)dealloc
    {
        UnregisterRef(self);
        [_cleanupBlock release];
        [super dealloc];
    }

Toss in a simple description method so we can see what's going on internally:

    - (NSString *)description
    {
        return [NSString stringWithFormat: @"<%@: %p -> %@>", [self class], self, [self target]];
    }

And a standard setter for setting the cleanup block:

    - (void)setCleanupBlock: (void (^)(id target))block
    {
        block = [block copy];
        [_cleanupBlock release];
        _cleanupBlock = block;
    }

The target method gets a little more complicated. Because the target can be destroyed at any time, it needs to fetch its value while holding the global weak reference lock. It also needs to retain the target while holding that lock, to ensure that, if the target is alive, it stays alive until the receiver is done using it. This is of course balanced with an autorelease afterwards:

    - (id)target
    {
        __block id ret;
        WhileLocked(^{
            ret = [_target retain];
        });
        return [ret autorelease];
    }

Finally there's a private method used to zero out the target, which is called by the internal machinery when the target object is deallocated. Since the global lock is already held by that machinery, there's no need to explicitly lock it here too. This method simply calls and releases the cleanup block if there is one, and clears out the target;

    - (void)_zeroTarget
    {
        if(_cleanupBlock)
        {
            _cleanupBlock(_target);
            [_cleanupBlock release];
            _cleanupBlock = nil;
        }
        _target = nil;
    }

And that's it! Easy, right? Of course, all the interesting bits are in those utility functions, the utility functions they call, and on and on....

Implementation of Utility Functions
The implementation of UnregisterRef is simple. Get the target out of the MAZeroingWeakRef, get the table of references to the target, and remove the given reference. Wrap it all in a lock to ensure that the target can't be deallocated in the middle of this operation:

    static void UnregisterRef(MAZeroingWeakRef *ref)
    {
        WhileLocked(^{
            id target = ref->_target;
            
            if(target)
                RemoveWeakRefFromObject(target, ref);
        });
    }

RegisterRef is similar. In addition to adding the reference to the table of references, it also calls EnsureCustomSubclass. That function will, if necessary, create a new custom subclass and set the class of the target object to that subclass.

    static void RegisterRef(MAZeroingWeakRef *ref, id target)
    {
        WhileLocked(^{
            EnsureCustomSubclass(target);
            AddWeakRefToObject(target, ref);
        });
    }

The implementation of EnsureCustomSubclass is broken into many pieces. First it checks to see if the object is already an instance of a custom subclass. If it is, then nothing has to be done. If it's not, it then looks up the custom subclass that corresponds to the object's current class, and sets the class of the target object accordingly. If no custom subclass has yet been created, it creates it.

    static void EnsureCustomSubclass(id obj)
    {
        if(!GetCustomSubclass(obj))
        {
            Class class = object_getClass(obj);
            Class subclass = [gCustomSubclassMap objectForKey: class];
            if(!subclass)
            {
                subclass = CreateCustomSubclass(class, obj);
                [gCustomSubclassMap setObject: subclass forKey: class];
                [gCustomSubclasses addObject: subclass];
            }
            object_setClass(obj, subclass);
        }
    }

The implementation of GetCustomSubclass is easy. Get the object's class, and check to see if it's in the gCustomSubclasses set. If not, get the superclass, and follow it up the chain until one is found. If none are found, then there is no custom subclass for this object. (The reason for following the chain is so that this code will still behave correctly even if some other code, such as Key-Value Observing, sets its own custom subclass after MAZeroingWeakRef set one.)

    static Class GetCustomSubclass(id obj)
    {
        Class class = object_getClass(obj);
        while(class && ![gCustomSubclasses containsObject: class])
            class = class_getSuperclass(class);
        return class;
    }

Again, not too hard. The real fun begins in CreateCustomSubclass. The first thing it does is check to see if the object is a CoreFoundation toll-free bridged object. As I discussed above, the subclassing approach breaks for those objects, so they need to be rejected:

    static Class CreateCustomSubclass(Class class, id obj)
    {
        if(IsTollFreeBridged(class, obj))
        {
            NSCAssert(0, @"Cannot create zeroing weak reference to object of type %@ with COREFOUNDATION_HACK_LEVEL set to %d", class, COREFOUNDATION_HACK_LEVEL);
            return class;
        }
        else
        {

(COREFOUNDATION_HACK_LEVEL is the #define which determines how much CoreFoundation hackery to enable. As I mentioned above, I'm going through the code as through it's not enabled.)

The implementation of IsTollFreeBridged simply checks to see if the class name starts with NSCF:

    static BOOL IsTollFreeBridged(Class class, id obj)
    {
        return [NSStringFromClass(class) hasPrefix: @"NSCF"];
    }

For the else branch, the first order of business is to create a name for the new class. Since Objective-C class names have to be unique, it constructs a new name based on the original name and a unique suffix:

            NSString *newName = [NSString stringWithFormat: @"%s_MAZeroingWeakRefSubclass", class_getName(class)];
            const char *newNameC = [newName UTF8String];

Next, call objc_allocateClassPair to create a new class pair. (In Objective-C, each class has a corresponding metaclass, which is related to how the runtime works. The objc_allocateClassPair function creates both in one shot.)

            Class subclass = objc_allocateClassPair(class, newNameC, 0);

The new class implements two methods, release and dealloc. The next step is then to add those two methods to the class, pointing them to the functions which implement them:

            Method release = class_getInstanceMethod(class, @selector(release));
            Method dealloc = class_getInstanceMethod(class, @selector(dealloc));
            class_addMethod(subclass, @selector(release), (IMP)CustomSubclassRelease, method_getTypeEncoding(release));
            class_addMethod(subclass, @selector(dealloc), (IMP)CustomSubclassDealloc, method_getTypeEncoding(dealloc));

Finally, call objc_registerClassPair to register the new class with the runtime, and return the newly created class:

            objc_registerClassPair(subclass);
            
            return subclass;
        }
    }

Next, CustomSubclassRelease. Conceptually, the implementation of this class is simple. Acquire the global weak reference lock, and call [super release] while it's acquired. The purpose of this is to ensure that the final release for an object and its deallocation happens atomically, and an object can't be resurrected in between the two by a weak reference that hasn't yet been zeroed out.

The trouble is that simply writing [super release] won't work, because the compiler only allows that in a true, compile-time method implementation. In order to perform the equivalent action, it's necessary to figure out the superclass of the custom weak reference subclass. This is done using a simple helper function which calls GetCustomSubclass and returns the superclass of that class:

    static Class GetRealSuperclass(id obj)
    {
        Class class = GetCustomSubclass(obj);
        NSCAssert(class, @"Coudn't find ZeroingWeakRef subclass in hierarchy starting from %@, should never happen", object_getClass(obj));
        return class_getSuperclass(class);
    }

With that helper in place, the implementation of CustomSubclassRelease can use it to look up the superclass, use that to look up the superclass's implementation of release, and then call that with the lock held:

    static void CustomSubclassRelease(id self, SEL _cmd)
    {
        Class superclass = GetRealSuperclass(self);
        IMP superRelease = class_getMethodImplementation(superclass, @selector(release));
        WhileLocked(^{
            ((void (*)(id, SEL))superRelease)(self, _cmd);
        });
    }

Almost done! The one remaining function is CustomSubclassDealloc. It gets the table of weak references to the object and tells all of them to _zeroTarget. It then invokes the superclass implementation of dealloc using the same technique as CustomSubclassRelease uses.

    static void CustomSubclassDealloc(id self, SEL _cmd)
    {
        ClearWeakRefsForObject(self);
        Class superclass = GetRealSuperclass(self);
        IMP superDealloc = class_getMethodImplementation(superclass, @selector(dealloc));
        ((void (*)(id, SEL))superDealloc)(self, _cmd);
    }

That's it! You now have zeroing weak references to Objective-C objects (except to bridged CoreFoundation objects, which I'll get to next week).

Examples:
Basic usage of MAZeroingWeakRef is simple:

    NSAutoreleasePool *pool = [[NSAutoreleasePool alloc] init];
    NSObject *obj = [[NSObject alloc] init];
    MAZeroingWeakRef *ref = [[MAZeroingWeakRef alloc] initWithTarget: obj];
    
    NSLog(@"%@", [ref target]);
    [obj release];
    [pool release];
    
    NSLog(@"%@", [ref target]);

The first NSLog will print the object, and the second will print (null). The autorelease pool is used to ensure that the object is truly destroyed, because the use of target will put the object into the pool and otherwise it will stay alive longer.

Using a cleanup block is similarly simple:

    NSObject *obj = [[NSObject alloc] init];
    MAZeroingWeakRef *ref = [[MAZeroingWeakRef alloc] initWithTarget: obj];
    [ref setCleanupBlock: ^(id target) { NSLog(@"Cleaned object %p!", target); }];
    [obj release];

The log will print when [obj release] is called. Of course you can take more actions than simply printing. However, because the cleanup block is called while the global weak reference lock is held, you should try to keep your activities in there to a minimum. If you need to do a lot of work, set up a deferred call, using performSelectorOnMainThread:, GCD, NSOperationQueue, etc. and do the extra work there.

A simple way to turn a regular instance variable into a zeroing weak reference is to use MAZeroingWeakRef in your getter and setter, and then make sure to always use your getter in other code:

    // ivar
    MAZeroingWeakRef *_somethingWeakRef;
    
    // accessors
    - (void)setSomething: (Something *)newSomething
    {
        [_somethingWeakRef release];
        _somethingWeakRef = [[MAZeroingWeakRef alloc] initWithTarget: newSomething];
    }
    
    - (Something *)something
    {
        return [_somethingWeakRef target];
    }
    
    // use
    - (void)doThing
    {
        [[self something] doThingWithObject: self];
    }

And of course if you do that, you have to be sure to release your reference in -dealloc, just like any other object you allocate. Just don't release the target.

For a more advanced use, here's an addition to NSNotificationCenter that eliminates the need to manually remove an observer in dealloc:

    @implementation NSNotificationCenter (MAZeroingWeakRefAdditions)
    
    - (void)addWeakObserver: (id)observer selector: (SEL)selector name: (NSString *)name object: (NSString *)object
    {
        [self addObserver: observer selector: selector name: name object: object];
        
        MAZeroingWeakRef *ref = [[MAZeroingWeakRef alloc] initWithTarget: observer];
        [ref setCleanupBlock: ^(id target) {
            [self removeObserver: target name: name object: object];
            [ref autorelease];
        }];
    }
    
    @end

Note the use of a cleanup block to remove the notification observer when the object is destroyed. All you have to do is call addWeakObserver: instead of addObserver: in notification observers, and you'll never again forget to remove an observer in dealloc.

Similarly, if you're tired of mysterious crashes caused by NSTableView data sources being deallocated before the views themselves, you can easily fix it:

    @implementation NSTableView (MAZeroingWeakRefAdditions)
    
    - (void)setWeakDataSource: (id <NSTableViewDataSource>)source
    {
        [self setDataSource: source];
        
        MAZeroingWeakRef *ref = [[MAZeroingWeakRef alloc] initWithTarget: observer];
        [ref setCleanupBlock: ^(id target) {
            if([self dataSource] == target) // double check for safety
                [self setDataSource: nil];
            [ref autorelease];
        }];
    }
    
    @end

If you anticipate a scenario where you change the data source of a table view frequently, you'll want to write some more sophisticated code to clear out the old weak reference when adding a new one. However that is not a common scenario.

Essentially, any time you have a weak reference (an object reference that you don't retain or copy), you should use a MAZeroingWeakRef instead of a raw unretained pointer. It will save you trouble and pain and is extremely easy to use.

ZeroingCollections
The repository includes MAWeakArray and MAWeakDictionary, subclasses of NSMutableArray and NSMutableDictionary which use zeroing weak references to their contents. MAWeakDictionary uses strong keys to weak objects, which would be useful for many caching scenarios. I won't go through their code here, but they're simple, and you can look at the code in the repository if you're curious.

Although I didn't write them, it would be possible to creat a weak version of NSMutableSet and NSMutableDictionary which uses weak keys instead of, or in addition to, weak objects. These would be trickier due to hashing/equality issues with the weak references, but could certainly be done.

Conclusion
Zeroing weak references are an extremely useful construct present in many languages. Even Objective-C has them when running under garbage collection, but without GC, Objective-C code has been stuck using non-zeroing weak references, which are tricky and dangerous.

MAZeroingWeakRef brings zeroing weak references to manual memory managed Objective-C. Although it uses some trickery on the inside, the API is extremely simple to use. By automatically zeroing weak references, you avoid many potential crashers and data corruption. Zeroing weak references can also be used for things like object caches where non-zeroing weak references aren't very practical at all.

The code is made available under a BSD license.

For the next Friday Q&A in two weeks, I will discuss how MAZeroingWeakRef works around the problems with CoreFoundation objects. Until then, enjoy!

Friday Q&A 2010-07-02: Background Timers

Fri, 02 Jul 2010 16:45:00 GMT

Friday Q&A 2010-07-02: Background Timers

Welcome back to another Friday Q&A. This week I'm departing from my usual user-driven format to present a class I've written for what I'm calling "background timers", and discuss potential uses for it.

Periodic Cleanup
To understand the usefulness of background timers, it's important to understand what kind of problem they're trying to solve.

It's common to have a class which needs to perform some sort of periodic cleanup or dumping. For example, buffered file IO (as done by e.g. printf) requires occasionally flushing the buffer to the file. A cache may want to occasionally evict old entries.

As one concrete example, consider an implementation of NSMutableArray. The array needs to manage storage for its contents, which it allocates with malloc. When an object is added that exceeds the current storage size, it uses realloc to grow the array. When it shrinks enough to justify it, it uses realloc to shrink the array.

The key is "enough to justify it". When is it enough?

One strategy would be to shrink it every time the current allocation was less than half full. However, imagine that you remove a lot of elements, but leave the array at one element over half full, then let it sit for a long time. You're wasting a lot of space! You could reduce the potential for wasted space by, say, shrinking any time the array is less than 90% full. But that can be inefficient if you're removing a lot of elements right away, or add and remove a lot of objects at a size that causes the array to constantly shrink and then re-grow.

Another strategy would be to shrink it every so many calls, say, every 100 calls. This could be combined with the above so that it would only shrink when there was enough wasted space to justify it. But this, too, could cause a lot of unnecessary shrinking and re-growing with an unfriendly access pattern, or a lot of wasted space if you suddenly leave the array idle on call #99.

Yet another strategy would be to base the decision not on fullness or calls, but on time. Check the array, say, once every half-second while it's in active use. If needed, resize the array. If the array isn't being used, nothing happens.

The natural way to implement this strategy would be with NSTimer. Whenever an object is removed from the array, check to see if a timer exists, and if it doesn't, create one with a half-second delay. When the timer fires, resize the array if it's necessary.

Trouble is, NSTimer requires an active runloop. If the array is manipulated a lot without returning to the runloop, it won't resize during that period. Worse, if the array is manipulated on a thread that doesn't have an active runloop, it will never resize.

To fix this, you'd want the timer to run on some sort of dedicated background thread. And you'd want to make sure that your normal array code was synchronized with that background thread so that all of your data access was safe.

Of course, Mac OS X already has an API that lets you do work on background threads and synchronize accesses with them: Grand Central Dispatch. GCD even includes timers, although they're not 100% what's wanted here.

Thus, I created a class, MABGTimer. It wraps GCD timers to provide the functionality needed to perform these periodic maintenance tasks based on time and in the background.

Code
As usual, you can get the code that goes along with this post from my public subversion repository:

    svn co http://mikeash.com/svn/BackgroundTimer/

Or just click on the link above to browse it.

API
The key public methods of MABGTimer are:

    - (void)afterDelay: (NSTimeInterval)delay do: (void (^)(id self))block;
    - (void)performWhileLocked: (void (^)(void))block;
    - (void)cancel;

After creating the timer, you set up a task by calling afterDelay:do:. You give it a delay, and a block to perform after that delay passes. If you call this method multiple times before the delay expires, the timer is either extended or coalesced, depending on settings.

Notice that the block passed to afterDelay:do: takes a parameter called self. The idea is that MABGTimer is initialized with a pointer to the object it's supposed to operate on, and it then passes a pointer to that object as a parameter to the block.

You might wonder, what's the point? After all, the block could simply capture self from the enclosing scope. That's what blocks are all about, after all.

The reason for the self parameter is that capturing self from the enclosing scope sets up a retain cycle. The object will be kept alive by the block until the timer fires. MABGTimer keeps a weak reference to the object, so that it can be destroyed at any time. When it is, the object can cancel the timer using the cancel method. This allows an object to set up long-term maintenance tasks and then cancel them early if the object is destroyed and no longer needs to perform them. MABGTimer then passes that weak reference into the block so it can use the original object without forcing a strong reference.

(Note: it is possible to give the block a weak reference to something in the enclosing scope by declaring a local variable with the __block qualifier and capturing that. However, that's more work than simply having a parameter passed in that you can use, so MABGTimer does a little extra work to make the client's job easier.)

As I mentioned above, since the timer executes in the background, synchronization is important. The performWhileLocked: method takes care of synchronization. Any time you do something with data that is also accessed in the timer block, wrap that code in a call to performWhileLocked:, and the timer will ensure that access is synchronized.

To clarify, here's an example of how these methods might be used:

    // do some work with non-shared data
    _someIvar++;
    [_someOtherIvar addObject: parameter];
    
    // do some work with timer-accessed data
    __block id resultObject;
    [_timer performWhileLocked: ^{
        // retain here to ensure the object stays live, since
        // this is multithreaded!
        resultObject = [[_cache objectForKey: parameter] retain];
    }];
    // balance the retain
    [resultObject autorelease];
    
    // clean the cache periodically
    [_timer afterDelay: 1.0 do: ^(id self) {
        // DON'T directly access ivars here
        // that will implicitly capture self, and cause a retain cycle
        [self _flushCache];
    }];
    
    return resultObject;

Behaviors
Each call to afterDelay:do: does not necessarily result in an invocation of the block passed in. If it's called multiple times before the timer fires, the block is only called once. This means that you should pass the same block each time; if they do different things, some of those things won't get done!

What exactly happens when you call it multiple times depends on how the timer was configured. This is done using behaviors, and I currently implement two.

When set with the coalesce behavior, the timer fires at the earliest time specified by the calls. In other words, calling with 2 seconds and then with 1 second will fire after 1 second. Calling with 10 seconds, then waiting 1 second, then calling with 5 seconds, will fire at the 6-second mark.

Coalesce is good for periodic maintenance tasks. You can call the timer many times, and it will fire periodically as needed. By passing different delays into the timer, you can handle events with varying urgency. For example, if you write some very low-priority data to a file handle, you might specify a 60-second delay. If you write high-priority data, you might specify a 0.1-second delay. MABGTimer will intelligently combine those so that high-priority data following low-priority data will flush the entire cache.

When set with the delay behavior, the timer's firing time is reset with each call. This essentially implements an idle timer. As long as your class is active, the timer will continue to reset, but after it's quiet for a while, it will fire. This could be used to implement a GUI control which refreshes an expensive view only when the mouse has stopped moving.

Behaviors are specified when creating the timer object using this method:

    - (id)initWithObject: (id)obj behavior: (MABGTimerBehavior)behavior;

There is also a convenience initializer:

    - (id)initWithObject: (id)obj;

This defaults to coalesce behavior, because I think it's the more common one.

Target Queue
There's also one method for advanced GCD users:

    - (void)setTargetQueue: (dispatch_queue_t)target;

This allows you to specify a dispatch queue where the MABGTimer will execute its code. This includes the timer block as well as the block passed to performWhileLocked:.

By default, MABGTimer runs everything on a private queue targeted to the default-priority global queue. This method could be used to retarget it to a global queue of different priority, to another private queue (to manage suspension behavior) or even to the main queue so you can do GUI work in the timer.

Implementation
MABGTimer has the following instance variables, which should be self-explanatory:

    id _obj;
    dispatch_queue_t _queue;
    dispatch_source_t _timer;
    MABGTimerBehavior _behavior;
    NSTimeInterval _nextFireTime;

The initializers and dealloc are also pretty simple:

    - (id)initWithObject: (id)obj
    {
        return [self initWithObject: obj behavior: MABGTimerCoalesce];
    }
    
    - (id)initWithObject: (id)obj behavior: (MABGTimerBehavior)behavior
    {
        if((self = [super init]))
        {
            _obj = obj;
            _behavior = behavior;
            _queue = dispatch_queue_create("com.mikeash.MABGTimer", NULL);
        }
        return self;
    }
    
    - (void)dealloc
    {
        if(_timer)
        {
            dispatch_source_cancel(_timer);
            dispatch_release(_timer);
        }
        dispatch_release(_queue);
        [super dealloc];
    }

And setTargetQueue: and performWhileLocked:just call through to the appropriate dispatch function:

    - (void)setTargetQueue: (dispatch_queue_t)target
    {
        dispatch_set_target_queue(_queue, target);
    }
    
    - (void)performWhileLocked: (dispatch_block_t)block
    {
        dispatch_sync(_queue, block);
    }

The cancel method calls through to an internal _cancel method that's run on the queue. This ensures that cancellation is synchronized with timer activity:

    - (void)cancel
    {
        [self performWhileLocked: ^{
            [self _cancel];
        }];
    }

And the _cancel method is also simple: if the timer is active, cancel it and destroy it:

    - (void)_cancel
    {
        if(_timer)
        {
            dispatch_source_cancel(_timer);
            dispatch_release(_timer);
            _timer = NULL;
        }
    }

The meat of the functionality is in afterDelay:do:. The first thing it does is run everything synchronized to avoid race conditions and the like:

    - (void)afterDelay: (NSTimeInterval)delay do: (void (^)(id self))block
    {
        [self performWhileLocked: ^{

It then checks to see whether it needs to reset the timer or not. It needs to reset the timer if the GCD timer doesn't exist (no pending fire has been set up), if the timer is in delay mode, or if the timer is in coalesce mode and the new fire time is before the previous fire time:

            BOOL hasTimer = _timer != nil;
            
            BOOL shouldProceed = NO;
            if(!hasTimer)
                shouldProceed = YES;
            else if(_behavior == MABGTimerDelay)
                shouldProceed = YES;
            else if(_behavior == MABGTimerCoalesce && [self _now] + delay < _nextFireTime)
                shouldProceed = YES;

Next, if the timer needs to be reset and the GCD timer doesn't exist, create it:

            if(shouldProceed)
            {
                if(!hasTimer)
                    _timer = dispatch_source_create(DISPATCH_SOURCE_TYPE_TIMER, 0, 0, _queue);

Then it first sets the GCD timer and the _nextFireTime instance variable:

                dispatch_source_set_timer(_timer, dispatch_time(DISPATCH_TIME_NOW, delay * NSEC_PER_SEC), 0, 0);
                _nextFireTime = [self _now] + delay;

Then it sets the event handler on the timer. The event handler first calls the block that's passed in. Since GCD timers are always repeating, it then calls _cancel to make sure it only fires once, and also to signal to any future calls that the timer is no longer active:

                dispatch_source_set_event_handler(_timer, ^{
                    block(_obj);
                    [self _cancel];
                });

Finally, if the timer was newly created, resume it so it can become active:

                if(!hasTimer)
                    dispatch_resume(_timer);
            }
        }];
    }

One last thing, we need an implementation of the _now method. This is simple: call mach_absolute_time, convert it to seconds:

    - (NSTimeInterval)_now
    {
        uint64_t t = mach_absolute_time();
        Nanoseconds nano = AbsoluteToNanoseconds(*(AbsoluteTime *)&t);
        NSTimeInterval seconds = (double)*(uint64_t *)&nano / (double)NSEC_PER_SEC;
        return seconds;
    }

Conclusion
Background timers are a useful technique for decoupling the timing of calls to an API from the tasks it performs. The repository contains BackgroundResizingArray, an implementation of NSMutableArray which uses a background timer to implement resizing. Background timers can be useful for networking as well, especially on iOS devices where you want to batch up transmissions to reduce power usage on the cellular radio, or any case where you have a lot of non-urgent messages to send.

That's it for this Friday Q&A. Check back in another two weeks for more gooey goodness. Friday Q&A is driven by reader suggestions (mostly), so if you have an idea for a topic you would like to see covered here, send it in!

Blocks and GCD in Russian

Tue, 29 Jun 2010 15:22:00 GMT

Blocks and GCD in Russian

Alexander Babaev has been kind enough to translate my series of posts on blocks and GCD into Russian for TouchDev.ru. So far he has posted two, Blocks in Objective-C and Intro to Grand Central Dispatch, Part I. Others in the series will be going up in the future. If you happen to speak Russian, check them out!

Friday Q&A 2010-06-18: Implementing Equality and Hashing

Fri, 18 Jun 2010 14:48:00 GMT

Friday Q&A 2010-06-18: Implementing Equality and Hashing

Welcome back to a late edition of Friday Q&A. WWDC pushed the schedule back one week, but it's finally time for another one. This week, I'm going to discuss the implementation of equality and hashing in Cocoa, a topic suggested by Steven Degutis.

Equality
Object equality is a fundamental concept that gets used all over the place. In Cocoa, it's implemented with the isEqual: method. Something as simple as [array indexOfObject:] will use it, so it's important that your objects support it.

It's so important that Cocoa actually gives us a default implementation of it on NSObject. The default implementation just compares pointers. In other words, an object is only equal to itself, and is never equal to another object. The implementation is functionally identical to:

    - (BOOL)isEqual: (id)other
    {
        return self == other;
    }

While oversimplified in many cases, this is actually good enough for a lot of objects. For example, an NSView is never considered equal to another NSView, only to itself. For NSView, and many other classes which behave that way, the default implementation is enough. That's good news, because it means that if your class has that same equality semantic, you don't have to do anything, and get the correct behavior for free.

Implementing Custom Equality
Sometimes you need a deeper implementation of equality. It's common for objects, typically what you might refer to as a "value object", to be distinct from another object but be logically equal to it. For example:

    // use mutable strings because that guarantees distinct objects
    NSMutableString *s1 = [NSMutableString stringWithString: @"Hello, world"];
    NSMutableString *s2 = [NSMutableString stringWithFormat: @"%@, %@", @"Hello", @"world"];
    BOOL equal = [s1 isEqual: s2]; // gives you YES!

Of course NSMutableString implements this for you in this case. But what if you have a custom object that you want to be able to do the same thing?

    MyClass *c1 = ...;
    MyClass *c2 = ...;
    BOOL equal = [c1 isEqual: c2];

In this case you need to implement your own version of isEqual:.

Testing for equality is fairly straightforward most of the time. Gather up the relevant properties of your class, and test them all for equality. If any of them are not equal, then return NO. Otherwise, return YES.

One subtle point with this is that the class of your object is an important property to test as well. It's perfectly valid to test a MyClass for equality with an NSString, but that comparison should never return YES (unless MyClass is a subclass of NSString, of course).

A somewhat less subtle point is to ensure that you only test properties that are actually important to equality. Things like caches that do not influence your object's externally-visible value should not be tested.

Let's say your class looks like this:

    @interface MyClass : NSObject
    {
        int _length;
        char *_data;
        NSString *_name;
        NSMutableDictionary *_cache;
    }

Your equality implementation would then look like this:

    - (BOOL)isEqual: (id)other
    {
        return ([other isKindOfClass: [MyClass class]] &&
                [other length] == _length &&
                memcmp([other data], _data, _length) == 0 &&
                [[other name] isEqual: _name])
                // note: no comparison of _cache
    }

Hashing
Hash tables are a commonly used data structure which are used to implement, among other things, NSDictionary and NSSet. They allow fast lookups of objects no matter how many objects you put in the container.

If you're familiar with how hash tables work, you may want to skip the next paragraph or two.

A hash table is basically a big array with special indexing. Objects are placed into an array with an index that corresponds to their hash. The hash is essentially a pseudorandom number generated from the object's properties. The idea is to make the index random enough to make it unlikely for two objects to have the same hash, but have it be fully reproducible. When an object is inserted, the hash is used to determine where it goes. When an object is looked up, its hash is used to determine where to look.

In more formal terms, the hash of an object is defined such that two objects have an identical hash if they are equal. Note that the reverse is not true, and can't be: two objects can have an identical hash and not be equal. You want to try to avoid this as much as possible, because when two unequal objects have the same hash (called a collision) then the hash table has to take special measures to handle this, which is slow. However, it's provably impossible to avoid it completely.

In Cocoa, hashing is implemented with the hash method, which has this signature:

    - (NSUInteger)hash;

As with equality, NSObject gives you a default implementation that just uses your object's identity. Roughly speaking, it does this:

    - (NSUInteger)hash
    {
        return (NSUInteger)self;
    }

The actual value may differ, but the essential point is that it's based on the actual pointer value of self. And just as with equality, if object identity equality is all you need, then the default implementation will do fine for you.

Implementing Custom Hashing
Because of the semantics of hash, if you override isEqual: then you must override hash. If you don't, then you risk having two objects which are equal but which don't have the same hash. If you use these objects in a dictionary, set, or something else which uses a hash table, then hilarity will ensue.

Because the definition of the object's hash follows equality so closely, the implementation of hash likewise closely follows the implementation of isEqual:.

An exception to this is that there's no need to include your object's class in the definition of hash. That's basically a safeguard in isEqual: to ensure the rest of the check makes sense when used with a different object. Your hash is likely to be very different from the hash of a different class simply by virtue of hashing different properties and using different math to combine them.

Generating Property Hashes
Testing properties for equality is usually straightforward, but hashing them isn't always. How you hash a property depends on what kind of object it is.

For a numeric property, the hash can simply be the numeric value.

For an object property, you can send the object the hash method, and use what it returns.

For data-like properties, you'll want to use some sort of hash algorithm to generate the hash. You can use CRC32, or even something totally overkill like MD5. Another approach, somewhat less speedy but easy to use, is to wrap the data in an NSData and ask it for its hash, essentially offloading the work onto Cocoa. In the above example, you could compute the hash of _data like so:

    [[NSData dataWithBytes: _data length: _length] hash]

Combining Property Hashes
So you know how to generate a hash for each property, but how do you put them together?

The easiest way is to simply add them together, or use the bitwise xor property. However, this can hurt your hash's uniqueness, because these operations are symmetric, meaning that the separation between different properties gets lost. As an example, consider an object which contains a first and last name, with the following hash implementation:

    - (NSUInteger)hash
    {
        return [_firstName hash] ^ [_lastName hash];
    }

Now imagine you have two objects, one for "George Frederick" and one for "Frederick George". They will hash to the same value even though they're clearly not equal. And, although hash collisions can't be avoided completely, we should try to make them harder to obtain than this!

How to best combine hashes is a complicated subject without any single answer. However, any asymmetric way of combining the values is a good start. I like to use a bitwise rotation in addition to the xor to combine them:

    #define NSUINT_BIT (CHAR_BIT * sizeof(NSUInteger))
    #define NSUINTROTATE(val, howmuch) ((((NSUInteger)val) << howmuch) | (((NSUInteger)val) >> (NSUINT_BIT - howmuch)))
    
    - (NSUInteger)hash
    {
        return NSUINTROTATE([_firstName hash], NSUINT_BIT / 2) ^ [_lastName hash];
    }

Custom Hash Example
Now we can take all of the above and use it to produce a hash method for the example class. It follows the basic form of the equality method, and uses the above techniques to obtain and combine the hashes of the individual properties:

    - (NSUInteger)hash
    {
        NSUInteger dataHash = [[NSData dataWithBytes: _data length: _length] hash];
        return NSUINTROTATE(dataHash, NSUINT_BIT / 2) ^ [_name hash];
    }

If you have more properties, you can add more rotation and more xor operators, and it'll work out just the same. You'll want to adjust the amount of rotation for each property to make each one different.

A Note on Subclassing
You have to be careful when subclassing a class which implements custom equality and hashing. In particular, your subclass should not expose any new properties which equality is dependent upon. If it does, then it must not compare equal with any instances of the superclass.

To see why, consider a subclass of the first/last name class which includes a birthday, and includes that as part of its equality computation. It can't include it when comparing equality with an instance of the superclass, though, so its equality method would look like this:

    - (BOOL)isEqual: (id)other
    {
        // if the superclass doesn't like it then we're not equal
        if(![super isEqual: other])
            return NO;
        
        // if it's not an instance of the subclass, then trust the superclass
        // it's equal there, so we consider it equal here
        if(![other isKindOfClass: [MySubClass class]])
            return YEs;
        
        // it's an instance of the subclass, the superclass properties are equal
        // so check the added subclass property
        return [[other birthday] isEqual: _birthday];
    }

Now you have an instance of the superclass for "John Smith", which I'll call A, and an instance of the subclass for "John Smith" with a birthday of 5/31/1982, which I'll call B. Because of the definition of equality above, A equals B, and B also equals itself, which is expected.

Now consider an instance of the subclass for "John Smith" with a birthday of 6/7/1994, which I'll call C. C is not equal to B, which is what we expect. C is equal to A, also expected. But now there's a problem. A equals both B and C, but B and C do not equal each other! This breaks the standard transitivity of the equality operator, and leads to extremely unexpected results.

In general this should not be a big problem. If your subclass adds properties which influence object equality, that's probably an indication of a design problem in your hierarchy anyway. Rather than working around it with weird implementations of isEqual:, consider redesigning your class hierarchy.

A Note on Dictionaries
If you want to use your object as a key in an NSDictionary, you need to implement hashing and equality, but you also need to implement -copyWithZone:. Techniques for doing that are beyond the scope of today's post, but you should be aware that you need to go a little bit further in that case.

Conclusion
Cocoa provides default implementations of equality and hashing which work for many objects, but if you want your objects to be considered equal even when they're distinct objects in memory, you have to do a bit of extra work. Fortunately, it's not difficult to do, and once you implement them, your class will work seamlessly with many Cocoa collection classes.

That's it for this week. Check back in two more weeks for another edition. Until then, keep sending me your requests for topics. Friday Q&A is driven by user submissions, so if you have an idea for a topic to cover here, please send it in.

Friday Q&A 2010-05-28: Leopard Collection Classes

Fri, 28 May 2010 16:43:00 GMT

Friday Q&A 2010-05-28: Leopard Collection Classes

Welcome back to another edition of Friday Q&A. For this week's post, I'm going to talk about three somewhat obscure collections classes that were introduced to Cocoa in 10.5: NSPointerArray, NSHashTable, and NSMapTable, a topic suggested by Phil Holland.

Introduction
These classes were introduced in 10.5 and it appears that their main purpose was to add some useful capabilities for the newly-introduced Cocoa garbage collection support. However, they add a lot of other useful capabilities beyond that as well.

Each of these classes is the counterpart of a more traditional Foundation collection class. NSPointerArray is the counterpart of NSArray, NSHashTable is the counterpart of NSSet, and NSMapTable is the counterpart of NSDictionary. They are not identical, but share a lot of behaviors, and are the same basic kind of container.

One nice feature of Cocoa garbage collection (and many other collectors) is zeroing weak references. These are references to an object which don't keep that object alive. Instead, they point to the object while it's alive, but if and when it gets garbage collected, the collector zeroes out the reference. This can be really useful for object caches, parent-child object relationships, automatic deregistration of observers and others.

Individual weak references are easy to use: simply prepend __weak to an object pointer variable's type and that variable becomes a weak reference. (Note: this does not work for local variables.) The standard collections all hold strong references to their contents. One of the reasons for these new collection classes was that they can be configured to hold weak references to their contents, greatly expanding the uses for weak references.

These classes are also much more flexible in general. They can hold NULL values, they can be configured to hold opaque non-object pointers, plain integers, or even pointers to memory with custom comparison/destruction operations.

NSPointerArray
This class is a lot like an NSMutableArray, but with the id objects replaced with void *, and many fewer convenience functions.

The major difference from NSMutableArray is in how you create a new NSPointerArray. The class has two initializers:

    - initWithOptions:(NSPointerFunctionsOptions)options;
    - initWithPointerFunctions:(NSPointerFunctions *)functions;

This is where the flexibility comes in. The parameters for these initialiers allow you to fully specify how the NSPointerArray treats its contents. You can use an NSPointerArray any time you want an NSArray that points to special kinds of objects or otherwise needs special treatment.

NSPointerFunctions
NSPointerFunctions is a class whose main purpose is to hold a bunch of function pointers. There are function pointers for hashing, equality, memory management, and more. There are also two flags you can set to have it use different garbage collection read/write barriers. By stuffing function pointers into this class, you can specify how everything works.

Let's build an example. We'll create an NSPointerFunctions object that deals in pointers to integers. Not too useful, but a good exercise.

The first thing to do is to define all of the various functions that will be needed. Hashing is easy, just return the integer that the pointer points to:

    static NSUInteger Hash(const void *item, NSUInteger (*size)(const void *item))
    {
        return *(const int *)item;
    }

Equality is just as easy, dereference both pointers and compare:

    static BOOL IsEqual(const void *item1, const void *item2, NSUInteger (*size)(const void *item))
    {
        return *(const int *)item1 == *(const int *)item2;
    }

Note the final size parameter to both functions. If necessary, this will get the size of the pointed-to object. We already know the size, so there's no need to use it. Since it's unnecessary, I won't provide a size function to the NSPointerFunctions object either.

For the description, we just return a simple string using the integer obtained from dereferencing the pointer:

    static NSString *Description(const void *item)
    {
        return [NSString stringWithFormat: @"%d", *(const int *)item];
    }

Relinquish and acquire are a bit trickier. They assume reference counting memory management, but I want to use plain malloc and free. I decided to just have relinquish always free the item, and acquire return a copy. The relinquish function is simple:

    static void Relinquish(const void *item, NSUInteger (*size)(const void *item))
    {
        free((void *)item);
    }

The acquire function isn't much more complicated. It mallocs some new memory, copies the value, and returns the new pointer:

    static void *Acquire(const void *src, NSUInteger (*size)(const void *item), BOOL shouldCopy)
    {
        int *newPtr = malloc(sizeof(int));
        *newPtr = *(const int *)src;
        return newPtr;
    }

And now with all of this in place, we can create a new NSPointerFunctions, and a new NSPointerArray from it:

    NSPointerFunctions *functions = [[NSPointerFunctions alloc] init];
    [functions setHashFunction: Hash];
    [functions setIsEqualFunction: IsEqual];
    [functions setDescriptionFunction: Description];
    [functions setRelinquishFunction: Relinquish];
    [functions setAcquireFunction: Acquire];
    
    NSPointerArray *array = [NSPointerArray pointerArrayWithPointerFunctions: functions];
    
    int one = 1, two = 2, three = 3;
    [array addPointer: &one];
    [array addPointer: &two];
    [array addPointer: &three];

And it all works.

NSPointerOptions
It may work, but that was a gigantic hassle. Fortunately, Apple has provided a bunch of pre-baked NSPointerFunctions to work with. These can be accessed by using NSPointerFunctionsOptions constants.

NSPointerFunctionsOptions is composed of three parts. There are memory options, personalities, and flags.

Memory options determine memory management. Using NSPointerFunctionsStrongMemory will get you the behavior of the more standard Foundation collection classes: a strong reference for garbage collection, and a retained reference for manual memory management. NSPointerFunctionsZeroingWeakMemory will get you zeroing weak references under garbage collection and, I believe, a non-retained reference under manual memory management.There are also options for malloc/free management, for Mach virtual memory, and for completely ignoring memory management.

Personalities determine hashing and equality. NSPointerFunctionsObjectPersonality provides the standard Foundation behavior of using hash and isEqual:. You can also use NSPointerFunctionsObjectPointerPersonality, which treats the contents as objects, but uses direct pointer value comparison; this is useful if you need a collection to work with object identity rather than value. NSPointerFunctionsIntegerPersonality allows storing pointer-sized integers directly in the container. Note that unlike the toy example above, this doesn't deal with pointers to integers, but rather integers directly, like storing (void *)42. This is useful if you need a collection that stores integers and don't want the code and runtime overhead of packing the integers into objects.

Apple has only given us one flag at the moment: NSPointerFunctionsCopyIn. When set, this flag will cause newly inserted pointers to be copied rather than simply retained. What exactly this means will depend on the personality set, but in the case of object personalities, it will use NSCopying.

Some examples:

Strong references with copied objects using object value comparison: NSPointerFunctionsStrongMemory | NSPointerFunctionsObjectPersonality | NSPointerFunctionsCopyIn.
Zeroing weak references and object identity: NSPointerFunctionsZeroingWeakMemory | NSPointerFunctionsObjectPointerPersonality.
C strings stored in malloc memory, copied when inserted: NSPointerFunctionsMallocMemory | NSPointerFunctionsCStringPersonality | NSPointerFunctionsCopyIn.

As you can see, there's a lot of flexibility to be had here without ever having to define your own functions.

Now that you know how all of those work, let's look at the remaining two classes.

NSHashTable
NSHashTable is the rough equivalent of NSMutableSet. It's an unordered collection of objects, using hashing to allow for fast access. Again, the basic functionality is the same, but without some of the more advanced methods. And again, it has two initializers which take pointer functions and options.

There is one extra factory method on NSHashTable:

    + (id)hashTableWithWeakObjects;

Apparently Apple thought that this was a common enough use to justify making it more convenient to create a new object of this type.

Like NSPointerArray, you can use NSHashTable any time you want an NSSet but with some different capabilities in terms of how it treats its contents.

NSMapTable
NSMapTable is the final class of the three, and is the rough equivalent of NSDictionary. It's an unordered collection of key/object pairs, with fast access to the objects by looking them up through their keys. Like the others, it has the standard two initializers to tell it how to act.

NSMapTable also has four extra factory methods:

    + (id)mapTableWithStrongToStrongObjects;
    + (id)mapTableWithWeakToStrongObjects;
    + (id)mapTableWithStrongToWeakObjects;
    + (id)mapTableWithWeakToWeakObjects;

This gives you all four possible combinations of weak and strong.

As with the others, you can use NSMapTable in any case where you'd normally want an NSDictionary but need a little extra flexibility.

In particular, [NSMapTable mapTableWithStrongToStrongObjects will give you an object which behaves much like an NSDictionary but which doesn't copy its keys. This is useful in all kinds of situtaions, and can save a lot of headache.

Comparison with CoreFoundation
Those of you who are intimately familiar with CoreFoundation collections probably nodded a lot at the NSPointerFunctions stuff. CoreFoundation collections such as CFArray require nearly identical functions to determine how they treat their contents. Given this, what are the advantages of each?

The new Cocoa classes are largely useful because they're vastly more convenient to set up. CoreFoundation has no equivalent for a lot of the built-in NSPointerOptions functionality, which would require you to build them all yourself. There is not, as far as I know, any way to do zeroing weak references with CoreFoundation collections. Toll-free bridging is also inconsistent when it comes to custom behavior: you can build a CFDictionary with callbacks that don't copy their keys, but using [customDictionary setObject: obj forKey: key] will still copy the key even though you expressly told it not to! (For any Apple employees reading this, I've filed this as bug #4350677, and it was returned as "behaves correctly".)

Custom CoreFoundation collections can be better due to toll-free bridging, which allows you to treat them as standard NSArrays and so forth. However, you must be careful when passing these to code you don't own, as they may make assumptions about the behavior of the collection which your custom callbacks don't respect. And as noted above, the behavior of custom callbacks with toll-free bridging is inconsistent, so watch out!

All in all, each one has its place. In pure Cocoa code, the new Cocoa classes are generally more convenient and can be more powerful.

Conclusion
The new collection classes added to Cocoa in 10.5 are a powerful, flexible addition to Foundation. They easily allow useful behaviors like storing weak references and raw integers, or just creating an object map that doesn't copy its keys.

That's it for this Friday Q&A. Come back in another two weeks for the next one, unless I decide that working it in around WWDC is too much, in which case I'll shoot for the week after. And if you're going to WWDC too, say hi!

Some Light Reading

Fri, 21 May 2010 16:02:00 GMT

Some Light Reading

As I mentioned last week, I'm shifting Friday Q&A to a biweekly schedule, so there will be no Friday Q&A this week. However, I've dug up a few articles that I enjoyed reading this week and that I thought you might enjoy as well.

If Windows 3.11 required a 32-bit processor, why was it called a 16-bit operating system? - An interesting account of the surprisingly complicated low-level architecture of a classic operating system.
How do emulators work and how are they written? - Fantastic Stack Overflow answer discussing the internal workings of emulators.
An overview of how IntelliSense works - Another Stack Overflow answer, this one talking about how Visual Studio's IntelliSense feature works internally.
Start in the Middle - Great advice about how you should go straight to the meat of new projects and leave the boring framing stuff for later.
Reverse debugging with GDB 7 - Fascinating tutorial about a really cool new feature in the latest version of GDB.

SocketObjC: A Networkable Messaging Library

Mon, 17 May 2010 21:27:00 GMT

SocketObjC: A Networkable Messaging Library

Reader Steven Degutis was inspired by my post about Distributed Objects and decided to make something that avoided those pitfalls. The result is SocketObjC, a remote messaging library that uses continuation passing style to achieve full asynchronous messaging. I haven't tried it, but it's worth checking out.

Friday Q&A 2010-05-14: What Every Apple Programmer Should Know

Fri, 14 May 2010 15:36:00 GMT

Friday Q&A 2010-05-14: What Every Apple Programmer Should Know

Welcome back to another Friday Q&A. This week, Quentin Carnicelli (who is heavily involved in generating my paychecks) has suggested that I talk about things that every Apple programmer should know. In other words, common Cocoa design and implementation decisions that I'd prefer Apple not to make.

But First, a Brief Word from Our Sponsor
Before I get into the meat of the post, I have a bit of meta-business. While I greatly enjoy writing Friday Q&A and am humbled by the great feedback I get about it, it also represents a significant drain on my time that's becoming hard to sustain. Therefore, starting with this post, I will be scaling Friday Q&A back to a biweekly schedule. I'll be writing the same stuff in the same place, just not quite as often. I hope that what I'm taking away in quantity, I'll be able to make up for in quality.

And Now, Back to Our Show
While the theme of this article is common problems in Cocoa, I think this will also have a great deal of relevance to any Cocoa programmer as well. Ultimately, this will be a collection of common problems in API design and implementation, and large chunks of any real application count as APIs. While I really want Apple to follow these ideas, if you follow them as well, they should make your life much easier.

Without further ado, the list.

Always use [self class] when invoking your own class methods
A bunch of these boil down to making your code easier to subclass, and this is the first. If you hardcode your class when invoking a class method, it makes it impossible for a subclass to override that behavior. If that class method is public, then you've created a frustrating situation: the method exists, is published, can be overridden, but won't be called if you do, so you can't change the behavior.

Don't access instance variables directly if there's an accessor
This is much like the previous one. If there's an accessor, there's an expectation that you can override it in a subclass to alter the value which is used. If you access the instance variable directly, you bypass that override, making it impossible for subclasses to alter behavior. Even worse, if you use the accessor only sometimes, then you get bizarre inconsistent behavior that's easy to go wrong. Apple really loves to do this one, so as a user of Cocoa, be careful when subclassing and overriding accessors, and be prepared for them not to be called.

If components of functionality are exposed as public methods, the implementation should always call them when it needs that functionality
Yet another ease-of-subclassing item. Sometimes Apple provides a public method, but doesn't use it internally to accomplish the task it's built for. An example of this is NSSliderCell, which provides a drawBarInside:flipped: method, but which does its own bar drawing separately. If you want custom bar drawing, you either have to override a higher level drawing method, or you have to override the private _usesCustomTrackImage method to convince it to call your custom code. Another example is NSMutableURLRequest's setHTTPBodyStream: method. If you create a custom NSInputStream class and pass an instance of that custom class as the parameter, it won't work. You have to override the private _scheduleInCFRunLoop:forMode: method for the two components to work together. Subclasses should be able to override a public method to alter functionality, or work with existing APIs, without jumping through these hoops.

Don't write empty stub methods and then make them public
NSView has this nifty method:

    - (BOOL)lockFocusIfCanDrawInContext:(NSGraphicsContext *)context;

It's nifty until you read the documentation on it, which says, "This method was declared in Mac OS X v10.4, but is not used in that release. It currently does nothing and returns NO. However, it might be implemented in a future release."

It baffles me as to why this method is public. It's useless, so why have it at all? If they plan to implement it in the future, they could make it public once it's implemented. I can only assume that it was implemented as a stub with the intent to complete it, but then it slipped through the cracks.

Apple doesn't do this much, but suffice it to say that it shouldn't happen at all.

User data fields should be id
It's a common pattern to have "user data" as part of an API, which is just some arbitrary data which can be passed through a callback or attached to an object. Sometimes this is an object, but sometimes Cocoa presents user data as a void *. This greatly complicates memory management (especially when using garbage collection) to little benefit. The common case is to pass an object as user data, and the API should simplify that. For the rare cases where you want a different type of pointer, the programmer can always wrap it in an NSValue.

Make up your mind on what "thread safe" means
As I discussed in an earlier post, Apple is pretty inconsistent about what "thread safe" actually means. Sometimes it means any instance can be safely used from multiple threads simultaneously. Sometimes it means any instance can be used from one thread at a time, but that you must synchronize access. Sometimes that's described as "not thread safe" instead. It's tremendously confusing! The world is becoming heavily multithreaded, and we need more explicit descriptions of what these APIs require.

Make fewer APIs dependent on the main thread
The main thread is a huge bottleneck in a modern Cocoa app, because many APIs only work on the main thread. Most GUI manipulation can't be safely done off the main thread, even if you take care to cleanly keep each window on a single thread. Entire APIs, like WebKit, can only be used from the main thread. Fortunately, the situation is gradually improving.

Make every runloop API take a modes parameter
Do a google search for webview modal to see what the problem is here. WebView depends on a running runloop to do its processing, but it only runs in the default mode. If you want your WebView to remain functional while a modal window is running, you're out of luck. You should be able to easily schedule the WebView in the modal runloop mode, but the API isn't there, so you can't. While it's perfectly reasonable to schedule into one particular runloop mode by default, a runloop-dependent API should always provide for the ability to schedule on other modes too.

Make it easy to convert between different classes with similar capabilities
An example of this is NSImage and CGImage. Before Snow Leopard, there was no easy way to convert between the two, even though they were fairly similar. (Yes, NSImage can contain multiple representations, isn't necessarily pixel-based, etc. They're still conceptually close.) If you had one, and needed the other, it was a bunch of work to go from one to the other.

In 10.6, Apple added APIs to NSImage to make it easy to convert between them, and suddenly life became a lot easier.

Toll free bridging in CoreFoundation is the pinnacle of how to do this right. The objects are interoperable, and just require a cast to convince the compiler that you're not insane. While this isn't always possible, easy methods to do explicit conversion help enormously.

There are still areas where this is lacking. NSColor and CGColor are difficult to convert between. CFBundle and NSBundle are extremely similar but not interchangeable or convertible.

Don't pollute namespaces
One of the unfortunate things missing from Objective-C is namespaces. It's all too easy for components in a framework to conflict with components in an application. If you're building a framework, then you need to minimize the possibility of this happening as much as possible.

Always prefix class names with something that should be reasonably unique. This goes even for private classes. They can conflict and cause problems even though they're never exposed as part of your public API.

You also need to prefix category methods that aren't made public. If they aren't prefixed, there's a risk of conflict with other category methods. The same also goes for private methods.

Conclusion
Overall, Cocoa is a great API, but there are a few common problems which make things a little bit less smooth than they otherwise could be. The intent is not to bash Apple, but just show how things could be made a little bit better, and give some ways that the rest of us can make our own APIs better as well.

That's it for this edition of Friday Q&A. Again, the next one will now be in two weeks. Until then, keep sending in your ideas for posts. Friday Q&A is driven by user ideas, so if you have a topic you'd like to see covered here, get in touch.

iPhone Apps I Can't Have

Fri, 14 May 2010 02:46:00 GMT

iPhone Apps I Can't Have

During a recent discussion on Twitter about Apple's draconion App Store policies, I mentioned that there's a long list of apps I want which Apple does not allow, and thus these restrictions directly hurt me not only as a developer, but as an iPhone user. This made @pbur curious, and he indicated he'd like to know what those apps are. So I sat down and came up with a list of apps that I really want for my iPhone but that Apple won't let me have. To the best of my knowledge, every single one of these ideas is completely feasible in a technical sense, wouldn't destroy the cell network, wouldn't make your phone's battery life unusably short, and are kept out of my hands solely because Apple thinks it knows what's best for me.

Airfoil
I'm a little biased, of course, since the company I work for makes it, but I'd love to have Airfoil on the iPhone so I can send music directly to an AirPort Express, instead of having to leave my computer turned on and fart around with various substandard remote control solutions. It's impossible to get audio from other apps on the iPhone (even once multitasking happens in 4.0), and apps aren't even allowed to access the audio data in the user's music library. While Airfoil could conceivably be implemented to send audio, there no way for it to get any interesting audio for it to send.

Hardware brightness control in Kindle
This is a simple one, but also highly desirable. I much prefer Kindle to iBooks on the iPad, because Kindle lacks the distracting visual elements in iBooks, and also has a far superior selection. iBooks does have one nice feature that Kindle lacks: control over the strength of the backlight. Kindle fakes it by adjusting the background color, but it's nowhere near as good. The hardware brightness adjustment is a private API, which third parties like Amazon are prohibited from using. Of course, the rules do not apply to Apple.

Automatic pasteboard synchronization
I often use my iPhone/iPad at home while also using my Mac, and often want to get data from one to the other. It would be great to have something that would automatically synchronize the pasteboards between them. Currently you can do this by launching a separate app to transfer pasteboard contents, but that's enormously inconvenient compared to a transparent background service. However, launching a separate app is the only option, because Apple doesn't allow us to build a pasteboard sync daemon.

Text macros
It would be great to have customizable macros that can be inserted into text boxes, either by typing a shortcut or hitting a custom button on the screen. It could be simple stuff like my e-mail address or my phone number, or it could be more complicated stuff like my current latitude and longitude. There's no way for a third party application to manipulate another application like this.

Alternate keyboards
I use the Dvorak keyboard on my Mac. Although Apple supports Dvorak on the iPad for external hardware keyboards, it's not an option for the on-screen keyboard. While adding a custom layout would probably be a trivial modification, no such activities are allowed.

Custom input methods
A more generalized version of alternate keyboards, it would be great to be able to load custom input methods that could be accessed in addition to the alternate keyboard. Apple already supplies a method which lets you write Chinese on the screen by drawing the characters with your finger. How about adding one which lets you write English in the same way? Maybe an input method which lets you trace words over a keyboard without lifting your finger, for a speed gain? But again, no such thing is allowed.

Scripting
I love scripting my computer. I have scripts bound to hotkeys that control my music or upload screenshots to my web site. I have scripts that automatically run backups. I have scripts that take actions when new mail arrives. I build once-off scripts to make different apps work together. Scripting is something that makes a system become far more than just the sum of its parts. Scripting doesn't exist on the iPhone, and is impossible for third parties to add under the current regime.

Tor/ssh proxy
I go to China every year or two, and when I'm there, I get to enjoy the Great Firewall of China. This means that I can't directly access Facebook, YouTube, and many other sites. Luckily, it's easy to work around the Great Firewall by using services like Tor. This allows me to access the full web, despite being in a country that tries to censor the internet.

(If anyone is getting worried, don't be. The Chinese government doesn't care if a few foreigners bypass their blocks to access information they're able to get in their home country anyway.)

Last time I went to China, I took an iPhone with me and got it up and running with a Chinese carrier, complete with cellular internet access. However, I couldn't access any blocked sites from the iPhone, because tools like Tor simply don't exist there.

Even in the US, it might be nice to keep some activity hidden from AT&T or my local WiFi provider, but there's no nice way to do it.

Call recorder
While the RAZR I had before I got my iPhone didn't have a lot to recommend it, one nice thing it did have was the ability to record calls. If somebody gave me directions over the phone, I didn't have to scramble for paper, I could just hit a button and record what they said, then transcribe it later at my leisure. I'd love to have this for my iPhone, but third-party apps can't access phone audio, so my only choice is to hope Apple adds it themselves someday.

WiFi sync
Another nice RAZR feature was the ability to sync contacts and photos with my computer over Bluetooth. I find it wonderfully ironic that my cheap crappy Motorola phone could do wireless sync, but my expensive and enormously powerful iPhone can't. It would be great to have this capability, whether by doing a custom syncing protocol, or just faking out iTunes and making the wireless link look like a USB connection. But again, this can't ever happen, so I'm stuck waiting on Apple to get around to it. In the meantime, my contacts are constantly out of date and it's an annoying ritual to plug my phone into my computer so I can get pictures off of it.

WiFi hotspot
There are third-party apps that allow you to connect to the internet through your phone with WiFi, but of course none of them are allowed in the store, so they're jailbreak-only. This is a highly desirable capability that's not all that technically difficult, but Apple's loyalty to AT&T is greater than their desire to benefit their customers here.

WiFi mapper
It would be a bunch of fun to wander around the neighborhood with my phone in my pocket and have it automatically map out all of the networks it came across. Really easy to do from a technical standpoint, but the WiFi APIs are all private, so I'm out of luck.

Thermal mapper
As some of you may already know, I fly gliders. One of the challenges of glider flight is to map out the location of thermals while climbing. I thought that I could get my iPhone to help with this. By getting vertical velocity information from the GPS chip, and correlating it with horizontal position, I could build a map over time of where the thermal was strongest. Although full three-dimensional velocity data is an inherent output of any GPS calculation, CoreLocation does not provide access to vertical velocity data, only horizontal. And direct access to the GPS chip is forbidden, so I had to give up on my project.

DOSBox
I have a flight recorder for my glider, which uses GPS to record my position every few seconds so that the flight can later be analyzed (and claimed for a badge or record, if eligible). To dowload the flight record after flying, I have to take the recorder out of the glider, connect it to a PC that we keep at the airport, download the flight, then transfer the record to a flash drive so I can take it home. It's a pain in the ass. The software for downloading the flight is provided by the manufacturer and runs in, yes, DOS. Its computational requirements are low, so it should run reasonably well even in an emulator on a slow ARM chip. It would be great if I could run DOSBox and connect some sort of serial adapter to the iPhone so I could use it to dowload my flights directly, rather than screwing around with keeping a whole PC laptop at the airport. But Apple hates emulators, so this shall never be.

Location/time based configuration changes
When I'm at home, I want my ringer on. When I'm out walking, I want the phone on vibrate. When I'm flying, I don't want incoming calls at all. I have to make all of these changes manually, even though my phone knows where it is at all times. I don't want audible calendar alerts when I'm at home and my computer will alert me. I want to have it only use a passcode lock if I'm in a place I don't normally visit. It should be able to detect my location and change its configuration to suit. But third-party apps can't change this kind of configuration, so it's impossible to add.

Time-based changes would be interesting as well. I could have the ringer be quieter at night, and loud during the day. I won't bother doing this manually (especially since I don't want to risk forgetting to turn the ringer back up) but it would be great to have the phone do it automatically. I'd also like to have audible new mail alerts during the day, but not at night, and only when I'm at home. But again, it can't be done.

This sort of thing would get even more interesting when combined with scripting. I could have my phone automatically respond to incoming instant messages from people I know to tell them that I'm at the airport and may be slow to respond. My phone could automatically message my wife when I leave for home. It could detect when I'm driving and use voice synthesis to speak incoming messages from certain people I want to be able to hear from on the road. I could set up a reminder to buy cat food that would pop up next time I'm at the store.

Utilities
So there you have it, 15 apps I'd love to have on my iPhone but that Apple won't let me have, purely for political reasons. Every one of these apps is technically feasible, and many of them not even particularly challenging, but I can't have any of them. They would dramatically increase the utility of my phone, but Apple thinks they know best.

These ideas almost all fall under the category of "utilities". And this is no coincidence: utilities are largely tools which work in concert with other software to offer more power in combination than you get separately. Apple prohibits third party apps from influencing anything outside themselves, so this sort of utility is impossible. The Utilities section of the App Store is a joke. Most of what it contains is either useless or miscategorized, because Apple forbids the creation of any true utility software for this platform.

And so you can see, Apple's restrictions don't just rankle on principle, and don't just hurt me as a developer, but they dramatically reduce the usefulness of the iPhone to me as a user. And they dramatically reduce the usefulness of the platform for millions of other users as well, even if they don't know what they're missing.

Another Week Without Friday Q&A

Fri, 07 May 2010 23:08:00 GMT

Another Week Without Friday Q&A

I must apologize, but I ran out of time this week and don't have a Friday Q&A for you to enjoy. If you want something to read, you might enjoy +initialize Can Be Executed Multiple Times (+load not so much) from Bill Bumgarner, Collection Extensions from friend-of-the-blog Guy English, and launchd: Better than sliced bread! from Chris Hanson.

Friday Q&A 2010-04-30: Dealing with Retain Cycles

Fri, 30 Apr 2010 15:29:00 GMT

Friday Q&A 2010-04-30: Dealing with Retain Cycles

Happy iPad 3G day to everyone. Whether you're waiting in line, waiting for the delivery guy, or just pining at home like I am, you can fill your idle moments with another edition of Friday Q&A. This week, Filip van der Meeren has suggested that I discuss retain cycles and how to deal with them.

Retain Cycles
First we need to discuss exactly what a retain cycle is. I'll assume you're familiar with standard Cocoa memory management. The simplest retain cycle is when two objects retain each other:

    Object A
     |    ^
     |    |
     v    |
    Object B

And in the general case, it can be any collection of objects which results in a circular series of links like this. It's rare, but possible, to have a chain of three, four, five, or more objects which point to each other in a cycle.

Retain cycles are a problem because the standard for Cocoa memory management is to release such retained references in an object's dealloc method. However, if an object is being retained, it won't dealloc. Objects which are part of a retain cycle will never be deallocated, and will leak if separated from the rest of the application.

Note that retain cycles can involve your own classes, but can also involve Cocoa classes. Two of the most common culprits in retain cycles in Cocoa classes are NSTimer and NSThread.

Also note that retain cycles only affect code that uses manual memory management. Cocoa's garbage collector is able to detect and destroy objects which have strong references to each other but which aren't referenced from the outside. However, retain cycles are a big threat if you're using retain/release memory management (like if you're on the iPhone), and can even show up in a garbage collected application if you use CFRetain and CFRelease to bypass the collector.

Avoiding Retain Cycles
Apple's memory management guidelines state that when two objects have a parent-child relationship, the parent should retain the child. If the child needs a reference back to the parent, that reference should be an unretained, weak reference. This allows the parent to be deallocated, which can then release its reference to the child, avoiding a cycle.

However, sometimes you have two objects which are peers. Neither one is a parent of the other, but they need to reference each other. If these references are retained, then you have a cycle.

One way to deal with this is to redefine the relationship into parent-child. You can arbitrarily choose one to be the parent object, which will have a retained reference to the other. The other can then have a weak reference to the first. The cycle diagram then looks like this:

    Object A
     |    ^
     |    :
     v    :
    Object B

To be safe, Object A should always zero out B's weak reference when it's destroyed, to ensure that B doesn't then try to message it afterwards:

    - (void)dealloc
    {
        [_b setAReference: nil];
        [_b release];
        [super dealloc];
    }

(This is also a good practice to follow with any weak reference, including things like NSTableView data sources.)

An alternative approach is to have another object act as the parent for both sub-objects. This can work with either retained or weak references between the sub-objects. With retained references:

           Object C
           |      |
           |      |
           v      v
    Object A<====>Object B

In this scenario, you still have a retain cycle, but C can break the cycle when it releases its references:

    - (void)dealloc
    {
        // break the cycle by zeroing the reference
        [_a setBReference: nil];
        
        // this breaks the cycle in both directions; this is optional
        [_b setAReference: nil];
        
        [_a release];
        [_b release];
        
        [super dealloc]; 
    }

You can also have a weak reference between the sub-objects:

           Object C
           |      |
           |      |
           v      v
    Object A<::::>Object B

In this case, C should clear the weak references as well to be safe, but could get away without doing so.

Which way is better? They're both basically equivalent. I think that using retained references is a bit safer, both in terms of continuing to work correctly if you change the object graph later, and in being more resistant to mistakes in the code.

NSThread and NSTimer
NSThread and NSTimer are common causes of retain cycles. It's not unusual to write code like this:

    - (id)init
    {
        ...
        _timer = [[NSTimer scheduledTimerWithTimeInterval: 0.1 target: self selector: @selector(whatever) userInfo: nil repeats: YES] retain];
        ...
    }
    
    - (void)dealloc
    {
        [_timer invalidate];
        [_timer release];
        [super dealloc];
    }

There's a retain cycle here! This object retains the timer, and the timer retains its target. And note that you can't fix this by not retaining _timer. The run loop will also retain the timer, and won't release it untill the call to invalidate. This acts as a second retained reference to the timer, causing what is essentially a cycle even without the explicit retained reference.

This exact same problem also happens with an NSThread, when specifying self as the target, and then shutting down the thread in dealloc. The dealloc method will never run, so the thread will never be shut down.

There are two ways to deal with this problem. One is to force explicit invalidation, and one is to split your code into two classes.

An NSTimer won't necessarily be destroyed when you release your final reference to it. As long as the timer is active, the runloop keeps a reference to it. To destroy a repeating timer, you can't just release all of your references to it, you have to explicitly invalidate it.

You can borrow this concept for your own class. Just expose your own invalidate method, and use that to destroy the timer:

    - (void)invalidate
    {
        [_timer invalidate];
        [_timer release];
        _timer = nil;
    }

Of course, this leaks implementation details up into your interface, but forcing clients to explicitly declare when they're done with your object isn't always bad.

The other way is to split your code into two classes. You have a shell class which is exposed to the outside world, and which manages the thread or timer. Then you have an implementation class which is the target of the thread or timer, and which does most of the actual work:

    @implementation MyClassImpl
    
    - (id)init
    {
        ...
        _timer = [[NSTimer scheduledTimerWithTimeInterval: 0.1 target: self selector: @selector(_timerAction) userInfo: nil repeats: YES] retain];
        ...
    }
    
    - (void)invalidate
    {
        [_timer invalidate];
        [_timer release];
        _timer = nil;
    }
    
    - (void)doThingy
    {
        // do stuff here
    }
    
    - (void)_timerAction
    {
        // periodic code here
    }
    
    @end

    @implementation MyClass
    
    - (id)init
    {
        ...
        _impl = [[MyClassImpl alloc] init];
        ...
    }
    
    - (void)dealloc
    {
        [_impl invalidate];
        [_impl release];
        
        [super dealloc];
    }
    
    - (void)doThingy
    {
        // just pass it on to the "real" code
        [_impl doThingy];
    }
    
    @end

By splitting the implementation from the interface, you avoid the retain cycle. In effect, MyClass becomes the common parent object, with MyClassImpl and NSTimer as the sub-objects. The parent then manually breaks the retain cycle between the sub-objects when it's destroyed. Externally, the parent preserves the normal retain/release semantics, with no need for explicit invalidation.

Blocks
Because blocks retain the objects they reference, they're another excellent candidate for a retain cycle. Consider this code:

    - (id)init
    {
        ...
        _observerObj = [[NSNotificationCenter defaultCenter] addObserverForName: ... queue: [NSOperationQueue mainQueue] usingBlock: ^(NSNotification *note) {
            [self doSomethingWith: note];
        }];
        [_observerObj retain];
        ...
    }
    
    - (void)dealloc
    {
        [[NSNotificationCenter defaultCenter] removeObserver: _observerObj];
        [_observerObj release];
        [super dealloc];
    }

Because the notification block references self, the block will retain self. The result is a subtle retain cycle. This can happen even if you don't directly reference self; simply referencing an instance variable will indirectly reference self, which will cause the block to retain it.

The solutions used for NSTimer and NSThread will work here as well: either add explicit invalidation to the class's API, or break the class into two pieces.

There's a blocks-specific solution that you can use as well, which is to refer to self through a variable declared __block, which will not be retained:

        __block MyClass *blockSelf = self;
        _observerObj = [[NSNotificationCenter defaultCenter] addObserverForName: ... queue: [NSOperationQueue mainQueue] usingBlock: ^(NSNotification *note) {
            [blockSelf doSomethingWith: note];
        }];

This avoids the cycle, because blockSelf is not retained. Be careful if you do this to avoid referring to instance variables directly, as those will still reference the original self. If you need to access an instance variable, explicitly indirect through blockSelf by doing blockSelf->_someIvar.

Finding Cycles
For the most part, standard leak finding techniques will work fine for finding retain cycles that cause a leak. Instruments is a good way to find them, both the ObjectAlloc instrument and the Leaks instrument. If you have a cycle that's hard to figure out, its ability to track retain and release calls to each object can help a lot.

If you prefer the command line, or just need text that's easier to search through, the leaks command-line tool is also handy.

When hunting for cycles, note that leaks tools won't always find a cycle if there's an external reference into the cycle. For example, consider a cycle involving an NSTimer. There's a reference from the runloop to the timer, and from the timer to your object, so they're both reachable. Both the Leaks instrument and the leaks tool will not consider this to be a leak. However, if they're doing nothing and build up without end, then it still is a leak, even if they're technically reachable. The ObjectAlloc tool will show this buildup even though the other tools won't identify the leak.

Conclusion
Retain cycles are an unfortunate wart on Cocoa's memory management system. However, with some care, they can be avoided or fixed with a minimum of pain, with small changes to your object hierarchy. Pay extra attention to NSTimer and NSThread (but don't ignore other code!), then either eliminate the cycle or add code that explicitly breaks it.

That's it for this week. Come back in another seven days for the next Friday Q&A. As always, Friday Q&A is driven by reader submissions. If you have an idea for a topic that you'd like to see covered here, please send it in.

Friday Q&A 2010-04-23: Implementing a Custom Slider

Fri, 23 Apr 2010 16:01:00 GMT

Friday Q&A 2010-04-23: Implementing a Custom Slider

Welcome to another chilling edition of Friday Q&A. While I hope to be soaring over the scenic Shenandoah Valley on this fine Friday, I have taken the precaution of preparing my post in advance, so that you may see it even while I am incommunicado. Such is the magic of the modern world. This week, Michael Crawford has suggested that I give in example of implementing a custom control in Cocoa.

Specifically, he requested a diagonal slider. This slider works much like a regular Cocoa slider, except that it's oriented diagonally. To make the example more useful, I implemented it completely from scratch rather than trying to base it off of NSSlider (which would probably not be very easy for this anyway).

Getting the Code
As usual, the code that I wrote for this post is available in my Subversion repository:

    svn co http://mikeash.com/svn/DiagonalSlider/

Or just click the URL above to browse the source.

Planning
When building a custom control, it's helpful to break your tasks down as much as possible. The concept of building a custom control can be daunting, but when broken into small pieces, each small piece can become easy.

There are three main pieces to any custom control:

Drawing: The code with which the control draws itself. As controls are just views, this usually means implementing drawRect: to draw whatever you want your control to look like. In the case of the diagonal slider, it needs to draw the slider track and the knob.
Event Tracking: This involves getting and responding to events. In this case, looking at mouse down/dragged/up events and moving the slider knob around appropriately.
Geometry: This is code which figures out where the various components of the control are located. The geometry information is then used by the drawing and event tracking code to figure out where to draw things and where events are in the control. In this case, the geometry code consists of figuring out where the slider track is, where the knob is, and converting from a point to a slider value.

Interface
Before getting into the implementation, let's define the interface of the class. It will subclass NSControl. It will implement setDoubleValue: and doubleValue to return its position. For instance variables, it needs to store its value. Also, because NSControl tends to assume that you have an NSCell, and I don't want to build a cell, I also need instance variables to hold the control's target and action:

    @interface DiagonalSlider : NSControl
    {
        double _value;
        id _target;
        SEL _action;
    }
    
    - (void)setDoubleValue: (double)value;
    - (double)doubleValue;
    
    @end

Geometry
Since magic numbers are evil, the first thing I do for the geometry code is define some constants that determine the geometry of the control. The slider will extend from the bottom left corner to the top right corner of the control, but the ends need to be inset a bit to allow room to draw the slider and knob. These insets are defined here. The slider width and knob size are also defined as constants:

    const CGFloat kInsetX = 12;
    const CGFloat kInsetY = 12;
    const CGFloat kSliderWidth = 6;
    const CGFloat kKnobRadius = 10;

Now for some actual code. A major theme you'll see here is building up small methods, where each method computes a single value, relying on other methods for intermediate results. This helps enormously with simplifying the task of programming the control.

First, two methods for getting the slider endpoints:

    - (NSPoint)_point1
    {
        return NSMakePoint(kInsetX, kInsetY);
    }
    
    - (NSPoint)_point2
    {
        NSRect bounds = [self bounds];
        return NSMakePoint(NSMaxX(bounds) - kInsetX, NSMaxY(bounds) - kInsetY);
    }

Next, finding the center of the knob. To do that, I just take a weighted average of the two endpoints, using _value as the weight:

    - (NSPoint)_knobCenter
    {
        NSPoint p1 = [self _point1];
        NSPoint p2 = [self _point2];
        
        return NSMakePoint(p1.x * (1.0 - _value) + p2.x * _value, p1.y * (1.0 - _value) + p2.y * _value);
    }

Next I create a method that returns an NSBezierPath that describes the knob. You might think that this belongs in drawing, not geometry. However, I plan to use this path not only for drawing the knob, but also for determining whether the mouse is within the knob or not. Conceptually, this bezier path is part of the common geometry code:

    - (NSBezierPath *)_knobPath
    {
        NSRect knobR = { [self _knobCenter], NSZeroSize };
        return [NSBezierPath bezierPathWithOvalInRect: NSInsetRect(knobR, kKnobRadius, kKnobRadius)];
    }

Next, I'll write code to determine the slider value that corresponds to a point, and whether the slider track contains a point. In order to write those, I need some utility functions. Specifically, I need vector subtraction, vector dot product, and vector length. To keep things simple, I use NSPoint as my "vector" type. These three utility functions are then easy to write:

    static NSPoint sub(NSPoint p1, NSPoint p2)
    {
        return NSMakePoint(p1.x - p2.x, p1.y - p2.y);
    }
    
    static CGFloat dot(NSPoint p1, NSPoint p2)
    {
        return p1.x * p2.x + p1.y * p2.y;
    }
    
    static CGFloat len(NSPoint p)
    {
        return sqrt(p.x * p.x + p.y * p.y);
    }

Now, code for determining the value for a point. The math here is not complex, but may not be obvious. I start by doing a vector projection of the vector from the slider start to the point in question onto the vector of the slider itself. This projection gives me the distance of the point in question from the slider start in the direction of the slider, ignoring any side component. I then divide this length by the length of the slider, and that gives me a proportion. I want the value to be between 0 and 1, so that number is exactly what I want. Here's the code:

    - (double)_valueForPoint: (NSPoint)p
    {
        // vector from slider start to point
        NSPoint delta = sub(p, [self _point1]);
        
        // vector of slider
        NSPoint slider = sub([self _point2], [self _point1]);
        
        // project delta onto slider
        CGFloat projection = dot(delta, slider) / len(slider);
        
        // value is projection length divided by slider length
        return projection / len(slider);
    }

Finally, I need code for determining whether a point is within the slider track. (This is used to determine whether a mouse click was on the slider track, and should be responded to, or whether it was outside.)

The concept for this code is similar. First, I use _valueForPoint: to see if the point is off the ends of the slider. If it is, instant rejection. Otherwise, I see how far to the side the point is from the slider. If this distance is within the slider width, then the point is contained by the slider.

Finding that distance is similar to the above code. Instead of projecting onto the slider's vector, I project onto a vector perpendicular to the slider. The length of that projection is the distance from the middle of the slider track:

    - (BOOL)_sliderContainsPoint: (NSPoint)p
    {
        // if beyond the ends, then it's not contained
        double value = [self _valueForPoint: p];
        if(value < 0 || value > 1)
            return NO;
        
        // vector from slider start to point
        NSPoint delta = sub(p, [self _point1]);
        
        // vector of slider
        NSPoint slider = sub([self _point2], [self _point1]);
        
        // vector of perpendicular to slider
        NSPoint sliderPerp = { -slider.y, slider.x };
        
        // project delta onto perpendicular
        CGFloat projection = dot(delta, sliderPerp) / len(sliderPerp);
        
        // distance to slider is absolute value of projection
        // see if that's within the slider width
        return fabs(projection) <= kSliderWidth;
    }

Drawing
With all of these geometry methods, drawing is a snap. First, I draw a line between _point1 and _point2. Then I get the _knobPath and fill it. And that's it!

Note that I'm going for technical information, not graphical prettiness, so my slider is ugly. The track is just a blue line, and the knob is just a red circle. Making it beautiful is up to you!

Here's what the drawing code looks like:

    - (void)drawRect: (NSRect)r
    {
        NSBezierPath *slider = [NSBezierPath bezierPath];
        [slider moveToPoint: [self _point1]];
        [slider lineToPoint: [self _point2]];
        [slider setLineWidth: kSliderWidth];
        
        [[NSColor blueColor] setStroke];
        [slider stroke];
        
        [[NSColor redColor] setFill];
        [[self _knobPath] fill];
    }

Event Tracking
For tracking a mouse down/dragged/up sequence, there are two ways to do things.

One way is to implement mouseDown:, mouseDragged:, and mouseUp:, to do what you need in each situation. The other way is to only implement mouseDown:, then run your own event loop inside that to look for dragged/up events.

This second way is how most (possibly all) Apple controls work, and in my opinion generally works better. You often have state which is generated by the mouse down event, and then needs to be referenced by the dragged/up handlers, and this is easier to manage when everything is in the same place instead of scattered through several different methods. The dragged and up code is also often similar, and a single event loop allows consolidating the two cases. Because I think this way is superior, that's how DiagonalSlider will handle event tracking.

To do this, implement mouseDown:. First, figure out whether to handle the event or not. In the case of the slider, we want to handle the event if the click was in the knob or slider track, but not if it fell outside them. Handle any necessary setup, then start the inner event loop.

The slider has two cases which act slightly differently. One case is clicking in the knob itself, which does nothing to begin with, then moves the knob relative to the mouse's movements. The other case is clicking directly in the slider track, which jumps the knob to that position, then tracks further movement.

These two cases handle the same tracking at the end, but have slightly different setup. To facilitate this, I split most of the tracking into a separate method, _trackMouseWithStartPoint, which can then be called by these two cases.

The mouseDown: method first gets the location of the event, then sees if it's within the knob. If it is, then it just goes straight to tracking:

    - (void)mouseDown: (NSEvent *)event
    {
        NSPoint p = [self convertPoint: [event locationInWindow] fromView: nil];
        
        if([[self _knobPath] containsPoint: p])
        {
            [self _trackMouseWithStartPoint: p];
        }

Otherwise, it checks to see if the event is within the slider track. If it is, then it jumps the value to the current mouse position. It also sends the slider's action, to notify the target that the slider moved immediately. It then starts tracking:

        else if([self _sliderContainsPoint: p])
        {
            [self setDoubleValue: [self _valueForPoint: p]];
            [self sendAction: [self action] to: [self target]];
            [self _trackMouseWithStartPoint: p];
        }
    }

If the event is not within the knob or slider, then it's just ignored.

Now for the actual event tracking. The first thing to do is compute a value offset. This is the difference between the slider's current value, and the value which corresponds to the location of the initial mouse down event. The purpose of this is to preserve the distance between the slider knob's center and the mouse cursor. If you click on the edge of the knob and drag, your cursor should stay on the edge, not have the knob suddenly jump to be centered. Note that this is only necessary when clicking the knob, not the track. However, when clicking the track, this value will be 0 and thus do nothing, so it's not necessary to conditionalize the code:

    - (void)_trackMouseWithStartPoint: (NSPoint)p
    {
        // compute the value offset: this makes the pointer stay on the
        // same piece of the knob when dragging
        double valueOffset = [self _valueForPoint: p] - _value;

Next, start the event loop. This consists of calling -[NSWindow nextEventMatchingMask:] in a loop, until a NSLeftMouseUp event is received. I also toss in an NSAutoreleasePool to ensure that memory doesn't build up if the loop continues for a long time:

        // create a pool to flush each time through the cycle
        NSAutoreleasePool *pool = [[NSAutoreleasePool alloc] init];
        // track!
        NSEvent *event = nil;
        while([event type] != NSLeftMouseUp)
        {
            [pool release];
            pool = [[NSAutoreleasePool alloc] init];
            
            event = [[self window] nextEventMatchingMask: NSLeftMouseDraggedMask | NSLeftMouseUpMask];

Once the event comes in, figure out where it is, set the slider's value appropriately, and send the action:

            NSPoint p = [self convertPoint: [event locationInWindow] fromView: nil];
            double value = [self _valueForPoint: p];
            [self setDoubleValue: value - valueOffset];
            [self sendAction: [self action] to: [self target]];
        }

And that's it for this method, just dump the last autorelease pool and exit:

        [pool release];
    }

Miscellaneous
The slider needs a bit more support code. The only one that does anything of consequence is setDoubleValue:. It performs several tasks. First, it clamps the incoming value to be between 0 and 1. Then it assigns the value, and finally marks the control as needing a redisplay, so that the GUI updates accordingly. Note that simply redisplaying the entire view is somewhat inefficient, and it would be better to compute a minimal changed rect. However, in the spirit of avoiding premature optimization, I didn't do this.

    - (void)setDoubleValue: (double)value
    {
        // clamp to [0, 1]
        value = MAX(value, 0);
        value = MIN(value, 1);
        
        _value = value;
        [self setNeedsDisplay: YES];
    }

I also have a few one-liners to return the value, and handle target/action:

    - (double)doubleValue
    {
        return _value;
    }
    
    - (void)setTarget: (id)anObject
    {
        _target = anObject;
    }
    
    - (id)target
    {
        return _target;
    }
    
    - (void)setAction: (SEL)aSelector
    {
        _action = aSelector;
    }
    
    - (SEL)action
    {
        return _action;
    }

And that's it!

Using the Slider
Using this custom slider is much like using any other control, just with somewhat worse Interface Builder support. To create the slider in IB, you have to drag out a plain NSView, then set the class of that view to DiagonalSlider. IB doesn't know what a DiagonalSlider looks like, so it'll still show up as a plain box, but it will work correctly at runtime. IB is smart enough to notice that DiagonalSlider is an NSControl subclass, and thus allows you to set the target/action of the slider right in the nib. Convenient!

Implement the action as you would for any other control. Then you can fetch the slider's current value using doubleValue. Update its value using setDoubleValue:. And that's it!

Conclusion
Building a custom control in Cocoa can be a daunting task, but if you break it down into components and build the control up from small pieces, it's really not that hard. By separating the code into geometry, drawing, and tracking sections, and buildingu p each section from parts, building a custom control can become relatively straightforward.

That's it for this edition of Friday Q&A. Come back next week for another one. Until then, keep sending your ideas for topics. Friday Q&A is driven by user ideas, so if you'd like to see a particular topic covered here, please send it in!

Mistakes and Chains of Events

Mon, 19 Apr 2010 19:18:00 GMT

Mistakes and Chains of Events

For those of you who don't read my employer's blog, I just made a post over there titled Mistakes and Chains of Events. It discusses the recent news about political cartoonist Mark Fiore's iPhone rejection, the bigger picture of Apple's system and policies, and my perception that Apple is not learning the right lessons from the various problems that they're encountering.

Friday Q&A 2010-04-16: Implementing Fast Enumeration

Fri, 16 Apr 2010 16:35:00 GMT

Friday Q&A 2010-04-16: Implementing Fast Enumeration

Last week I discussed the various options available in Objective-C for enumerating over a collection This week I'm going to finish up the discussion of enumeration with a guide on how to implement Fast Enumeration in your own program.

Basics
There are two benefits to implementing Fast Enumeration. One is that you can then use your object as the target in a for/in loop. The other is that, with a good implementation, such enumeration will be fast.

Implementing Fast Enumeration is accomplished by implementing the NSFastEnumeration protocol. This protocol contains only a single method:

    - (NSUInteger)countByEnumeratingWithState:(NSFastEnumerationState *)state objects:(id *)stackbuf count:(NSUInteger)len;

Easy enough, right? But what's that NSFastEnumerationState thing?

    typedef struct {
        unsigned long state;
        id *itemsPtr;
        unsigned long *mutationsPtr;
        unsigned long extra[5];
    } NSFastEnumerationState;

This starts to get a little bit complex....

Deciphering Fields and Parameters
To understand how to implement this method, you need to understand what all of the fields and parameters mean, as well as the return value. I'll take these out of order.

The objective of this method is to return a series of arrays of objects. Each call returns one array, which allows objects to be returned in bulk. For speed, this uses a C array, which means that it needs a pointer and a length.

The length is provided by the return value of the method. That's what the count refers to in the name of the method. The array is actually the itemsPtr field of the NSFastEnumerationState struct. These two values together define the array returned by the method.

NSFastEnumeration is designed to allow returning a pointer to internal storage. However, not all data structures fit well with that, so it's also designed to allow copying objects into an array provided by the caller. That caller-provided array is stackbuf, and its size is given by len.

NSFastEnumeration is also designed to detect when a collection is mutated while being enumerated, and throw an exception if this occurs. mutationsPtr is indended to be pointed to a value which changes if the collection is mutated.

That's just about everything. The only fields I haven't covered yet are the state and extra fields of NSFastEnumerationState. These are just freeform fields which the callee can use to store whatever values it finds useful.

Generated Loop Code
Now we know what all these things are for, but to really understand how this stuff works, it's best to understand what kind of code the compiler generates. You write this:

    for(id obj in collection)
    {
        // body
    }

What really goes on behind the scenes?

The compiler creates an NSFastEnumerationState on the stack, as well as a stack buffer. It creates two nested loops, one which repeatedly calls countByEnumeratingWithState:... and one which loops over the array it returns. It ends up being something like this:

    // declare all the local state needed
    NSFastEnumerationState state = { 0 };
    id stackbuf[16];
    BOOL firstLoop = YES;
    long mutationsPtrValue;
    
    // outer loop
    NSUInteger count;
    while((count = [collection countByEnumeratingWithState: &state objects: stackbuf count: 16]))
    {
        // check for mutation, but only after the first loop
        // (note that I'm not sure whether the real compiler puts this
        // in the inner loop or outer loop, and it could conceivably
        // change from one compiler version to the next)
        if(!firstLoop && mutationsPtrValue != *state.mutationsPtr)
            @throw ..mutation exception...
        firstLoop = NO;
        mutationsPtrValue = *state.mutationsPtr;
        
        // inner loop over the array returned by the NSFastEnumeration call
        id obj;
        for(NSUInteger index = 0; index < count; index++)
        {
            obj = state.itemsPtr[index];
            // body
        }
    }

Notice how this code never touches or examines the state and extra fields. As I mentioned before, these are provided purely for the use of the collection, and to facilitate that, their value is preserved between calls while within the same loop.

Returning One Object At a Time
A major point of NSFastEnumeration is to achieve speed through bulk enumeration. Returning one object at a time defeats that point. However, it's easy to implement, and still gets you the benefit of being able to use for/in syntax. In the spirit of avoiding premature optimization, if returning one object at a time is easy, then go for it.

As an example, imagine you have a linked list class:

    @implementation LinkedList : NSObject
    {
        struct Node *listHead;
    }

Now let's implement NSFastEnumeration for this class, in the simplest possible way, by returning one object at a time:

    - (NSUInteger)countByEnumeratingWithState:(NSFastEnumerationState *)state objects:(id *)stackbuf count:(NSUInteger)len
    {
        // plan of action: extra[0] will contain pointer to node
        // that contains next object to iterate
        // because extra[0] is a long, this involves ugly casting
        if(state->state == 0)
        {
            // state 0 means it's the first call, so get things set up
            // we won't try to detect mutations, so make mutationsPtr
            // point somewhere that's guaranteed not to change
            state->mutationsPtr = (unsigned long *)self;
            
            // set up extra[0] to point to the head to start in the right place
            state->extra[0] = (long)listHead;
            
            // and update state to indicate that enumeration has started
            state->state = 1;
        }
        
        // pull the node out of extra[0]
        struct Node *currentNode = (struct Node *)state->extra[0];
        
        // if it's NULL then we're done enumerating, return 0 to end
        if(!currentNode)
            return NULL
        
        // otherwise, point itemsPtr at the node's value
        state->itemsPtr = &currentNode->value
        
        // update extra[0]
        if(currentNode)
            state->extra[0] = (long)currentNode->next;
        
        // we're returning exactly one item
        return 1;
    }

This is really not bad at all. It gets a little ugly with the pointer/integer casting, but that's C for you....

Returning Copied Objects in Bulk
Let's say that it turns out the above method really is too slow and you want to make it faster. You can do this by returning objects in bulk. Because the objects in the linked list aren't stored contiguously, you have to do this by copying objects into the stackbuf. While no guarantee is given as to the size of stackbuf, we can assume that it's made large enough to justify this sort of thing. Here's how the code would look:

    - (NSUInteger)countByEnumeratingWithState:(NSFastEnumerationState *)state objects:(id *)stackbuf count:(NSUInteger)len
    {
        // plan of action: pretty much the same as before,
        // with extra[0] pointing to the next node to use
        // we just iterate over multiple nodes at once
        if(state->state == 0)
        {
            state->mutationsPtr = (unsigned long *)self;
            state->extra[0] = (long)listHead;
            state->state = 1;
        }
        
        // pull the node out of extra[0]
        struct Node *currentNode = (struct Node *)state->extra[0];
        
        // keep track of how many objects we iterated over so we can return
        // that value
        NSUInteger objCount = 0;
        
        // we'll be putting objects in stackbuf, so point itemsPtr to it
        state->itemsPtr = stackbuf;
        
        // loop through until either we fill up stackbuf or run out of nodes
        while(currentNode && objCount < len)
        {
            // fill current stackbuf location and move to the next
            *stackbuf++ = currentNode->value
            
            // move to next node
            currentNode = currentNode->next;
            
            // and keep our count
            objCount++;
        }
        
        // update extra[0]
        if(currentNode)
            state->extra[0] = (long)currentNode->next;
        
        return objCount;
    }

This is not too much harder, and will significantly reduce the number of message sends that occur in the for/in loop.

Returning a Bulk Interior Pointer
For best efficiency, you can return a pointer to contiguously stored objects. For example, say you have a simple array class like this:

    @interface Array : NSObject
    {
        id *pointer;
        NSUInteger count;
    }

Implementing NSFastEnumeration for this class is really easy. It can return a single interior pointer to all of the objects, and that's it

    - (NSUInteger)countByEnumeratingWithState:(NSFastEnumerationState *)state objects:(id *)stackbuf count:(NSUInteger)len
    {
        if(state->state == 0)
        {
            state->mutationsPtr = (unsigned long *)self;
            state->itemsPtr = pointer;
            state->state = 1;
            return count;
        }
        else
            return 0;
    }

That was easy! It'll also be really fast, because the enumeration loop will basically devolve into a straight C for loop.

This technique can also be used, with some care, for more complex data structures. If you have a series of contiguous object pointers, you can return pointers to each one in turn, which will result in efficient enumeration over all of the objects in sequence. You can make good use of the extra values to keep track of where you are in your internal data structure.

A Note on Temporary Objects
You may find it useful to store Objective-C objects in the extra values:

    state->extra[1] = (long)[NSArray arrayWith...];

But beware! This will break with this completely legal enumeration code:

    NSAutoreleasePool *pool = [NSAutoreleasePool new];
    for(id obj in collection)
    {
        // do stuff with obj
        [pool release];
        pool = [NSAutoreleasePool new];
    }
    [pool release];

When the autorelease pool goes away, it'll take your array with it, and the next time you try to access it, you'll explode. And you can't retain the array, either, because there's no guarantee the caller will loop all the way to the end to let you release it; they might break out of the loop early, and then you've leaked the object.

There's really no general way to solve this. (I've concocted a completely insane scheme which involves tracking the position of the stack pointer to know when it's safe to destroy temporary objects, but it's, well, completely insane.) If you can, try to avoid storing temporary Objective-C objects in extra like this. And if you must do it, just keep in mind that you have to be careful with autorelease pools in the for/in loops that you use with this object. Since you're likely to be the only client of your NSFastEnumeration implementation, this is a reasonable constraint to make, but it's something that you have to be aware of.

Conclusion
Implementing NSFastEnumeration allows you to use nice, simple syntax for enumerating over your custom objects which are conceptually collections of other objects. As a bonus, it will usually speed up that enumeration as well. And while NSFastEnumeration can look daunting at first glance, it's actually pretty easy to write an implementation of it, depending on just how hard-core you want to get and how complex your internal data structures are.

That's it for this week's Friday Q&A. Come back in another seven days for more gooey goodness. Friday Q&A is driven by user submissions, so in the meantime, if you have an idea for a topic that you'd like to see covered here, please send it in!

An Objective-C Continuations Library

Tue, 13 Apr 2010 16:25:00 GMT

An Objective-C Continuations Library

A couple of months ago I wrote about using Continuation Passing Style in Objective-C as an alternative technique for returning errors from methods. The major downside to that technique is that it integrates poorly with Cocoa, since Cocoa isn't written to use CPS. Jordan Breeding has spent the intervening time building up an impressive CPS adapter library which allows converting any Cocoa NSError ** call into CPS style with virtually no work. Source code and extensive examples are available, and I encourage you to check it out.