Getting the IMP of the current method

Once in a very great while, you come across a weird situation where you want to know the IMP of the current method. I’ll just say right now that if you think you need this, you probably don’t. That’s how rare this situation is.

Regardless, it’s an interesting question. How do you get the function pointer for the currently-executing method?

A few years ago, Matt Gallagher came up with a clever solution to this using a compiler function called __builtin_return_address(). His code still works great with the LLVM 3.0 compiler. My only beef with it is that there’s a lot of looping going on. He’s looping over the entire superchain, over every single method, looking at the IMP's address and comparing them to another pointer.

Pretty Pretty

This morning I was thinking about a question on Stack Overflow and thought of another way to get the current IMP:

static inline IMP __CurrentIMP(const char *info, SEL _cmd) {
  IMP imp = NULL;
  if (info[0] == '-' || info[0] == '+') {
    NSString *tmp = [NSString stringWithCString:info+2 encoding:NSUTF8StringEncoding];
    NSRange r = [tmp rangeOfString:@" "];
    NSString *className = [tmp substringToIndex:r.location];
    Class thisClass = NSClassFromString(className);
    if (thisClass != nil) {
      Method m = NULL;
      if (info[0] == '+') {
        m = class_getClassMethod(thisClass, _cmd);
      } else {
        m = class_getInstanceMethod(thisClass, _cmd);
      }
      if (m != NULL) {
        imp = method_getImplementation(m);
      }
    }
  }
  return imp;
}

#define CurrentIMP __CurrentIMP(__PRETTY_FUNCTION__, _cmd)

So, what’s going on? Basically, we’re parsing a special string that’s generated by the compiler and then doing a single lookup. The important bit is the __PRETTY_FUNCTION__. This is a built-in “magic” value that, when compiled, becomes a very nice-looking description of the current function (it’s “pretty”).

For a regular C function, __PRETTY_FUNCTION__ becomes a const char* that includes the name of the function and some type information. The main() function has a __PRETTY_FUNCTION__ of this: "int main(int, const char **)". Ooooo, pretty! :)

An Objective-C method’s pretty description doesn’t include type information, but it does include some very important information. Let’s say we have a class Bar that has this method:

- (id)doAwesomeThingWithFoo:(Foo *)foo {
    ...
}

The pretty description for this is "-[Bar doAwesomeThingWithFoo:]". Here, we see two very important pieces of information:

  • The first character is a -, indicating that the method is an instance method
  • The name of the implementing class is clearly visible.

The selector is also in there, but we would have that anyway through _cmd, so that’s not very interesting. (We could forego passing in _cmd to the __CurrentIMP function and parse it out of the description, but since _cmd is there already, let’s use that.)

The really important thing to realize here is that the name of the class in the description is the class on which the method is implemented, and not the class of any instance. This makes sense, because this is all happening at compile time, not runtime.

Armed with these two pieces of information, we can quickly get the appropriate IMP. First, we do some really simple string parsing to extract the name of the class from the description, and turn it in to a Class object with the NSClassFromString function.

Now that we have the Class and the selector (we’re just using _cmd), we can get the IMP. However, we need to know which runtime function we should be using. For this, we can simply look at the first character in the description string. If it’s a +, then we use the class-specific function, otherwise we’ll use the instance-specific function.

These functions (class_getClassMethod and class_getInstanceMethod) both return Method references. From this Method, we can simply use method_getImplemention to get the method’s IMP. Simple!

Some may ask: why are we getting the Method reference instead of using the class_getMethodImplementation function, which returns an IMP directly? The answer for that is that while that would usually work, it would fail for methods that have large return values (i.e. where the size of the return value is larger than sizeof(id)). In that case, we’d have to use the class_getMethodImplementation_stret function, which means we’d have to get an NSMethodSignature object and check the methodReturnLength to decide which function to use. I figure that getting the Method and asking it for its IMP is probably simpler.

Now, there is a downside to this approach (that are not present in Matt’s implementation). Since this is relying on a compile time detail (the pretty description), this totally and utterly breaks when you start add methods, swizzling implementations, make IMPs from blocks, etc.

But for those times where you, for whatever reason, need to know what your IMP is, this works pretty well.


Steve Weller pointed on on Twitter that if you combine this code with Matt’s version, you can reasonably determine when a method has been swizzled. Cool!

Dumbfounded

I was just shown an NSPredicate that dumbfounded me for several reasons:

  1. It’s using five nested SUBQUERY expressions. In other words, a SUBQUERY within a SUBQUERY within a SUBQUERY within a SUBQUERY within a SUBQUERY.
  2. It works
  3. It’s reasonably fast
  4. Core Data correctly handles it on a SQLite store
  5. It’s the only way the author could accomplish what he needed in a “reasonable” way.

What sort of NSPredicate is this? Here you go:

static NSString *kCommonRequestFragment = @"SUBQUERY(things, $thing, SUBQUERY($thing.thingType.spams, $spam, SUBQUERY($spam.ham.eggs, $egg, SUBQUERY($egg.foo.bars, $bar, SUBQUERY($bars.baz.blips, $blip, $blip.bing.id == %@).@count > 0).@count > 0).@count > 0).@count > 0).@count > 0";

- (NSFetchRequest *)fetchRequestForSomeObjects {
    NSFetchRequest *theRequest = [self templateFetchRequest];
    NSString * thePredicateFormatString = [NSString stringWithFormat:@"(%@) AND (%@)", @"SUBQUERY(participatingObjects, $object, $object.property.id == %@).@count > 0", kCommonRequestFragment];
    [theRequest setPredicate:[NSPredicate predicateWithFormat:thePredicateFormatString, self.aThing.anID, self.aThing.anotherID]];

    return theRequest;
}

- (NSFetchRequest *)fetchRequestForOtherObjects {
    NSFetchRequest *theRequest = [self templateFetchRequest];
    NSString * thePredicateFormatString = [NSString stringWithFormat:@"(%@) AND (%@)", @"SUBQUERY(participatingObjects, $object, $object.property.id == %@).@count == 0", kCommonRequestFragment];
    [theRequest setPredicate:[NSPredicate predicateWithFormat:thePredicateFormatString, self.aThing.anID, self.aThing.anotherID]];

    return theRequest;
}

Insane.

Parsing Mathematical Expressions

A while ago, I was looking for a library to parse NSString objects as mathematical expressions. I wanted to be able to take a string like @"2+3*4" and get back 14. I found two easy ways to do this: GCMathParser and NSPredicate (of course!).

GCMathParser is a library by Graham Cox for parsing strings as equations. It uses a parser generated by BISON as the primary engine, with a straight-forward Objective-C wrapper for easy interaction. In terms of raw speed, it’s blazingly fast. However, I found one major flaw with it: it is impossible to extend. It has support for a bunch of built-in functions (all your basic trigonometric functions, rounding, etc), but if you wanted to add support for bitwise operators (bitwise AND, OR, NOT, XOR, etc), you’re totally out of luck. There’s no way to do it without regenerating an entirely new parser.

NSPredicate, as I’ve mentioned before, can also parse numerical expressions. Like GCMathParser, it has a couple of flaws:

  1. The associativity of the power operator is wrong. The string @"2 ** 3 ** 2" is parsed as (2 ** 3) ** 2, or 64. This is “left associativity”. In practical terms, it means that when you have a bunch of the same operator in a row like that, the left-most one is evaluated first. However, exponentiation is supposed to be right associative. In other words, that expression should’ve been parsed as 2 ** (3 ** 2), or 512. This is a major flaw, and it’s been reported: rdar://8692313.
  2. The syntax for custom functions is absurdly bizarre. NSExpression, the class that makes up the basic components of a predicate, does not have any trigonometric functions built-in. However, NSExpression does support defining your own functions, but with a ridiculously complex syntax. For my purposes, I wanted to take a regular user-entered string and parse it, without requiring the user to know about FUNCTION() syntax. I could’ve tried manipulating the user’s string to transform sin(<#expression#>) into FUNCTION(<#expression#>, 'sinValue') and then written a sinValue category method on NSNumber, but if I was going to write a transformer to manipulate the string, I might as well write a full-fledged parser.

So, I wrote DDMathParser to be extensible, correct, and easy to understand.

The Guts

I tried writing a formal grammar for parsing a mathematical expression, and actually got pretty far. However, when writing the recursive descent parser to match strings against this grammar, I came up against some conceptual hurdles that I couldn’t work around. I also didn’t like that modifying the grammar, even slightly, usually meant making extremely large changes to the parser. Eventually I gave up with that sort of parser and came up with something else.

There are several phases to parsing a string using this parser:

  1. Tokenization
  2. Grouping
  3. Resolving

Tokenization

Tokenization is simply the process of breaking up the string into chunks. If I have the string @"1 + 2 - 3 * 4 / 5", then after tokenization I’m going to end up with 9 tokens: 1, +, 2, -, 3, *, 4, /, and 5. No attempt is made to try to resolve anything. I will note, however, that this is the point at which implicit multiplication is made explicit. More on that later.

The tokenization process simply reads through the string character-by-character, and decides what to do with the characters it finds. The general rules it follows are:

  • If it reads a digit or a decimal point, attempt to parse a number (a number is defined as anything recognizable by NSNumberFormatter).
  • If parsing a number failed and the character is matched by [a-zA-Z0-9] (any alphanumeric character), then attempt to parse the name of a function.
  • If parsing a function name failed and the character is the $ character, then attempt to parse a variable name.
  • If parsing a variable name failed, then attempt to parse an operator.
  • If parsing an operator failed, then abort with an error.

It’s also at this point that we figure out if - and + are acting, for example, as negation or subtraction. The basic rule is: if a - or + is preceded by another operator that’s not a closing parenthesis (or it’s the first token in the steam), then it’s the unary operator (negation, etc). Otherwise it’s the binary operator.

Grouping

If tokenization succeeds, the tokens are grouped into “terms”. To explain what goes on, we’ll look at an example. Let’s say we’re parsing the string @"2 * (pi()sin(dtor(45)) + max($a, 42)/54)". The token stream will have generated these tokens:

2 * ( pi ( ) * sin ( dtor ( 45 ) ) + max ( $a , 42 ) / 54 )

Grouping organizes the terms hierarchically. This is done recursively, and is also where parentheses are checked to make sure they’re balanced. Visually, we’ll end up with something like this:

First phase of grouping

As you can see, no attempt has been made to define precedence. The step is only to break up the tokens into parenthetical “levels”.

Resolving

After the terms have been grouped, we can break things up further. We take the root group and iterate over the terms in its “subterms" array to find the indices of the operators with the highest precedence. Precedence is defined via an enum:

enum {
    DDPrecedenceBitwiseOr = 0,
    DDPrecedenceBitwiseXor,
    DDPrecedenceBitwiseAnd,
    DDPrecedenceLeftShift,
    DDPrecedenceRightShift,
    DDPrecedenceSubtraction,
    DDPrecedenceAddition = DDPrecedenceSubtraction,
    DDPrecedenceDivision,
    DDPrecedenceMultiplication = DDPrecedenceDivision,
    DDPrecedenceModulo,
    DDPrecedenceUnary,
    DDPrecedenceFactorial,
    DDPrecedencePower,
    DDPrecedenceParentheses,

    DDPrecedenceUnknown = -1,
    DDPrecedenceNone = -2
};

Parentheses produce the highest precedence, followed by the power operator, then the factorial operator, then any generic unary operator (negation, bitwise NOR, etc), and then down on through the standard mathematical operators, with bitwise OR having the lowest precedence. Subtraction has the same precedence as addition, since subtraction is really just the addition of a negative number. Likewise, division is the same as multiplication by the number’s multiplicative inverse.

Once we have the indices of the operators with the highest precedence, we’ll need to look and see if we have more than one. If we do, then we look at the associativity of the operator to see if we should choose the first (ie, left associative) or last (ie, right associative) operator. After picking an operator, we can look at the terms around the operator, recursively resolve those terms (if necessary), and then combine those resolved terms and the operator into a new group term. This is when we check to make sure that operators have all the necessary terms. It’s at this point, for example, that @"2+" would fail to parse, because + is a binary operator, but the string only has a single term. @"+2", however, would parse, because + would already have been recognized as a unary operator.

After resolution has finished, our object hierarchy now looks like this:

After term resolution

At this point, the term hierarchy is fully organized, and it’s a simple matter to convert it into expression objects for storage and/or evaluation.

Implicit Multiplication

When writing mathematical expressions, we understand that we can express the multiplication of two terms without actually writing a multiplication operator. For example, 5x is 5 * x, and 6(9) is the same thing as 6 * 9. I really wanted the parser to handle implicit multiplication, and it turns out it was very simple to implement. When tokenizing a string, a * token is inserted between two tokens if a Number, Variable, or Close Parenthesis token is followed by anything except an operator token (unless it’s an Open Parenthesis token). With this setup:

  • 5$x becomes 5 * $x
  • 6(9) becomes 6 * (9)
  • 2sin($x) becomes 2 * sin($x)

Analysis

As I see it, there are several major advantages to this parser:

  • The only limit on valid numbers is that they be recognizable by NSNumberFormatter. This means that we can use numerical types with far more precision than a double, and much larger than a long long. For all but the trigonometric functions, calculations are done with NSDecimal structs boxed in NSDecimalNumber objects.
  • Function resolution doesn’t happen until evaluation time. This allows us to parse strings like bogus(42), but not care that the bogus function doesn’t exist. With the ability to delay function recognition, we’re free to define any extra functions that we want.
  • Parsing is not defined by a grammar. If we need to add a new operator, it’s very feasible, and won’t require generating a whole new parser.
  • Operator associativity can be changed on-the-fly. If, for some reason, you need exponentiation to be left associative rather than right associative, it’s extremely easy to change that with a simple property change.

The primary downside of this parser, however, is speed. Since we’re operating with several different layers of Objective-C objects, rather than on a C string, there’s going to be an enormous* speed discrepancy between GCMathParser and DDMathParser. However, what we lose in speed is more than made up for in extensibility and accuracy.

The code is available for your perusal at GitHub: https://github.com/davedelong/DDMathParser

* by “enormous”, I mean “about 2 orders of magnitude, but still able to parse and evaluate a complex string in a fraction of a second”


Updates

  • 4 Jun 2011: original posting
  • 5 Jun 2011: added description of recognizing unary operators

Subclassing NSInputStream

Subclassing NSInputStream is a problem that has been plaguing Cocoa developers for a long time. Googling “subclass nsinputstream” reveals that people have been having issues with this for six or seven years. While the documentation seems to indicate that it should be fairly straightforward, actually trying to do so reveals several hairy spots.

For example, if you try to use a custom NSInputStream as the body of an NSURLRequest, you’ll get an exception that your input stream doesn’t respond to _scheduleInCFRunLoop:forMode:. So then you create an empty stub for that method. You’re good, right? Nope! Now you fail with an unimplemented _setCFClientFlags:callback:context:. So you implement that, and you’re good, right? Nope! You fail now with an unimplemented _unscheduleFromCFRunLoop:forMode:. So you put that in as a stub, and you’re good? Well, you don’t get any more exceptions… but nothing ever gets read from your stream. Minor details…

Well, the dark night of ignorance and inability is over!

BJ Homer has just posted an article on how he got his NSInputStream subclass to work. He’s even posted a demo on his GitHub account. I won’t spoil any of the details here; go read it for yourself! His solution is really quite clever.

(And as a side note, at the time of this writing, there are 2,272 occurrences of the letter ‘n’ on his blog’s home page.)

How to learn Cocoa

This is something any experienced Cocoa developer has been asked at least half a dozen times:

"What’s the best way to learn Objective-C/Cocoa?"

I have two answers to this question:

  1. Be curious
  2. Don’t be satisfied

Be Curious

Curiosity is the heart of learning anything. If you can cultivate a deep curiosity about the Objective-C language and the Cocoa frameworks, then I guarantee that you will have absolutely no problem learning them. I’m not talking about the “oh, wouldn’t it be nice to know how to write iOS apps” kind of curiosity. I’m talking about the “why does the @ sign go there? What’s up with these asterisks all over the place? Why are things done in this order instead of that order” kind of curiosity. Gaining this level of curiosity can be very difficult, especially at first. But without it, you’ll never really understand how everything is working together.

If you’re familiar with an sort of object-oriented programming language, then Objective-C, as a language, shouldn’t be that hard to pick up. Just use get used to the square brackets, and things will look pretty familiar. Learning the frameworks, on the other hand, will take a lifetime. The Cocoa Frameworks (Foundation, AppKit/UIKit, CoreData, CoreFoundation, MapKit, QuickLook, MediaAccess, CoreLocation, etc) are enormously broad. The Foundation framework itself is composed of 173 public classes and 31 protocols. That’s a lot of pre-built code, and that’s just one framework out of a couple dozen! There are some classes you will come to know very intimately (NSString, NSArray, NSDictionary), but even they will surprise you every now and then. Plus, Apple actively develops these frameworks; they’re being improved and optimized and expanded all the time. There will always be more to learn.

Along with the capabilities of the classes, there are patterns to learn. Design patterns describe how classes interact with each other. Some of the first ones you’ll encounter are Model View Controller, Delegation, and Class Clusters. There are many others, and they’re in there for a very good reason. As you come across them, take the time to understand why they’re there.

Do the same with the classes in the frameworks. Explore them. Play with them. Abuse them. Ask yourself:

  • What problem does this solve?
  • How does it solve the problem?
  • Can you use these abilities for anything else?
  • How would you implement this class if you had to? (And then go do it!)

Be curious.

Don’t Be Satisfied

As you learn Cocoa, the code you write will be terrible. Understand that. But don’t accept it. There is always a different way you could do something, and quite often one of those different ways is a better way. Always seek out opportunities to improve your code and to find different and better ways to organize it. Sometimes this will mean rewriting things half a dozen times. But you know what? That’s OK! All developers experience this. If you can learn to not be satisfied with your code, you’ll quickly learn how to iterate over it and make improvements here, tweak some stuff there, maybe rip out some layer of control and totally reorganize it… This is what programming is all about. Don’t be satisfied with how your code looks. Strive to make it a work of art and a thing of beauty.

Final Thoughts

So there you have it! These are my recommendations for how to learn Cocoa. They have served me well, and I think they pretty much summarize what I’ve observed about experienced developers.

Oh, and by the way…

  1. Know what a pointer is.
  2. Memorize the memory management rules.
  3. Never invoke -retainCount.

Welcome to Cocoa.