Nat! bio photo

Nat!

Senior Mull

Twitter Github Twitch

mulle-objc: method searching and accidental override protection

Continued from mulle_objc: root objects and unloadable runtimes.

_mulle_objc_class_search_method is the central function for matching a selector to a C-function. The search function is executed everytime a selector/implementation pair can not be found in the class cache.

It is actually fairly easy to understand how it works, if you know how method-lists work. So here is a quick introduction on methods and method-lists.

The method-list: struct _mulle_objc_methodlist

A struct _mulle_objc_methodlist is a variably sized struct defined like this:

struct _mulle_objc_methodlist
{
   unsigned int                n_methods; // must be #0 and same as struct _mulle_objc_ivarlist
   char                        *owner;
   struct _mulle_objc_method   methods[ 1];
};
Field Description
n_methods The number of entries in methods
owner Optional: a pointer to a static string, describing the owner of this method list. This could be the name of a category for example. Only use it for debugging purposes.
methods The methods sorted by their selectors.

The actual size of the method list can be calculated with mulle_objc_size_of_methodlist given a value for n_methods.

So what is a method ?

The method: struct _mulle_objc_method

A method ties together the selector of a method with its implementation along with some other meta-information, that is all part of the descriptor. The funky union is just there for easier debug-ability in a debugger:

struct _mulle_objc_method
{
   struct _mulle_objc_methoddescriptor  descriptor;
   union
   {
      mulle_objc_methodimplementation_t    value;
      mulle_atomic_functionpointer_t       implementation;
   };
};
Field Description
descriptor Gives name, selector, encoding of the method
implementation Pointer to the actual implementation of the method

The method descriptor contains all the meta-information about the function/selector pair.

struct _mulle_objc_methoddescriptor
{
   mulle_objc_methodid_t   methodid;
   char                    *name;
   char                    *signature;
   unsigned int            bits;
};
Field Description
methodid This is the selector, e.g. @selector( foo:)
name This is the name, e.g. “foo:”
signature This is the encoding of the method, e.g. @encode( -(void) foo:(id) p) -> “v16@:@”
bits Some bits set by the compiler, which are useful for introspection of the method. Enough content for another article.

It is easy to visualize all this using the mulle-objc runtime itself:

//
// compile with: mulle-clang -o example example.m -lmulle_objc_standalone
//
#include <mulle_objc/mulle_objc.h>

@interface Root
- (void) foo;
- (void) foobar;
@end

@implementation Root
- (void) foo    {}
- (void) foobar {}
@end

@implementation Root ( Bar)
- (void) bar    {}
@end

@implementation Root ( Foobar)
- (void) foobar {}
@end


int  main()
{
   mulle_objc_runtime_dump_graphviz_to_file( "/tmp/foo.dot");
   return( 0);
}

Here is the resulting graphic:

Runtime

The magenta “Root” is the meta-class. There were no class-methods defined, so it has no method-lists. Blue “Root” has three method-lists, one for its implementation and one for each category.

_mulle_objc_class_search_method explained

Armed with this knowledge here is a commented listing of _mulle_objc_class_search_method.

It’s probably easier to follow the listing,if you open above link in a separate window.

_mulle_objc_class_search_method#L1263:

struct _mulle_objc_method   *_mulle_objc_class_search_method( struct _mulle_objc_class *cls,
                                                              mulle_objc_methodid_t methodid,
                                                              struct _mulle_objc_method *previous,
                                                              unsigned int inheritance)
{
   struct _mulle_objc_runtime                         *runtime;
   struct _mulle_objc_method                          *found;
   struct _mulle_objc_method                          *method;
   struct _mulle_objc_methodlist                      *list;
   struct mulle_concurrent_pointerarrayreverseenumerator   rover;
   unsigned int                                       n;
   unsigned int                                       tmp;
Parameter Description
cls The class to search for. This is either the class (for instance - methods) or the meta-class for (class + methods)
methodid The selector we will be searching for.
previous Usually NULL, but it could be the result of a previous _mulle_objc_class_search_method call. This is a way to retrieve overridden method implementations.
inheritance Control the inheritance of methods. You can selectively turn off parts of the search. More on this later.

_mulle_objc_class_search_method#L1275:

   assert( mulle_objc_class_is_current_thread_registered( cls));

   // only enable first (@implementation of class) on demand
   //  ->[0]    : implementation
   //  ->[1]    : category
   //  ->[n -1] : last category

This is a runtime assert, to make sure that the runtime is properly setup. This comes in handy, when doing multi-threaded processing. As this operation is not costless, it’s an assert, to be turned off with -DNDEBUG.

_mulle_objc_class_search_method#L1283:

   n = mulle_concurrent_pointerarray_get_count( &cls->methodlists);
   assert( n);
   if( inheritance & MULLE_OBJC_CLASS_DONT_INHERIT_CATEGORIES)
      n = 1;

A class MUST have a method-list, at least an empty one. If inheritance forbids searching through category methodlists, then only the first method-list which is always the class `@implementation is searched.

_mulle_objc_class_search_method#L1288:

   rover = mulle_concurrent_pointerarray_reverseenumerate( &cls->methodlists, n);
   found = NULL;

   runtime = _mulle_objc_class_get_runtime( cls);
   if( runtime->debug.trace.method_searches)
      fprintf( stderr, "mulle_objc_runtime %p trace: search class %s for methodid %08x (previous=%p)\"\n", runtime, cls->name, methodid, previous ? _mulle_objc_method_get_implementation( previous) : NULL);

Methodlists are searched from back to front. This is logical as categories override the class implementation. Therefore a “reverse enumerator” is used on the internal lists of methods cls->methodlists.

_mulle_objc_class_search_method#L1295:

   while( list = _mulle_concurrent_pointerarrayreverseenumerator_next( &rover))
   {
      method = _mulle_objc_methodlist_search( list, methodid);

      if( method)
      {
         if( previous)
         {
            if( previous == method)
            {
               previous = NULL;
               continue;
            }
         }

Now each method-list is searched by _mulle_objc_methodlist_search. This is a binary search, which makes the lookup often better than linear, but by no means fast. If a match is made, the previous logic checks if the search needs to continue.

_mulle_objc_class_search_method#L1310:

         if( found)
         {
            errno = EEXIST;
            return( NULL);
         }

Here is some logic for a special “bit” in the descriptor. The runtime can check for possibly hidden overrides, by continuing the search. In the example.m the compiler knows that -foobar in Root ( Foobar) is intended to override a method declared in the class. It would also know, that -bar of Root ( Bar) is not an intended override. By setting the override fatal bit on -bar, the runtime can check, that in the future this does not accidentally override a method. See: How to avoid accidental overriding method or property in Objective-C

The compiler doesn’t emit that bit yet.

_mulle_objc_class_search_method#L1316:

         if( ! _mulle_objc_methoddescriptor_is_hidden_override_fatal( &method->descriptor))
         {
            if( runtime->debug.trace.method_searches)
            {
               // one more ? it's a category
               if( list = _mulle_concurrent_pointerarrayreverseenumerator_next( &rover))
                  fprintf( stderr, "mulle_objc_runtime %p trace: found in category %s( %s) implementation %p for methodid %08x ( \"%s\")\"\n", runtime, cls->name, list->owner ? list->owner : "", _mulle_objc_method_get_implementation( method), method->descriptor.methodid, method->descriptor.name);
               else
                  fprintf( stderr, "mulle_objc_runtime %p trace: found in class %s implementation %p for methodid %08x ( \"%s\")\"\n", runtime, cls->name, _mulle_objc_method_get_implementation( method), method->descriptor.methodid, method->descriptor.name);
            }

Usually though the search method exits here on a match:

_mulle_objc_class_search_method#L1334:

            mulle_concurrent_pointerarrayreverseenumerator_done( &rover);
            return( method);
         }

         found = method;
      }
   }
   mulle_concurrent_pointerarrayreverseenumerator_done( &rover);

Now after having searched through the class and the categories, there is the option to all search the protocol classes. See: mulle_objc: inheriting methods from protocols This is by enabled by default in MulleObjC:

_mulle_objc_class_search_method#L1336:

   if( ! (inheritance & MULLE_OBJC_CLASS_DONT_INHERIT_PROTOCOLS))
   {
      tmp = 0;
      if( inheritance & MULLE_OBJC_CLASS_DONT_INHERIT_PROTOCOL_CATEGORIES)
         tmp |= MULLE_OBJC_CLASS_DONT_INHERIT_CATEGORIES;

      method = _mulle_objc_class_protocol_search_method( cls, methodid, previous, tmp);
      if( method)
      {
         if( found)
         {
            errno = EEXIST;
            return( NULL);
         }

         if( ! _mulle_objc_methoddescriptor_is_hidden_override_fatal( &method->descriptor))
            return( method);

         found = method;
      }
   }

_mulle_objc_class_protocol_search_method enumerates the protocol classes and calls _mulle_objc_class_search_method on them.

Finally if all else failed, the class hierarchy above cls is searched by recursively with a a _mulle_objc_class_search_method of the superclass:

_mulle_objc_class_search_method#L1358:

   if( ! (inheritance & MULLE_OBJC_CLASS_DONT_INHERIT_SUPERCLASS))
   {
      if( cls->superclass)
      {
         method = _mulle_objc_class_search_method( cls->superclass, methodid, previous, cls->superclass->inheritance);
         if( method)
         {
            if( found)
            {
               errno = EEXIST;
               return( NULL);
            }

            if( ! _mulle_objc_methoddescriptor_is_hidden_override_fatal( &method->descriptor))
               return( method);

            found = method;
         }
         else
         {
            if( errno == EEXIST)
               found = NULL;
         }
      }
   }

   if( ! found)
      errno = ENOENT;  // thread safe errno is potentially expensive

   return( found);
}

And that’s it.

Continued to mulle_objc: caches pivot - selectors mask - methods preload.