Foreach in C++ stl

#define CONCAT_IMPL( x, y ) x##y
#define MACRO_CONCAT( x, y ) CONCAT_IMPL( x, y )
#define PPUniVar(name) MACRO_CONCAT(name, __COUNTER__)

#define _foreach(var, collection, collection_to_iter, collection_type) \
typedef typeof(collection) collection_type; \
collection_type collection_to_iter = (collection); \
collection_type::iterator _##var=collection_to_iter.begin(); \
if (_##var!=collection_to_iter.end()) \
for (collection_type::value_type var = *_##var; _##var!=collection_to_iter.end() && (var = *_##var, true); _##var++ )

#define foreach(var, collection) \
_foreach(var, collection, PPUniVar(collection_to_iter), PPUniVar(collection_type))

C Switch for Non-Integers

In C, and thus Objective-C, a switch statement only works with integers, and the case labels all need to be constant.  Strings seem like a natural thing to switch on, especially for command line interfaces.  Unfortunately, they cannot be reduced to integer constants, so we cannot use them.  Now that we have blocks in the language, we can create a dictionary where we associate any object, such as an NSString, with a block, and call the selected block after a simple dictionary lookup.

The syntax

//get a string from standard input
char str[256];
fgets(str, 256, stdin);
*(char *)memchr(str, '\n', 256) = '';

JPSwitch([NSString stringWithUTF8String:str]) {
	JPCase(@"option one"):
		NSLog(@"the first posibility was selected");

	JPStringCase(Do Non-NSString objects work?):
		NSLog(@"Yes, technically any object would work as a key,"
		  @"and anything else would work with an NSValue wrapper");

	JPDefaultCase:
		NSLog(@"None of the possiblities were selected.  Oh noes!");
} JPSwitchEnd;

Due to the unordered nature of a dictionary, there is no (simple) way to enable fall-through, so control-flow breaks immediately upon a subsequent case statement, eliminating the need for the break keyword.  More than that however, I view the lack of a break keyword as a net positive because they usually simply require extra typing, creating a reduction of code density, compared to the relative few of times fall-through functionality is necessary.

The JPSwitchEnd macro and its exact usage is something I agonized for a while over, as it would be much more C-like if the switch statement ended at the closing brace.  The main point of interest was the semicolon’s inclusion or exclusion from the macro, but ultimately I decided on its exclusion so that the JPSwitch statement would look closer to the C do…while statement, instead of a dangling reminder of an ugly macro.

The Macro Hackery

Peeling back the layers, here is what the JPSwitch statement above would look without macros:

__JPSwitch([NSString stringWithUTF8String:str], ^{
}, @"option one", ^{ JPSwitchCase:
	 NSLog(@"the first posibility was selected");
}, @"Do Non-NSString objects work?", ^{ JPSwitchCase:
	 NSLog(@"Yes, technically any object would work as a key,"
	       @"and anything else would work with an NSValue wrapper");
}, &JPSwitchDefaultCaseIndicator, ^{ JPSwitchCase:
	 NSLog(@"None of the possiblities were selected.  Oh noes!");
} , &JPSwitchTermationIndicator);

as you can see, the macros just barely cover a variadic function, which does the real work.  Before we delve into that function, a few things to note which may be non-obvious:

The empty block that is the second parameter to __JPSwitch is there so that the first case (“option one”) will not have any errors upon the closing brace that it begins with.  Because we want the control flow of the previous case to break upon the following case, it is vital that we include this all on one line, hence in one macro, hence the closing brace (for all other cases).

Another thing to note is the JPSwitchCase label which precedes every case; this is so we can have the colon after the (macros) of the case labels, but serves no actual purpose.  They do not conflict with each other because they are in separate blocks.

Lastly, note the &JPSwitchDefaultCaseIndicator and &JPSwitchTerminationIndicator.  Variadic functions need a sentinel value to signal the end of their parameter list, but typically NULL (which is the same as nil) is the colloquial sentinel for pointer types.  Because methods often return nil when unable to return a valid object, it is possible that a case label object may be nil.  (In order to make __JPSwitch nil safe, we will ignore nil case labels and their blocks.)  The reason the NULL constant is used, however, is because it is guaranteed that no actual object (in the C sense of the word) can occupy the space pointed to by NULL, and therefore it can never accidentally equal a valid pointer.  With this in mind, it is easy to create a pointer sentinel value: just allocate global dummy memory and use its pointer, that way no valid object’s pointer can compare equal to it.  Thinking myself rather clever, I used this approach for the default case label as well.

The result:

//JPSwitch.h
extern char JPSwitchTermationIndicator;
extern char JPSwitchDefaultCaseIndicator;

void __JPSwitch(id selector, ...);
#define JPSwitch(selector)	__JPSwitch(selector, ^
#define JPCase(obj)		}, obj, ^{ JPSwitchCase
#define JPStringCase(str)	JPCase(@#str) //Preprocessor stringification
#define JPDefaultCase		}, &JPSwitchDefaultCaseIndicator, ^{ JPSwitchCase
#define JPSwitchEnd		, &JPSwitchTermationIndicator)

__JPSwitch

The majority of its workings having been exposed already, there is one last intricacy of __JPSwitch.  I mentioned above that it used a dictionary; it does not, however, use an NSDictionary.  While it could be using a C++ std::map, I chose to keep this purely Objective-C, although if I hadn’t I would be making use of the templating in std::map for the case label object, making it compatible with any object, C, Objective-C, or C++.  Instead, I used NSMapTable.  The reason I chose it over NSDictionary is that NSMapTable is more than happy to accept arbitrary pointers, but more importantly not retain them.  This is significant because when you retain a block, you copy it, which can be expensive.  This way, you have very little overhead for unused code.  While the rest should be left as an exercise  for the reader, it’s on my github, so I’ll post it here as well:

//JPSwitch.m
#import "JPSwitch.h"

char JPSwitchTermationIndicator, JPSwitchDefaultCaseIndicator;

void __JPSwitch(id selector, ...) {
	va_list args;
	va_start(args, selector);

	id caseLabel;
	void(^caseBlock)();
	void(^defaultCaseBlock)() = nil;

	va_arg(args, void(^)());	//Eat empty first block

	NSMapTable *allCases = [NSMapTable mapTableWithWeakToWeakObjects];
	while ((caseLabel = va_arg(args, id)) != (void *)&JPSwitchTermationIndicator) {
		caseBlock = va_arg(args, id);
		if (caseLabel == (void *)&JPSwitchDefaultCaseIndicator) {
			defaultCaseBlock = caseBlock;
		} else if (caseLabel != nil) {
			[allCases setObject:caseBlock forKey:caseLabel];
		}
	}

	caseBlock = (void(^)())[allCases objectForKey:selector] ?: defaultCaseBlock;
	if (caseBlock) caseBlock();
}

Conclusion

So now you can use a switch statement over any Objective-C object, including NSStrings.  Additionally, you can switch with anything else by wrapping it in an NSValue.  I think this could be best used in parsing and especially in command line interfaces.

You can download the entire project here.

Call any super class’s implementation of any method

In Objective-C, you can only call an overridden implementation of a method from an immediate subclass of that method’s class.  This works well to provide encapsulation, and based on the way super is handled, a super method implementation cannot be called from any but the immediate superclass (inheritance notwithstanding).  This is a good thing, as it would break large bits of encapsulation if subclasses could call arbitrary super implementations, or worse, if other objects could call super implementations of methods on foreign objects.

What we’re going to do

Keeping in mind that you should never do this, let’s implement a way to call arbitrary super implementations of arbitrary objects.  This includes calling a super implementation of arbitrary level on self, which is not as awful, but still implementation dependent.

This encapsulation-breaking design-pattern destroyer will also have a -super method that takes no arguments and messages the immediate superclass, but can be chained together, so that we may use dot-syntax.  However, the use of this method is a malfeasance in the world of Objective-C, where the actual class of an object may be a subclass of the class which you have declared it a pointer to an object of, and you will end up calling the implementation of the wrong superclass.  Additionally, in the case where you are using it on self, the runtime lookup of the superclass may result in the calling of the implementation from the class of the caller, if self is actually a subclass which happened to be in a call to a super implementation of its own, which is absolutely a Very Bad Thing and will likely lead to a crash.

All in all, by the end of this we will be able to write things like this:

[[Superclass levelSuperOf:self] dosomething];
[[Superclass levelSuperOf:self] performSelector:@selector(dosomething)];
[object.super dosomething];
[object_getSuper(myNonNSObjectInheritingObject, itsClass) dosomething];
[[object superWithClass:[Superclass class]] dosomething];

The implementation

The object_getSuper function works for any object, so we’re not restricted to NSObject subclasses for these methods, and their implementations’ consist of calling object_getSuper with the correct parameters, so we will not be spending time writing them out.

One additional note is that we must implement +(id)superWithClass:(Class)superclass, should never actually be called when one could simply call the method on the superclass directly, if it were at hand. However, the metaclass of NSObject actually inherits from NSObject, which is unbelievably confusing (explained rather well here, especially in the comments), but basically means that -superWithClass: would be available in something like [NSObjectSubclass superWithClass:NSObject], unless you actually ‘overload’ it with +superWithClass:. At any rate, for my +superWithClass:, I simply return the passed superclass.

For the actual implementation of object_getSuper, we return a HigherOrderMessage object (full code on my github repo, abbreviated here)

id object_getSuper(id object, Class superclass) {

	return [HigherOrderMessage HOMWithGetSignatureForSelector:^NSMethodSignature *(SEL aSelector) {
		return [object methodSignatureForSelector:aSelector];
	} capture:^(NSInvocation *message) {
//Snip.  Extra code handling performSelector:, its variants, and super
		[message invokeWithTarget:object superclass:superclass];
	}];
}

…which hands off the work to a NSInvocation category,

@implementation NSInvocation (SuperMessenger)

- (void)invokeWithTarget:(id)target superclass:(Class)superclass {
	[SuperMessenger superMessage:self withObject:target class:superclass];
}

@end

…which hands off the work to a class called SuperMessenger

Some Background

In Objective-C, the super keyword is the way to call a superclass’s implementation of a method.  When the compiler finds a method call, it generates code as if it was a function call to (an appropriately casted) objc_msgSend, with two additional arguments preceding the ones passed to the method: receiver and selector, corresponding to the ‘hidden parameters’ self and _cmd in the callee.  However, the compiler special cases a method call with a target of super, and instead generates a call to objc_msgSendSuper, which also takes a selector parameter, but instead of a receiver, uses a pointer to a struct of the receiver (self) and the (super)class whose implementation we are calling, which in Objective-C is always the immediate superclass of the caller’s class.

All of the above can be found in Apple’s official Objective-C language documentation, especially the first two sections.

Keep in mind that the difference between the signatures of objc_msgSendSuper is the destination type of the first argument.  This is so after objc_msgSendSuper has done the method implementation lookup, it can swap the pointer for the actual receiver without any additional fuss.  (It cannot however simply look up the superclass of the receiver at runtime, for reasons mentioned above in ‘What We’re Going To Do’.)  Both of these methods lookup the method implementation in the superclasses (sequentially) of the target class if the method is not found in the target class.

The SuperMessenger implementation

SuperMessenger implements a plethora of convenience methods, but they all end up saving the target of the message send and its selected superclass in an ivar (target) of type struct objc_super (the destination type of the first argument of objc_msgSendSuper).  Then the -invoke: method is called with a NSInvocation.  The -invoke: method saves the selector of the invocation in an ivar (selector), and then sets the invocation’s selector to the appropriate forwarding method for its return type, (ABIs handle struct and sometimes floating point returns differently, depending on the ABI.) and invokes the invocation on self.

The ‘forwarding methods’ are all exactly the same, however they are separated for the sole purpose of giving them different return types for the runtime.  They work by calling the __builtin_apply family of GCC extensions to apply all (even unknown) arguments passed to them to objc_msgSendSuper, but only after swapping the receiver (self) and selector (_cmd) for their proper values residing in ivars target and selector.  Additionally, an integer containing the frame length of the method is required for __builtin_apply, but we do not have to worry about this as NSMethodSignature provides a convenient method returning just that, so all we have to do is store it in an ivar in -invoke:.  Lastly, once we set self to the objc_super, ivars will become unavailable to us (although the compiler won’t give us any errors), so we need to remember to set self after we get the other two ivars or we crash.

The Core Code

#define SUPERMESSAGE(method) {									\
int framelength = frameLength;									\
_cmd = selector;										\
self = (id)⌖										\
__builtin_return(__builtin_apply((void(*)())method, __builtin_apply_args(), framelength));	\
}																							

- (long long)superMessage SUPERMESSAGE(objc_msgSendSuper)
- (double)superMessageFpret SUPERMESSAGE(objc_msgSendSuper)
- (CGRect)superMessageStret SUPERMESSAGE(objc_msgSendSuper_stret)
//CGRect used to simulate generic struct

- (void)invoke:(NSInvocation *)invoc {
	NSMethodSignature *methodSignature = invoc.methodSignature;
	frameLength = methodSignature.frameLength;
	char retType = methodSignature.methodReturnType[0];

	selector = invoc.selector;
	if (retType == 'd' || retType == 'f') {
		invoc.selector = @selector(superMessageFpret);
	} else if (methodSignature.methodReturnLength > 8) {
		invoc.selector = @selector(superMessageStret);
	} else {
		invoc.selector = @selector(superMessage);
	}

	[invoc invokeWithTarget:self];
}

Platform/Compiler Dependence – You should never, ever, EVER use this

Alas, this code only works on GCC, as llvm-gcc does not yet support the __builtin_apply functions.  Most worrisome, however, is that this code (even with the correct modifications to the forwarding method selection in -invoke:) only works on an IA-32 processor (Intel 32-bit MacOS); this means that it is code generation (read: compiler-target) dependent, so not only does this fail in ‘modern’ MacOS applications/iOS, it also means that it could break with an update to GCC, or conceivably even an update to the OS.  Of course, we are using __builtin_apply after changing the arguments, which we’re not supposed to do, so it is understandable that it would not work, and we are lucky that it functions on at least one platform.  It is none the less unsettling.
I’m not quite sure what to make of this, but many of the samples I found of __builtin_apply were part of an old version of the Objective-C runtime.  This may relate to the above code working only on IA-32, or it might hold an inkling of irony (if I’m guessing correctly, it may have been added to the compiler for forwarding in Objective-C).

I may eventually return to this topic, when I have fully delved into the calling conventions of the various platforms on which Objective-C runs, but regardless I dare say it necessary to wrap most/all of the code in ‘The Core Code’ in a platform-specific ifdef.  Upon that continuation, however, I would need to make a choice to either leave the firm foundation of fact and journey into thickets of wildest guesswork with regard to the generated data structure returned by __builtin_apply_args, or write the forwarders in assembly.  While assembly really is the (very, very) best tool for the job, there are two problems: I don’t have any experience writing assembly, and if we were going to use assembly we should have just used libffi/libffi-iphone (which are both really cool).

Conclusion

We’ve just written a whole bunch of code that both should never be used and is extra fragile.  …  That almost sounds like I just wasted 5 minutes of your time.  Whoops.  Next post will cover non-fragile, totally portable stuff.  Maybe.

So now we can, on Mac OS 32 bit applications, call an arbitrary super implementation of an arbitrary class.

You can download the project here.

The best use of this that I can think of is skipping over specific overridden implementations of a superclass method to call a higher (inheritance-wise) implementation.  This could actually be rather useful, if it weren’t for the fact that this means you’re breaking encapsulation, however I guess it is understandable if used to hack Cocoa.

My Higher Order Message Implementation

As this is my first post, I feel that there should be some sort of introduction here.  However, this post is really just here because it contains the implementation of something that will be used in my next post, but isn’t on quite the same topic, and  therefore should really have it’s own post.  Also, it is therefore a good deal shorter than I expect most posts will be.  Well it looks like I’ve inadvertently given a little introduction, so I really should round it off with a few good words, and they are: Nitwit! Blubber! Oddment! Tweak!

Note: This is not an original idea of mine.  For a good explanation of what Higher Order Messaging is, see this paper.

The Idea

There are some great implementations of higher order messaging, but this is not one of them.  Instead, this is an implementation of a HigherOrderMessage object, which is designed with the goal of extensibility, by forgoing subclasses for blocks.  This is obviously very straight forward, with an external interface of just

+ (id)HOMWithGetSignatureForSelector:(NSMethodSignature *(^)(SEL selector))_sig
                             capture:(void (^)(NSInvocation *message))_forward

This way, we can put all of the higher order messaging logic in one place, allowing us to (for example) implement -[NSObject(HOM) ifResponds] in only 7 lines:

- (id)ifResponds {
	return [HigherOrderMessage HOMWithGetSignatureForSelector:^(SEL selector) {
		return [self methodSignatureForSelector:selector] ?: [NSMethodSignature signatureWithObjCTypes:"@@:"];
	} capture:^(NSInvocation *message) {
		[message invokeWithTarget:([self respondsToSelector:message.selector] ? self : nil)];
	}];
}

Note that for selectors which are not understood, if the calling function expects a non-object/pointer return type, this may produce undefined returns.  However, this post is about the HigherOrderMessage, so the details of various calling conventions will be left to others, except for this reminder that whenever we deal with NSMethodSignature and NSInvocation we need to pay extra close attention, as these are relatively fragile as Cocoa classes go (of no fault of their own).

The Implementation

At any rate, the implementation for this is extremely simple: create ivars for the two blocks, and call them in -methodSignatureForSelector: and -forwardInvocation: respectively.  First instinct is to put these in a subclass of NSProxy, considering that’s its raison d’être. However, NSProxy implements a number of methods which we would naturally prefer forwarded to our target, for example -class, to which NSProxy responds with its own subclass, as opposed to the class of the target.

Instead, we can easily implement our own root class, with only two things the language requires for all classes: have the first ivar be a Class, commonly named isa (for is-a, as in this object is-a whatever-class-this-first-ivar-is), and implement +initialize, because +initialize is called just before the first message is sent to an object of its class, and we therefore crash without it.  (note: class_createInstance and later object_dispose used in place of +alloc and -dealloc respectively are defined in <objc/runtime.h>, so you’ll need to #include it in HigherOrderMessage.m)

//HigherOrderMessage.h
@interface HigherOrderMessage {
	Class isa;
	NSUInteger retainCount;

	NSMethodSignature *(^methodSignatureForSelector)(SEL selector);
	void (^forward)(NSInvocation *capture);
}
+ (id)HOMWithGetSignatureForSelector:(NSMethodSignature *(^)(SEL selector))_sig
			     capture:(void (^)(NSInvocation *message))_forward;
- (id)retain;
- (id)autorelease;
- (void)release;
@end
//HigherOrderMessage.m
+ (id)HOMWithGetSignatureForSelector:(NSMethodSignature *(^)(SEL selector))_sig
			     capture:(void (^)(NSInvocation *message))_forward
{
	HigherOrderMessage *message = class_createInstance(self, 0);
	if (message) {
		message->methodSignatureForSelector = [_sig copy];
		message->forward = [_forward copy];
		message->retainCount = 1;
	}
	return [message autorelease];
}

- (NSMethodSignature *)methodSignatureForSelector:(SEL)aSelector {
	return methodSignatureForSelector(aSelector);
}

- (void)forwardInvocation:(NSInvocation *)invocation {
	forward(invocation);
}

+ (void)initialize {
}

Memory Management

One other thing NSProxy takes care of (also the main reason for choosing it over making a root class) is memory management: it implements +alloc, -retain, -release, -autorelease, and -dealloc.   These are not only easy to avoid/implement, but in the off chance that -dealloc is to be called directly by a client of a HigherOrderMessage, it would almost definitely be intended for the forwarding target, so by not using NSProxy, we can simply not implement -dealloc on HigherOrderMessage, and instead put the teardown logic in -release.  Indeed, this makes sense when we look at -dealloc as simply an override point called in the default -release implementation so that typically we do not have to override it.

We will use the __sync_add_and_fetch and __sync_sub_and_fetch functions for incrementing and decrementing the retainCount because they are GCC atomic builtins, making -retain and -release thread safe, as long as the memory management guide is adhered to.  Of course, in -release when the retain count hits zero but the object has not yet been disposed, if another thread calls -forwardInvocation: or -methodSignatureForSelector: it would cause a dereference of the then-deallocated block called in that method, and thus a crash.  There’s no point in trying to change this, as this is how Cocoa handles it, with the same problems.  However, the memory management guide says that no pointers should be left pointing at an object when it is destroyed, so no methods could be called on it, making this potential race condition theoretically impossible.

- (id)retain {
	__sync_add_and_fetch(&retainCount, 1);
	return self;
}

- (id)autorelease {
	[NSAutoreleasePool addObject:self];
	return self;
}

- (void)release {
	if (__sync_sub_and_fetch(&retainCount, 1) == 0) {
		[methodSignatureForSelector release];
		[forward release];
		object_dispose(self);
	}
}

@end

Conclusion

Higher Order Messaging is very cool, and very powerful, but one thing annoying about implementing it is the excessive use of subclasses in addition to NSObject/collection class categories, which breaks up the logic into  two places.  My particular implementation uses blocks, which in many ways can be used in place of Higher Order Messaging, to implement said higher order messaging, while alleviating the issues of separation of logic, and allowing it to be instead encapsulated in the implementation of the (category) method.

You can download the project at http://github.com/jaredp/jaredp.repo/tree/master/HigherOrderMessage/

Again, there is nothing particularly special about this particular implementation, but I needed it for background for my next post, which was really sort of meant to be my first post, and will change the way we use Objective-C forever.  Not really.  But ooh look, I’m teasing my next post already, looks like the bloggery has begun to set in.  Which brings me to…

Epilogue (or: Prologue to the future my blog)

Well, it looks like thats my first post.  That didn’t hurt as much as the interblags said.  I hope to hold myself to one every week or so, at a minimum.  And somehow it’s 3am, and I’m writing a 1000 word essay that I’ve been putting off for a few days.  Good thing school hasn’t started yet.  And now I’m just rambling.  I do that a lot.

Follow

Get every new post delivered to your Inbox.