gcc/objc/sendmsg.c

   1 /* GNU Objective C Runtime message lookup
   2    Copyright (C) 1993 Free Software Foundation, Inc.
   3
   4 Author: Kresten Krab Thorup
   5
   6 This file is part of GNU CC.
   7
   8 GNU CC is free software; you can redistribute it and/or modify it under the
   9    terms of the GNU General Public License as published by the Free Software
  10    Foundation; either version 2, or (at your option) any later version.
  11
  12 GNU CC is distributed in the hope that it will be useful, but WITHOUT ANY
  13    WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
  14    FOR A PARTICULAR PURPOSE.  See the GNU General Public License for more
  15    details.
  16
  17 You should have received a copy of the GNU General Public License along with
  18    GNU CC; see the file COPYING.  If not, write to the Free Software
  19    Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  */
  20
  21 /* As a special exception, if you link this library with files compiled with
  22    GCC to produce an executable, this does not cause the resulting executable
  23    to be covered by the GNU General Public License. This exception does not
  24    however invalidate any other reasons why the executable file might be
  25    covered by the GNU General Public License.  */
  26
  27 #include "runtime.h"
  28
  29 #ifdef OBJC_SPARSE_LOOKUP
  30 const char* __objc_sparse_lookup_id = "Method lookup uses sparse arrays";
  31 #endif
  32
  33 #ifdef OBJC_HASH_LOOKUP
  34 const char* __objc_hash_lookup_id = "Method lookup uses hash caching";
  35 #endif
  36
  37 #ifdef OBJC_HASH_LOOKUP
  38 #include "objc/cache.h"
  39 #endif
  40
  41 #ifdef OBJC_SPARSE_LOOKUP
  42 /* The uninstalled dispatch table */
  43 struct sarray* __objc_uninstalled_dtable = 0;
  44 #endif
  45
  46 /* Send +initialize to class */
  47 static void __objc_send_initialize(Class*);
  48
  49 static void __objc_install_dispatch_table_for_class (Class*);
  50
  51 /* Forward declare some functions */
  52 #ifdef OBJC_SPARSE_LOOKUP
  53 static void __objc_init_install_dtable(id, SEL);
  54 #endif
  55 static id __objc_missing_method(id, SEL, ...);
  56 static Method_t search_for_method_in_hierarchy (Class* class, SEL sel);
  57 static Method_t search_for_method_in_list(MethodList_t list, SEL op);
  58 id nil_method(id, SEL, ...);
  59
  60 id
  61 nil_method(id receiver, SEL op, ...)
  62 {
  63   return receiver;
  64 }
  65
  66 /* Given a class and selector, return the selector's implementation.  */
  67 __inline__ IMP
  68 get_imp (Class* class, SEL sel)
  69 {
  70 #ifdef OBJC_SPARSE_LOOKUP
  71   void* res = sarray_get (class->dtable, (size_t) sel);
  72   if(res == __objc_init_install_dtable)
  73     __objc_install_dispatch_table_for_class (class);
  74   return sarray_get (class->dtable, (size_t) sel);
  75 #else
  76   return cache_get (class, sel);
  77 #endif
  78 }
  79
  80 __inline__ BOOL
  81 __objc_responds_to (id object, SEL sel)
  82 {
  83   return get_imp (object->class_pointer, sel) != __objc_missing_method;
  84 }
  85
  86 /* This is the lookup function.  All entries in the table are either a
  87    valid method *or* one of `__objc_missing_method' which calls
  88    forward:: etc, or `__objc_init_install_dtable' which installs the
  89    real dtable */
  90 __inline__ IMP
  91 objc_msg_lookup(id receiver, SEL op)
  92 {
  93   if(receiver)
  94 #ifdef OBJC_HASH_LOOKUP
  95     return cache_get(receiver->class_pointer, op);
  96 #else
  97     return sarray_get(receiver->class_pointer->dtable, (sidx)op);
  98 #endif
  99   else
 100     return nil_method;
 101 }
 102
 103 IMP
 104 objc_msg_lookup_super (Super_t super, SEL sel)
 105 {
 106   if (super->self)
 107     return get_imp (super->class, sel);
 108   else
 109     return nil_method;
 110 }
 111
 112 retval_t
 113 objc_msg_sendv(id object, SEL op, size_t frame_size, arglist_t arg_frame)
 114 {
 115 #ifdef __objc_frame_receiver
 116   __objc_frame_receiver(arg_frame) = object;
 117   __objc_frame_selector(arg_frame) = op;
 118   return __builtin_apply((apply_t)get_imp(object->class_pointer, op),
 119                          arg_frame,
 120                          frame_size);
 121 #else
 122 #warning performv:: will not work
 123   (*_objc_error)(object, "objc_msg_sendv (performv::) not supported\n", 0);
 124   return 0;
 125 #endif
 126 }
 127
 128 void __objc_init_dispatch_tables()
 129 {
 130 #ifdef OBJC_SPARSE_LOOKUP
 131   __objc_uninstalled_dtable
 132     = sarray_new(200, __objc_init_install_dtable);
 133 #endif
 134 }
 135
 136 #ifdef OBJC_SPARSE_LOOKUP
 137 /* This one is a bit hairy.  This function is installed in the
 138    premature dispatch table, and thus called once for each class,
 139    namely when the very first message is send to it.  */
 140
 141 static void __objc_init_install_dtable(id receiver, SEL op)
 142 {
 143   __label__ allready_initialized;
 144   IMP imp;
 145   void* args;
 146   void* result;
 147
 148   /* This may happen, if the programmer has taken the address of a
 149      method before the dtable was initialized... too bad for him! */
 150   if(receiver->class_pointer->dtable != __objc_uninstalled_dtable)
 151     goto allready_initialized;
 152
 153   if(CLS_ISCLASS(receiver->class_pointer))
 154     {
 155       /* receiver is an ordinary object */
 156       assert(CLS_ISCLASS(receiver->class_pointer));
 157
 158       /* install instance methods table */
 159       __objc_install_dispatch_table_for_class (receiver->class_pointer);
 160
 161       /* call +initialize -- this will in turn install the factory
 162          dispatch table if not already done :-) */
 163       __objc_send_initialize(receiver->class_pointer);
 164     }
 165   else
 166     {
 167       /* receiver is a class object */
 168       assert(CLS_ISCLASS((Class*)receiver));
 169       assert(CLS_ISMETA(receiver->class_pointer));
 170
 171       /* Install real dtable for factory methods */
 172       __objc_install_dispatch_table_for_class (receiver->class_pointer);
 173
 174       if(op != sel_get_uid ("initialize"))
 175         __objc_send_initialize((Class*)receiver);
 176       else
 177         CLS_SETINITIALIZED((Class*)receiver);
 178     }
 179
 180 allready_initialized:
 181
 182   /* Get real method for this in newly installed dtable */
 183   imp = get_imp(receiver->class_pointer, op);
 184
 185   args = __builtin_apply_args();
 186   result = __builtin_apply((apply_t)imp, args, 96);
 187   __builtin_return (result);
 188
 189 }
 190 #endif
 191
 192 /* Install dummy table for class which causes the first message to
 193    that class (or instances hereof) to be initialized properly */
 194 void __objc_install_premature_dtable(Class* class)
 195 {
 196 #ifdef OBJC_SPARSE_LOOKUP
 197   assert(__objc_uninstalled_dtable);
 198   class->dtable = __objc_uninstalled_dtable;
 199 #else
 200   class->cache = (Cache_t)__objc_xcalloc(1, sizeof(Cache));
 201 #endif
 202 }
 203
 204 /* Send +initialize to class if not already done */
 205 static void __objc_send_initialize(Class* class)
 206 {
 207   Method_t m;
 208
 209   /* This *must* be a class object */
 210   assert(CLS_ISCLASS(class));
 211   assert(!CLS_ISMETA(class));
 212
 213   if (!CLS_ISINITIALIZED(class))
 214     {
 215       CLS_SETINITIALIZED(class);
 216       CLS_SETINITIALIZED(class->class_pointer);
 217
 218       if(class->super_class)
 219         __objc_send_initialize(class->super_class);
 220
 221       m = search_for_method_in_list(class->class_pointer->methods,
 222                                     sel_get_uid("initialize"));
 223       if(m != NULL)
 224         {
 225           CLS_SETINITIALIZED(class);
 226           (*m->method_imp) ((id) class, sel_get_uid("initialize"));
 227         }
 228     }
 229 }
 230
 231 static void
 232 __objc_install_dispatch_table_for_class (Class* class)
 233 {
 234 #ifdef OBJC_SPARSE_LOOKUP
 235   Class* super;
 236   MethodList_t mlist;
 237   int counter;
 238
 239   /* If the class has not yet had it's class links resolved, we must
 240      re-compute all class links */
 241   if(!CLS_ISRESOLV(class))
 242     __objc_resolve_class_links();
 243
 244   super = class->super_class;
 245
 246   if (super != 0 && (super->dtable == __objc_uninstalled_dtable))
 247     __objc_install_dispatch_table_for_class (super);
 248
 249   /* Allocate dtable if nessecary */
 250   if (super == 0)
 251     {
 252       class->dtable = sarray_new (__objc_selector_max_index,
 253                                   __objc_missing_method);
 254     }
 255   else
 256     class->dtable = sarray_lazy_copy (super->dtable);
 257
 258   for (mlist = class->methods; mlist; mlist = mlist->method_next)
 259     {
 260       counter = mlist->method_count - 1;
 261       while (counter >= 0)
 262         {
 263           Method_t method = &(mlist->method_list[counter]);
 264           sarray_at_put (class->dtable,
 265                          (sidx) method->method_name,
 266                          method->method_imp);
 267           counter -= 1;
 268         }
 269     }
 270 #endif
 271 }
 272
 273 void __objc_update_dispatch_table_for_class (Class* class)
 274 {
 275   Class* next;
 276 #ifdef OBJC_SPARSE_LOOKUP
 277   struct sarray* save;
 278 #else
 279   Cache_t save;
 280 #endif
 281
 282   /* not yet installed -- skip it */
 283 #ifdef OBJC_SPARSE_LOOKUP
 284   if (class->dtable == __objc_uninstalled_dtable)
 285 #else
 286   if (class->cache->mask == 0)
 287 #endif
 288     return;
 289
 290 #ifdef OBJC_SPARSE_LOOKUP
 291   save = class->dtable;
 292   __objc_install_premature_dtable (class);
 293   sarray_free (save);
 294
 295 #else
 296   save = class->cache;
 297   __objc_install_premature_dtable (class);
 298   free(save);
 299
 300 #endif
 301
 302   if (class->subclass_list)     /* Traverse subclasses */
 303     for (next = class->subclass_list; next; next = next->sibling_class)
 304       __objc_update_dispatch_table_for_class (next);
 305 }
 306
 307
 308 /* This function adds a method list to a class.  This function is
 309    typically called by another function specific to the run-time.  As
 310    such this function does not worry about thread safe issued.
 311
 312    This one is only called for categories. Class objects have their
 313    methods installed rightaway, and their selectors are made into
 314    SEL's by the function __objc_register_selectors_from_class. */
 315 void
 316 class_add_method_list (Class* class, MethodList_t list)
 317 {
 318   int i;
 319
 320   /* Passing of a linked list is not allowed.  Do multiple calls.  */
 321   assert (!list->method_next);
 322
 323   /* Check for duplicates.  */
 324   for (i = 0; i < list->method_count; ++i)
 325     {
 326       Method_t method = &list->method_list[i];
 327
 328       if (method->method_name)  /* Sometimes these are NULL */
 329         {
 330           /* This is where selector names are transmogriffed to SEL's */
 331           method->method_name = sel_register_name ((char*)method->method_name);
 332
 333           if (search_for_method_in_list (class->methods, method->method_name))
 334             {
 335               /* Duplication. Print a error message an change the method name
 336                  to NULL. */
 337               fprintf (stderr, "attempt to add a existing method: %s\n",
 338                        sel_get_name(method->method_name));
 339               method->method_name = 0;
 340             }
 341         }
 342     }
 343
 344   /* Add the methods to the class's method list.  */
 345   list->method_next = class->methods;
 346   class->methods = list;
 347 }
 348
 349
 350 Method_t
 351 class_get_instance_method(Class* class, SEL op)
 352 {
 353   return search_for_method_in_hierarchy(class, op);
 354 }
 355
 356 Method_t
 357 class_get_class_method(MetaClass* class, SEL op)
 358 {
 359   return search_for_method_in_hierarchy(class, op);
 360 }
 361
 362
 363 /* Search for a method starting from the current class up its hierarchy.
 364    Return a pointer to the method's method structure if found.  NULL
 365    otherwise. */
 366
 367 static Method_t
 368 search_for_method_in_hierarchy (Class* cls, SEL sel)
 369 {
 370   Method_t method = NULL;
 371   Class* class;
 372
 373   if (! sel_is_mapped (sel))
 374     return NULL;
 375
 376   /* Scan the method list of the class.  If the method isn't found in the
 377      list then step to its super class. */
 378   for (class = cls; ((! method) && class); class = class->super_class)
 379     method = search_for_method_in_list (class->methods, sel);
 380
 381   return method;
 382 }
 383
 384
 385
 386 /* Given a linked list of method and a method's name.  Search for the named
 387    method's method structure.  Return a pointer to the method's method
 388    structure if found.  NULL otherwise. */
 389 static Method_t
 390 search_for_method_in_list (MethodList_t list, SEL op)
 391 {
 392   MethodList_t method_list = list;
 393
 394   if (! sel_is_mapped (op))
 395     return NULL;
 396
 397   /* If not found then we'll search the list.  */
 398   while (method_list)
 399     {
 400       int i;
 401
 402       /* Search the method list.  */
 403       for (i = 0; i < method_list->method_count; ++i)
 404         {
 405           Method_t method = &method_list->method_list[i];
 406
 407           if (method->method_name)
 408             if (method->method_name == op)
 409               return method;
 410         }
 411
 412       /* The method wasn't found.  Follow the link to the next list of
 413          methods.  */
 414       method_list = method_list->method_next;
 415     }
 416
 417   return NULL;
 418 }
 419
 420
 421 /* This fuction is installed in the dispatch table for all methods which are
 422    not implemented.  Thus, it is called when a selector is not recognized. */
 423 static id
 424 __objc_missing_method (id object, SEL sel, ...)
 425 {
 426   IMP imp;
 427   SEL frwd_sel;
 428   SEL err_sel;
 429
 430   /* first try if the object understands forward:: */
 431   frwd_sel = sel_get_uid("forward::");
 432   imp = get_imp(object->class_pointer, frwd_sel);
 433   if(imp != __objc_missing_method)
 434     {
 435       void *result, *args = __builtin_apply_args();
 436       result = (*imp)(object, frwd_sel, sel, args);
 437       __builtin_return(result);
 438     }
 439
 440   /* If the object recognizes the doesNotRecognize: method then we're going
 441      to send it. */
 442   err_sel = sel_get_uid ("doesNotRecognize:");
 443   imp = get_imp (object->class_pointer, err_sel);
 444   if (imp != __objc_missing_method)
 445     {
 446       return (*imp) (object, err_sel, sel);
 447     }
 448
 449   /* The object doesn't recognize the method.  Check for responding to
 450      error:.  If it does then sent it. */
 451   {
 452     char msg[256 + strlen ((char*)sel_get_name (sel))
 453              + strlen ((char*)object->class_pointer->name)];
 454
 455     sprintf (msg, "(%s) %s does not recognize %s",
 456              (CLS_ISMETA(object->class_pointer)
 457               ? "class"
 458               : "instance" ),
 459              object->class_pointer->name, sel_get_name (sel));
 460
 461     err_sel = sel_get_uid ("error:");
 462     imp = get_imp (object->class_pointer, err_sel);
 463     if (imp != __objc_missing_method)
 464       return (*imp) (object, sel_get_uid ("error:"), msg);
 465
 466     /* The object doesn't respond to doesNotRecognize: or error:;  Therefore,
 467        a default action is taken. */
 468     fprintf (stderr, "fatal: %s\n", msg);
 469     abort ();
 470   }
 471 }
 472
 473 void __objc_print_dtable_stats()
 474 {
 475   int total = 0;
 476   printf("memory usage: (%s)\n",
 477 #ifdef OBJC_SPARSE_LOOKUP
 478 #ifdef OBJC_SPARSE2
 479          "2-level sparse arrays"
 480 #else
 481          "3-level sparse arrays"
 482 #endif
 483 #else
 484          "hash-cache"
 485 #endif
 486          );
 487
 488 #ifdef OBJC_SPARSE_LOOKUP
 489   printf("arrays: %d = %d bytes\n", narrays, narrays*sizeof(struct sarray));
 490   total += narrays*sizeof(struct sarray);
 491 #ifdef OBJC_SPARSE3
 492   printf("indices: %d = %d bytes\n", nindices, nindices*sizeof(struct sindex));
 493   total += nindices*sizeof(struct sindex);
 494 #endif
 495   printf("buckets: %d = %d bytes\n", nbuckets, nbuckets*sizeof(struct sbucket));
 496   total += nbuckets*sizeof(struct sbucket);
 497
 498   printf("idxtables: %d = %d bytes\n", idxsize, idxsize*sizeof(void*));
 499   total += idxsize*sizeof(void*);
 500 #else /* HASH_LOOKUP */
 501   total = __objc_class_hash_tables_size ();
 502 #endif
 503   printf("-----------------------------------\n");
 504   printf("total: %d bytes\n", total);
 505   printf("===================================\n");
 506 }
 507
 508 #ifdef OBJC_HASH_LOOKUP
 509 static Cache_t __objc_cache_insert(Cache_t cache, SEL op, IMP imp);
 510
 511 static Cache_t
 512 __objc_double_cache(Cache_t cache)
 513 {
 514   int i;
 515   Cache_t newc = (Cache_t)__objc_xcalloc(1, sizeof(Cache)
 516                                          +(sizeof(Cache)*2*(cache->mask+1)));
 517   newc->occupied = cache->occupied;
 518   newc->mask = ((cache->mask)<<1) | 1;
 519   for(i=0; i <= cache->mask; i++)
 520     newc = __objc_cache_insert(newc,
 521                                cache->buckets[i].method_selector,
 522                                cache->buckets[i].method_imp);
 523   free(cache);
 524   return newc;
 525 }
 526
 527
 528 static Cache_t
 529 __objc_cache_insert(Cache_t cache, SEL op, IMP imp)
 530 {
 531   int index = ((size_t)op)&(cache)->mask;
 532
 533   if(op == 0)
 534     return cache;
 535
 536   do
 537     {
 538       if((cache)->buckets[index].method_selector == 0)
 539         {
 540           (cache)->buckets[index].method_selector = op;
 541           (cache)->buckets[index].method_imp = imp;
 542           (cache)->occupied += 1;
 543           return cache;
 544         }
 545     }
 546   while (--index >= 0);
 547
 548   cache = __objc_double_cache(cache);
 549   return __objc_cache_insert(cache, op, imp);
 550 }
 551
 552 void*
 553 __objc_cache_miss(Class* class, SEL op)
 554 {
 555   Method_t m;
 556   Cache_t cache = class->cache;
 557
 558   if(!CLS_ISRESOLV(class))
 559     __objc_resolve_class_links();
 560
 561   m = search_for_method_in_hierarchy(class, op);
 562
 563   if(!CLS_ISINITIALIZED(class))
 564     if(CLS_ISMETA(class))
 565       __objc_send_initialize(objc_get_class(class->name));
 566     else
 567       __objc_send_initialize(class);
 568
 569   if(m == NULL)
 570     return __objc_missing_method;
 571
 572   if((cache->occupied+2)*2 > cache->mask)
 573     class->cache = __objc_double_cache(cache);
 574
 575   class->cache = __objc_cache_insert(class->cache, op, m->method_imp);
 576   return m->method_imp;
 577 }
 578
 579 #endif
 580
 581