The BOOL return problem

Created 11/28/2006, updated 5 weeks ago11 minute read

The "select" HOM is one of the most frequently used patterns in any demonstration of HOM yet ironically it is also the most difficult to implement due to a quirk in the way the compiler and runtime work. Given code like the following:

NSArray *selection = [[array select] hasPrefix:@"foo"];

The compiler will warn:

warning: initialization makes pointer from integer without a cast

The compiler expects hasPrefix: to return a BOOL yet it sees that result being assigned to a pointer to an object id and hence issues a warning. As will be shown below this is not just a compile-time problem but a run-time one as well. If we try casting to id we get a different warning; this code:

NSArray *selection = (id)[[array select] hasPrefix:@"foo"];

Yields the following warning:

warning: cast to pointer from integer of different size

The compiler here warns that an integer (a BOOL, one byte in size on Intel) is being cast to a pointer (an integer of four bytes in size when running on a 32-bit architecture). Even if our HOM implementation returns a real pointer in response to the hasPrefix: selector, the code generated by the compiler will truncate it and return a mangled, broken, one-byte version.

Digging deeper

So there are two levels on which the problem needs to be addressed: firstly, the compile-time issue (how do we eliminate compiler warnings and errors?) and secondly, the run-time issue (how do we get the code to actually do what we want it to do?).

The cause of the confusion is that the compiler will find a method signature that looks like this:

- (BOOL)hasPrefix:(NSString *)prefix;

You could declare another one, which returns type id:

- (id)hasPrefix:(NSString *)prefix;

But then the compiler would complain as follows:

warning: multiple methods named ‘-hasPrefix:’ found
warning: using ‘-(BOOL)hasPrefix:(NSString *)aString’

You can’t trick the compiler to use the one you want by merely casting:

// compiler will still use the BOOL variant
(id)[object hasPrefix:@"foo"];

There are only two ways to explicitly force the compiler to use the version you want. One is to cast to a specific class; for example, given the following interface:

@interface Hack : NSObject
- (id)hasPrefix:(NSString *)prefix;
@end

You could explicitly cast to Hack:

[(Hack *)object hasPrefix:@"foo"];

You could also drop down to the runtime level and do an explicit cast:

((id (*)(id, SEL, id))objc_msgSend)(object, @selector(hasPrefix:), @"foo");

Now let’s look at the assembly code generated by the above line:

leal LC1-"L00000000001$pb"(%ebx), %edx
leal L_OBJC_SELECTOR_REFERENCES_0-"L00000000001$pb"(%ebx), %eax
movl (%eax), %eax
movl %edx, 8(%esp)
movl %eax, 4(%esp)
movl -16(%ebp), %eax
movl %eax, (%esp)
call L_objc_msgSend$stub     ; the preparation in the lead-up to the message send is identical
movl %eax, -12(%ebp)         ; id return: get return value from %eax (4 bytes in size)

Compare that with the assembly generated for the BOOL return case:

leal LC1-"L00000000001$pb"(%ebx), %edx
leal L_OBJC_SELECTOR_REFERENCES_0-"L00000000001$pb"(%ebx), %eax
movl (%eax), %eax
movl %edx, 8(%esp)
movl %eax, 4(%esp)
movl -16(%ebp), %eax
movl %eax, (%esp)
call L_objc_msgSend$stub     ; the preparation in the lead-up to the message send is identical
movb %al, -9(%ebp)           ; BOOL return: get return value from %al (1 byte in size)

This is why merely casting is never going to be enough to solve this problem: the low-level ABI returns different kinds of results in different ways. Fortunately, the ABI itself is very well documented, and we may need to get our hands dirty with it before the end of this article.

Exploring the possible solutions

We’ve seen two workarounds already above: one is declaring "hack" interfaces and then casting to them (you could define macros to make this easier if you think it’s going to be something that you do often); another is using casting in conjunction with objc_msgSend.

But which would you rather use?

[[object select] hasPrefix:@"foo"];
((id (*)(id, SEL, id))objc_msgSend)(object, @selector(hasPrefix:), @"foo");

The whole point of HOM is making your intention as transparent and easy-to-express as possible. It might be possible to make the cast a little less ugly using a macro definition:

#define WO_SELECT(object, sel, ...) \
((id (*)(id, SEL, id))objc_msgSend)(objc_msgSend(object, @selector(select)), sel, __VA_ARGS__);

Which would mean that you could write…

WO_SELECT(object, @selector(hasPrefix:), @"foo");

… which is marginally better but still far from desirable, and even further from the the ideal of true HOM.

The underscore trick

I believe that MPWFoundation provides a hack which programmers can use to avoid the unwanted compiler mangling; the details run something like this:

[[object select] __hasPrefix:@"foo"];

Anything beginning with two consecutive underscores will be caught by the trampoline, the underscores removed, and the real message sent. MPWFoundation provides a number of predefined "hack" interface declarations for methods such as __isKindOfClass: to avoid compiler warnings. If you try this trick with any method for which a corresponding interface declaration does not exist then you’ll get this warning:

warning: no ‘-__hasPrefix:’ method found
warning: (Messages without a matching method signature
warning: will be assumed to return ‘id’ and accept
warning: ‘...’ as arguments.)

If you go down this path you may find it useful to define a macro:

#define WO_MACRO_HACK(selector) __ # selector

Which would be used as such:

[[object select] WO_UNDERSCORE_HACK(hasPrefix:@"foo")];

But it is debatable whether this looks any better or is more useful than the alternative.

The inline assembly trick

Ofri Wolfus’ HOM implementation takes an alternative tack. First he defines an ID macro as follows (for Intel):

#define ID(X...) ({ volatile id __o = nil; X; asm volatile ("mov %%eax, %0": "=m" (__o)); __o; })

Message objects are then created using the MSG macro:

#define MSG(X...) ID([_sharedMessageBuilder X])

So the following:

[array select:MSG(hasPrefix:@"foo")];

After preprocessing evaluates to:

[array select:({ volatile id __o = 0; [_sharedMessageBuilder hasPrefix:@"foo"]; asm volatile ("mov %%eax, %0": "=m" (__o)); __o; })];

As our assembly excerpt above shows, the compiler will see the hasPrefix: message and output the following assembly language:

call L_objc_msgSend$stub
movb %al, -9(%ebp)

But what we wanted was:

call L_objc_msgSend$stub
movl %eax, -12(%ebp)

So if we re-write the above code block using a mixed Objective-C/assembly notation we get:

{
    volatile id __o = 0;
    [_sharedMessageBuilder hasPrefix:@"foo"];   // compiler thinks that return value is in %al
    asm volatile ("mov %%eax, %0": "=m" (__o)); // move real return value from %eax to __o
    __o;                                        // evaluate __o: __o will effectively be passed to select:
}

Although this may seem terribly hackish, the ABI itself is quite well documented so there’s only a small amount of "black magic" going on here. It’s not too difficult to imagine using the ID macro in a more conventional HOM implementation with only a slight readability penalty:

ID([[collection select] hasPrefix:@"foo"])

The downside of using such macros is that due to their low-level nature it requires four variations to be written, maintained and tested (32 and 64 bit variants for PowerPC, likewise for 32 and 64 bit Intel) and if Apple ever changes the ABI in a significant way then they must be updated.

An alternative macro approach

The Cocoade frameworks (documented here) do a different macro trick, using a HOM macro and hom_t type to leverage some GCC built-in functions:

typedef union { long l; unsigned long ul; long long ll;
unsigned long long ull; float f; double d; void *v;
id o; } hom_t;


#define HOM(X) \
((hom_t) \
__builtin_choose_expr(\
__builtin_types_compatible_p(__typeof__(X), float),(__typeof__(X)) X, \
__builtin_choose_expr(\
__builtin_types_compatible_p(__typeof__(X), double),(__typeof__(X)) X, \
__builtin_choose_expr(\
sizeof(__typeof__(X)) <= sizeof(long),(long)="" x,="" (__typeof__(x))="" x="" )))).o<="" pre="">

This macro depends on GCC's __builtin_choose_expr and __builtin_types_compatible_p functions, documented here. Expressed in "pseudo code" the HOM macro does the following with the expression, X:

if (type of X is float or compatible)
    return (float)X;
else
{
    if (type of X is double or compatible)
        return (double)X;
    else
    {
        if (size of type of X <= size="" of="" long="" type)="" return="" (long)x;="" }="" (type="" x)x;<="" pre="">

The "returned" value in the pseudo-code above is used to populate the appropriate field of a hom_t union, and the o field of that union is then evaluated, effectively casting to id (the type of o).

I don't have access to the Cocoade source code, only the public headers, but based on my analysis of this macro I can't see how it would solve the problem at issue here. The macro is effectively a fancy cast to id that you can use without provoking any "cast to pointer from integer of different size" warnings, but it doesn't seem to address the underlying problem that the compiler will still trash the id return value wherever it thinks it is a BOOL.

Changing GCC

The notes that come with MPWFoundation state, "The current compiler generates code for the BOOL return it thinks is happening that mangles the id-return that is actually happening.  A patch has been submitted to the gcc Objective-C maintainer". I haven't been able to find any other public details about this, but I imagine it modifies the way that BOOLs are returned so that they are returned in the same way that normal integers are (in EAX in the case of Intel chips). If accepted, it will probably be quite a while before such a patch makes trickles down into the version of GCC that ships with Apple's Xcode tools. I'm not all that hopeful, to tell the truth, because if this patch involves any ABI changes then its chances of being accepted are very slim indeed; but given that the patch isn't public it's hard to say...

Twisted workarounds

Thinking about other ways to tackle this problem leads one down a path in which the workarounds get successively twisted and lead one further and further away from the ideal (transparent intentions, minimal obstacles to expressing those intentions).

For example...

// desired ideal form, but with fatal flaw
[[collection select] hasPrefix:@"foo"];


// could you interpose something there that made the compiler think that an id was returned?
[[collection select] method_that_returns_id_and_accepts_bool:[thing hasPrefix:@"foo"];

So what is the "method_that_returns_id_and_accepts_bool"? select can return a proxy or some other kind of object responds to the "method_that_returns_id_and_accepts_bool" message. But what then is the "thing" object referred to above? Evidently it must be something that somehow records a message send and returns a boolean.

But the "thing" object has no idea what kind of message it is going to have to record, doesn’t know what object it is standing in for (because it doesn’t know what kind of collection select was sent to) and so it will be difficult for it to obtain a proper method signature in a bullet-proof fashion. Also, given that it only returns a BOOL, it can’t really communicate anything useful back to the "method_that_returns_id_and_accepts_bool".

This leads you inevitably towards the following type of construct:

// need some way of letting the "catcher" know what kind of object it is standing in for
catcher = [BoolCatcherMaker catcherForObject:collecton];


// and need some kind of way to tell a collection to select on the basis of what the catcher says
[[collection selectWithBoolCatcher:catcher] hasPrefix:@"foo"];


// the return value can't be trusted, must query the catcher
[catcher selection];

And no matter how you try to formulate things you will always come up with a construct of three lines; there’s no way to do it as a one-liner. This is for the simple reason that you can’t trust the return value after sending the hasPrefix: message. You therefore need to query the proxy afterwards in a separate message send (requiring 2 lines). And in order to query the proxy you need to grab a reference to it first (now we’re up to 3 lines).

That is, the pattern is:

Get the proxy, keeping a reference to it
Send the message to the proxy (and let the proxy do its work)
Query the proxy for the results

So the simple:

[[collection select] hasPrefix:@"foo"];

Has morphed into:

WOHOMSelector *selector = [WOHOMSelector selectorForObject:object];
(void)[selector hasPrefix:@"foo"];
NSArray *selection = [object select:selector];

And in doing this you practically lose the entire benefit of HOM. If that’s the best you can do then you may as well just write stuff using NSPredicate objects:

[array filteredArrayUsingPredicate:[NSPredicate predicateWithFormat:@"hasSalary == %d", 1000]];

The only shortcoming of this approach is that the NSPredicate class is 10.4+ only, and it is incapable of expressing constructs like this one:

[[array select] hasPrefix:[prefixes each]];

There is one way in which we could reduce our hackish three-line HOM construct to two lines, and that would be to add a method to store the last result and then later retrieve it:

(void)[[WOHOMSelector selectorForObject:object] hasPrefix:@"foo"];   // can't depend on return value
NSArray *selection = [WOHOMSelector lastSelection];

To make this thread-safe would require the use of thread-local storage, and thread-local storage is quite slow, unfortunately. Adding that to the already considerable overhead of trampoline-based HOM makes it quite unattractive.

Concluding comments

"The BOOL return problem" is such a big deal that some HOM implementors have elected to omit some of the most important and useful HOM selectors ("select" and "reject"):

One unfortunate consequence of these goals is that certain HOMs become difficult or impossible to implement. The classic filter messages, -select and -reject, cannot be implemented in a simple, portable manner because the messages given to them typically return BOOL, but the HOM needs to return an object. This could be at least partially rectified by writing filter messages which only act on mutable containers and don’t return anything, but this is less than ideal.

Of all the possible solutions, the Wolfus (ID) macro-based solution seems to be the best of a bad bunch, and it is a macro-based solution that I went with when I checked in my own "select" implementation yesterday.

It’s probably worth reminding ourselves why we care about all this anyway. The kind of HOM pattern that we can easily implement without kludges (the "collect" pattern) is exactly the kind of pattern we could do faster using normal Cocoa calls:

// this is the HOM collect
[[collection collect] foobar];


// and this is the Cocoa equivalent for NSArray
[collection valueForKey:@"foobar"];

The Cocoa version wins on speed, is only a few characters longer, and works on 10.3 and up. The HOM version may lose a bit on speed (depending on the number of elements in the array), wins the character count contest by a few chars, and (depending on the implementation) can work on any version of Mac OS X and with any kind of collection object (not just NSArray); my implementation goes a step further and works with any object at all.

In terms of clarity of intention it’s probably a tie. The HOM alternative is highly readable to anyone familiar with HOM. Other programmers may need a clarifying comment. The Cocoa version looks extremely readable at first glance but it requires a constant string key instead of a bare selector and its operation may not be immediately evident; a "value for key" method might suggest to some that a single element is being returned, not an array containing the values for the key of the objects in the receiver.

But there are two things you can do in the HOM pattern that you cannot do in the standard Cocoa version and they are pass parameters:

[[collection collect] hasPrefix:@"foo"];

And iterate over collection members and arguments in "lock step":

[[collection collect] foobar:[keywords elements]];

And that’s why people jump through so many hoops so that they can drag the "select" and "select where" HOMs, kicking and screaming, into Objective-C; so that they can write stuff like this:

return [[collection selectWhere] plugInIdentifier] isEqualToString:[desiredIdentifiers elements]];

Instead of this:

NSEnumerator *enumerator = [collection objectEnumerator];
id item;
unsigned counter = 0;
NSMutableArray *results = [NSMutableArray array];
while ((item = [enumerator nextObject]))
{
    if ([[item plugInIdentifier] isEqualToString:[desiredElements objectAtIndex:counter++]])
        [results addObject:item];
}
return [[array copy] autorelease];

blog