OSDN Git Service

c84e90f5b6e35111ff82ad59ea0e18daa3101a9c
[pf3gnuchains/gcc-fork.git] / libobjc / sendmsg.c
1 /* GNU Objective C Runtime message lookup 
2    Copyright (C) 1993, 1995, 1996, 1997, 1998,
3    2001, 2002, 2004, 2009, 2010 Free Software Foundation, Inc.
4    Contributed by Kresten Krab Thorup
5
6 This file is part of GCC.
7
8 GCC 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 3, or (at your option) any later version.
11
12 GCC 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 Under Section 7 of GPL version 3, you are granted additional
18 permissions described in the GCC Runtime Library Exception, version
19 3.1, as published by the Free Software Foundation.
20
21 You should have received a copy of the GNU General Public License and
22 a copy of the GCC Runtime Library Exception along with this program;
23 see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
24 <http://www.gnu.org/licenses/>.  */
25
26 /* Uncommented the following line to enable debug logging.  Use this
27    only while debugging the runtime.  */
28 /* #define DEBUG 1 */
29
30 /* FIXME: This file has no business including tm.h.  */
31 /* FIXME: This should be using libffi instead of __builtin_apply
32    and friends.  */
33
34 #include "objc-private/common.h"
35 #include "objc-private/error.h"
36 #include "tconfig.h"
37 #include "coretypes.h"
38 #include "tm.h"
39 #include "objc/runtime.h"
40 #include "objc/message.h"          /* For objc_msg_lookup(), objc_msg_lookup_super().  */
41 #include "objc/thr.h"
42 #include "objc-private/module-abi-8.h"
43 #include "objc-private/runtime.h"
44 #include "objc-private/hash.h"
45 #include "objc-private/sarray.h"
46 #include "objc-private/selector.h" /* For sel_is_mapped() */
47 #include "runtime-info.h"
48 #include <assert.h> /* For assert */
49 #include <string.h> /* For strlen */
50
51 /* This is how we hack STRUCT_VALUE to be 1 or 0.   */
52 #define gen_rtx(args...) 1
53 #define gen_rtx_MEM(args...) 1
54 #define gen_rtx_REG(args...) 1
55 /* Already defined in gcc/coretypes.h. So prevent double definition warning.  */
56 #undef rtx
57 #define rtx int
58
59 #if ! defined (STRUCT_VALUE) || STRUCT_VALUE == 0
60 #define INVISIBLE_STRUCT_RETURN 1
61 #else
62 #define INVISIBLE_STRUCT_RETURN 0
63 #endif
64
65 /* The uninstalled dispatch table.  */
66 struct sarray *__objc_uninstalled_dtable = 0;   /* !T:MUTEX */
67
68 /* Two hooks for method forwarding. If either is set, it is invoked to
69  * return a function that performs the real forwarding.  If both are
70  * set, the result of __objc_msg_forward2 will be preferred over that
71  * of __objc_msg_forward.  If both return NULL or are unset, the
72  * libgcc based functions (__builtin_apply and friends) are used.  */
73 IMP (*__objc_msg_forward) (SEL) = NULL;
74 IMP (*__objc_msg_forward2) (id, SEL) = NULL;
75
76 /* Send +initialize to class.  */
77 static void __objc_send_initialize (Class);
78
79 /* Forward declare some functions */
80 static void __objc_install_dtable_for_class (Class cls);
81 static void __objc_prepare_dtable_for_class (Class cls);
82 static void __objc_install_prepared_dtable_for_class (Class cls);
83
84 static struct sarray *__objc_prepared_dtable_for_class (Class cls);
85 static IMP __objc_get_prepared_imp (Class cls,SEL sel);
86   
87
88 /* Various forwarding functions that are used based upon the
89    return type for the selector.
90    __objc_block_forward for structures.
91    __objc_double_forward for floats/doubles.
92    __objc_word_forward for pointers or types that fit in registers.  */
93 static double __objc_double_forward (id, SEL, ...);
94 static id __objc_word_forward (id, SEL, ...);
95 typedef struct { id many[8]; } __big;
96 #if INVISIBLE_STRUCT_RETURN 
97 static __big 
98 #else
99 static id
100 #endif
101 __objc_block_forward (id, SEL, ...);
102 static struct objc_method * search_for_method_in_hierarchy (Class class, SEL sel);
103 struct objc_method * search_for_method_in_list (struct objc_method_list * list, SEL op);
104 id nil_method (id, SEL);
105
106 /* Given a selector, return the proper forwarding implementation.  */
107 inline
108 IMP
109 __objc_get_forward_imp (id rcv, SEL sel)
110 {
111   /* If a custom forwarding hook was registered, try getting a
112      forwarding function from it. There are two forward routine hooks,
113      one that takes the receiver as an argument and one that does
114      not.  */
115   if (__objc_msg_forward2)
116     {
117       IMP result;
118       if ((result = __objc_msg_forward2 (rcv, sel)) != NULL)
119        return result;
120     }
121   if (__objc_msg_forward)
122     {
123       IMP result;
124       if ((result = __objc_msg_forward (sel)) != NULL) 
125         return result;
126     }
127
128   /* In all other cases, use the default forwarding functions built
129      using __builtin_apply and friends.  */
130     {
131       const char *t = sel->sel_types;
132       
133       if (t && (*t == '[' || *t == '(' || *t == '{')
134 #ifdef OBJC_MAX_STRUCT_BY_VALUE
135           && objc_sizeof_type (t) > OBJC_MAX_STRUCT_BY_VALUE
136 #endif
137           )
138         return (IMP)__objc_block_forward;
139       else if (t && (*t == 'f' || *t == 'd'))
140         return (IMP)__objc_double_forward;
141       else
142         return (IMP)__objc_word_forward;
143     }
144 }
145
146 /* Selectors for +resolveClassMethod: and +resolveInstanceMethod:.
147    These are set up at startup.  */
148 static SEL selector_resolveClassMethod = NULL;
149 static SEL selector_resolveInstanceMethod = NULL;
150
151 /* Internal routines use to resolve a class method using
152    +resolveClassMethod:.  'class' is always a non-Nil class (*not* a
153    meta-class), and 'sel' is the selector that we are trying to
154    resolve.  This must be called when class is not Nil, and the
155    dispatch table for class methods has already been installed.
156
157    This routine tries to call +resolveClassMethod: to give an
158    opportunity to resolve the method.  If +resolveClassMethod: returns
159    YES, it tries looking up the method again, and if found, it returns
160    it.  Else, it returns NULL.  */
161 static inline
162 IMP
163 __objc_resolve_class_method (Class class, SEL sel)
164 {
165   /* We need to lookup +resolveClassMethod:.  */
166   BOOL (*resolveMethodIMP) (id, SEL, SEL);
167
168   /* The dispatch table for class methods is already installed and we
169      don't want any forwarding to happen when looking up this method,
170      so we just look it up directly.  Note that if 'sel' is precisely
171      +resolveClassMethod:, this would look it up yet again and find
172      nothing.  That's no problem and there's no recursion.  */
173   resolveMethodIMP = (BOOL (*) (id, SEL, SEL))sarray_get_safe
174     (class->class_pointer->dtable, (size_t) selector_resolveClassMethod->sel_id);
175
176   if (resolveMethodIMP && resolveMethodIMP ((id)class, selector_resolveClassMethod, sel))
177     {
178       /* +resolveClassMethod: returned YES.  Look the method up again.
179          We already know the dtable is installed.  */
180       
181       /* TODO: There is the case where +resolveClassMethod: is buggy
182          and returned YES without actually adding the method.  We
183          could maybe print an error message.  */
184       return sarray_get_safe (class->class_pointer->dtable, (size_t) sel->sel_id);
185     }
186
187   return NULL;
188 }
189
190 /* Internal routines use to resolve a instance method using
191    +resolveInstanceMethod:.  'class' is always a non-Nil class, and
192    'sel' is the selector that we are trying to resolve.  This must be
193    called when class is not Nil, and the dispatch table for instance
194    methods has already been installed.
195
196    This routine tries to call +resolveInstanceMethod: to give an
197    opportunity to resolve the method.  If +resolveInstanceMethod:
198    returns YES, it tries looking up the method again, and if found, it
199    returns it.  Else, it returns NULL.  */
200 static inline
201 IMP
202 __objc_resolve_instance_method (Class class, SEL sel)
203 {
204   /* We need to lookup +resolveInstanceMethod:.  */
205   BOOL (*resolveMethodIMP) (id, SEL, SEL);
206
207   /* The dispatch table for class methods may not be already installed
208      so we have to install it if needed.  */
209   resolveMethodIMP = sarray_get_safe (class->class_pointer->dtable,
210                                       (size_t) selector_resolveInstanceMethod->sel_id);
211   if (resolveMethodIMP == 0)
212     {
213       /* Try again after installing the dtable.  */
214       if (class->class_pointer->dtable == __objc_uninstalled_dtable)
215         {
216           objc_mutex_lock (__objc_runtime_mutex);
217           if (class->class_pointer->dtable == __objc_uninstalled_dtable)
218             __objc_install_dtable_for_class (class->class_pointer);
219           objc_mutex_unlock (__objc_runtime_mutex);
220         }
221       resolveMethodIMP = sarray_get_safe (class->class_pointer->dtable,
222                                           (size_t) selector_resolveInstanceMethod->sel_id);           
223     }
224
225   if (resolveMethodIMP && resolveMethodIMP ((id)class, selector_resolveInstanceMethod, sel))
226     {
227       /* +resolveInstanceMethod: returned YES.  Look the method up
228          again.  We already know the dtable is installed.  */
229       
230       /* TODO: There is the case where +resolveInstanceMethod: is
231          buggy and returned YES without actually adding the method.
232          We could maybe print an error message.  */
233       return sarray_get_safe (class->dtable, (size_t) sel->sel_id);     
234     }
235
236   return NULL;
237 }
238
239 /* Given a CLASS and selector, return the implementation corresponding
240    to the method of the selector.
241
242    If CLASS is a class, the instance method is returned.
243    If CLASS is a meta class, the class method is returned.
244
245    Since this requires the dispatch table to be installed, this function
246    will implicitly invoke +initialize for CLASS if it hasn't been
247    invoked yet.  This also insures that +initialize has been invoked
248    when the returned implementation is called directly.
249
250    The forwarding hooks require the receiver as an argument (if they are to
251    perform dynamic lookup in proxy objects etc), so this function has a
252    receiver argument to be used with those hooks.  */
253 static inline
254 IMP
255 get_implementation (id receiver, Class class, SEL sel)
256 {
257   void *res;
258
259   if (class->dtable == __objc_uninstalled_dtable)
260     {
261       /* The dispatch table needs to be installed.  */
262       objc_mutex_lock (__objc_runtime_mutex);
263
264       /* Double-checked locking pattern: Check
265          __objc_uninstalled_dtable again in case another thread
266          installed the dtable while we were waiting for the lock to be
267          released.  */
268       if (class->dtable == __objc_uninstalled_dtable)
269         __objc_install_dtable_for_class (class);
270
271       /* If the dispatch table is not yet installed, we are still in
272          the process of executing +initialize.  But the implementation
273          pointer should be available in the prepared ispatch table if
274          it exists at all.  */
275       if (class->dtable == __objc_uninstalled_dtable)
276         {
277           assert (__objc_prepared_dtable_for_class (class) != 0);
278           res = __objc_get_prepared_imp (class, sel);
279         }
280       else
281         res = 0;
282
283       objc_mutex_unlock (__objc_runtime_mutex);
284       /* Call ourselves with the installed dispatch table and get the
285          real method.  */
286       if (!res)
287         res = get_implementation (receiver, class, sel);
288     }
289   else
290     {
291       /* The dispatch table has been installed.  */
292       res = sarray_get_safe (class->dtable, (size_t) sel->sel_id);
293       if (res == 0)
294         {
295           /* The dispatch table has been installed, and the method is
296              not in the dispatch table.  So the method just doesn't
297              exist for the class.  */
298
299           /* Try going through the +resolveClassMethod: or
300              +resolveInstanceMethod: process.  */
301           if (CLS_ISMETA (class))
302             {
303               /* We have the meta class, but we need to invoke the
304                  +resolveClassMethod: method on the class.  So, we
305                  need to obtain the class from the meta class, which
306                  we do using the fact that both the class and the
307                  meta-class have the same name.  */
308               Class realClass = objc_lookUpClass (class->name);
309               if (realClass)
310                 res = __objc_resolve_class_method (realClass, sel);
311             }
312           else
313             res = __objc_resolve_instance_method (class, sel);
314
315           if (res == 0)
316             res = __objc_get_forward_imp (receiver, sel);
317         }
318     }
319   return res;
320 }
321
322 inline
323 IMP
324 get_imp (Class class, SEL sel)
325 {
326   /* In a vanilla implementation we would first check if the dispatch
327      table is installed.  Here instead, to get more speed in the
328      standard case (that the dispatch table is installed) we first try
329      to get the imp using brute force.  Only if that fails, we do what
330      we should have been doing from the very beginning, that is, check
331      if the dispatch table needs to be installed, install it if it's
332      not installed, and retrieve the imp from the table if it's
333      installed.  */
334   void *res = sarray_get_safe (class->dtable, (size_t) sel->sel_id);
335   if (res == 0)
336     {
337       res = get_implementation(nil, class, sel);
338     }
339   return res;
340 }
341
342 /* The new name of get_imp().  */
343 IMP
344 class_getMethodImplementation (Class class_, SEL selector)
345 {
346   if (class_ == Nil  ||  selector == NULL)
347     return NULL;
348
349   /* get_imp is inlined, so we're good.  */
350   return get_imp (class_, selector);
351 }
352
353 /* Given a method, return its implementation.  This has been replaced
354    by method_getImplementation() in the modern API.  */
355 IMP
356 method_get_imp (struct objc_method * method)
357 {
358   return (method != (struct objc_method *)0) ? method->method_imp : (IMP)0;
359 }
360
361 /* Query if an object can respond to a selector, returns YES if the
362    object implements the selector otherwise NO.  Does not check if the
363    method can be forwarded.  Since this requires the dispatch table to
364    installed, this function will implicitly invoke +initialize for the
365    class of OBJECT if it hasn't been invoked yet.  */
366 inline
367 BOOL
368 __objc_responds_to (id object, SEL sel)
369 {
370   void *res;
371   struct sarray *dtable;
372
373   /* Install dispatch table if need be */
374   dtable = object->class_pointer->dtable;
375   if (dtable == __objc_uninstalled_dtable)
376     {
377       objc_mutex_lock (__objc_runtime_mutex);
378       if (object->class_pointer->dtable == __objc_uninstalled_dtable)
379         __objc_install_dtable_for_class (object->class_pointer);
380
381       /* If the dispatch table is not yet installed, we are still in
382          the process of executing +initialize.  Yet the dispatch table
383          should be available.  */
384       if (object->class_pointer->dtable == __objc_uninstalled_dtable)
385         {
386           dtable = __objc_prepared_dtable_for_class (object->class_pointer);
387           assert (dtable);
388         }
389       else
390         dtable = object->class_pointer->dtable;
391
392       objc_mutex_unlock (__objc_runtime_mutex);
393     }
394
395   /* Get the method from the dispatch table.  */
396   res = sarray_get_safe (dtable, (size_t) sel->sel_id);
397   return (res != 0) ? YES : NO;
398 }
399
400 BOOL
401 class_respondsToSelector (Class class_, SEL selector)
402 {
403   struct sarray *dtable;
404   void *res;
405
406   if (class_ == Nil  ||  selector == NULL)
407     return NO;
408
409   /* Install dispatch table if need be.  */
410   dtable = class_->dtable;
411   if (dtable == __objc_uninstalled_dtable)
412     {
413       objc_mutex_lock (__objc_runtime_mutex);
414       if (class_->dtable == __objc_uninstalled_dtable)
415         __objc_install_dtable_for_class (class_);
416
417       /* If the dispatch table is not yet installed,
418          we are still in the process of executing +initialize.
419          Yet the dispatch table should be available.  */
420       if (class_->dtable == __objc_uninstalled_dtable)
421         {
422           dtable = __objc_prepared_dtable_for_class (class_);
423           assert (dtable);
424         }
425       else
426         dtable = class_->dtable;
427
428       objc_mutex_unlock (__objc_runtime_mutex);
429     }
430
431   /* Get the method from the dispatch table.  */
432   res = sarray_get_safe (dtable, (size_t) selector->sel_id);
433   return (res != 0) ? YES : NO;
434 }
435
436 /* This is the lookup function.  All entries in the table are either a
437    valid method *or* zero.  If zero then either the dispatch table
438    needs to be installed or it doesn't exist and forwarding is
439    attempted.  */
440 IMP
441 objc_msg_lookup (id receiver, SEL op)
442 {
443   IMP result;
444   if (receiver)
445     {
446       /* First try a quick lookup assuming the dispatch table exists.  */
447       result = sarray_get_safe (receiver->class_pointer->dtable, 
448                                 (sidx)op->sel_id);
449       if (result == 0)
450         {
451           /* Not found ... call get_implementation () to install the
452              dispatch table and call +initialize as required,
453              providing the method implementation or a forwarding
454              function.  */
455           result = get_implementation (receiver, receiver->class_pointer, op);
456         }
457       return result;
458     }
459   else
460     return (IMP)nil_method;
461 }
462
463 IMP
464 objc_msg_lookup_super (struct objc_super *super, SEL sel)
465 {
466   if (super->self)
467     return get_imp (super->super_class, sel);
468   else
469     return (IMP)nil_method;
470 }
471
472 /* Temporarily defined here until objc_msg_sendv() goes away.  */
473 char *method_get_first_argument (struct objc_method *,
474                                  arglist_t argframe, 
475                                  const char **type);
476 char *method_get_next_argument (arglist_t argframe, 
477                                 const char **type);
478 int method_get_sizeof_arguments (struct objc_method *);
479
480 struct objc_method *
481 class_get_instance_method (Class class, SEL op);
482
483 retval_t
484 objc_msg_sendv (id object, SEL op, arglist_t arg_frame)
485 {
486   struct objc_method *m = class_get_instance_method (object->class_pointer, op);
487   const char *type;
488   *((id *) method_get_first_argument (m, arg_frame, &type)) = object;
489   *((SEL *) method_get_next_argument (arg_frame, &type)) = op;
490   return __builtin_apply ((apply_t) m->method_imp, 
491                           arg_frame,
492                           method_get_sizeof_arguments (m));
493 }
494
495 void
496 __objc_init_dispatch_tables ()
497 {
498   __objc_uninstalled_dtable = sarray_new (200, 0);
499
500   /* TODO: It would be cool to register typed selectors here.  */
501   selector_resolveClassMethod = sel_registerName ("resolveClassMethod:");
502   selector_resolveInstanceMethod = sel_registerName ("resolveInstanceMethod:");
503 }
504
505
506 /* Install dummy table for class which causes the first message to
507    that class (or instances hereof) to be initialized properly.  */
508 void
509 __objc_install_premature_dtable (Class class)
510 {
511   assert (__objc_uninstalled_dtable);
512   class->dtable = __objc_uninstalled_dtable;
513 }   
514
515 /* Send +initialize to class if not already done.  */
516 static void
517 __objc_send_initialize (Class class)
518 {
519   /* This *must* be a class object.  */
520   assert (CLS_ISCLASS (class));
521   assert (! CLS_ISMETA (class));
522
523   /* class_add_method_list/__objc_update_dispatch_table_for_class may
524      have reset the dispatch table.  The canonical way to insure that
525      we send +initialize just once, is this flag.  */
526   if (! CLS_ISINITIALIZED (class))
527     {
528       DEBUG_PRINTF ("+initialize: need to initialize class '%s'\n", class->name);
529       CLS_SETINITIALIZED (class);
530       CLS_SETINITIALIZED (class->class_pointer);
531
532       /* Create the garbage collector type memory description.  */
533       __objc_generate_gc_type_description (class);
534
535       if (class->super_class)
536         __objc_send_initialize (class->super_class);
537
538       {
539         SEL op = sel_registerName ("initialize");
540         IMP imp = 0;
541         struct objc_method_list * method_list = class->class_pointer->methods;
542         
543         while (method_list)
544           {
545             int i;
546             struct objc_method * method;
547             
548             for (i = 0; i < method_list->method_count; i++)
549               {
550                 method = &(method_list->method_list[i]);
551                 if (method->method_name
552                     && method->method_name->sel_id == op->sel_id)
553                   {
554                     imp = method->method_imp;
555                     break;
556                   }
557               }
558             
559             if (imp)
560               break;
561             
562             method_list = method_list->method_next;
563           }
564         if (imp)
565           {
566             DEBUG_PRINTF (" begin of [%s +initialize]\n", class->name);
567             (*imp) ((id) class, op);
568             DEBUG_PRINTF (" end of [%s +initialize]\n", class->name);
569           }
570 #ifdef DEBUG
571         else
572           {
573             DEBUG_PRINTF (" class '%s' has no +initialize method\n", class->name);          
574           }
575 #endif
576       }
577     }
578 }
579
580 /* Walk on the methods list of class and install the methods in the
581    reverse order of the lists.  Since methods added by categories are
582    before the methods of class in the methods list, this allows
583    categories to substitute methods declared in class.  However if
584    more than one category replaces the same method nothing is
585    guaranteed about what method will be used.  Assumes that
586    __objc_runtime_mutex is locked down.  */
587 static void
588 __objc_install_methods_in_dtable (struct sarray *dtable, struct objc_method_list * method_list)
589 {
590   int i;
591   
592   if (! method_list)
593     return;
594   
595   if (method_list->method_next)
596     __objc_install_methods_in_dtable (dtable, method_list->method_next);
597   
598   for (i = 0; i < method_list->method_count; i++)
599     {
600       struct objc_method * method = &(method_list->method_list[i]);
601       sarray_at_put_safe (dtable,
602                           (sidx) method->method_name->sel_id,
603                           method->method_imp);
604     }
605 }
606
607 void
608 __objc_update_dispatch_table_for_class (Class class)
609 {
610   Class next;
611   struct sarray *arr;
612
613   DEBUG_PRINTF (" _objc_update_dtable_for_class (%s)\n", class->name);
614
615   objc_mutex_lock (__objc_runtime_mutex);
616
617   /* Not yet installed -- skip it unless in +initialize.  */
618   if (class->dtable == __objc_uninstalled_dtable) 
619     {
620       if (__objc_prepared_dtable_for_class (class))
621         {
622           /* There is a prepared table so we must be initialising this
623              class ... we must re-do the table preparation.  */
624           __objc_prepare_dtable_for_class (class);
625         }
626       objc_mutex_unlock (__objc_runtime_mutex);
627       return;
628     }
629
630   arr = class->dtable;
631   __objc_install_premature_dtable (class); /* someone might require it... */
632   sarray_free (arr);                       /* release memory */
633   
634   /* Could have been lazy...  */
635   __objc_install_dtable_for_class (class); 
636
637   if (class->subclass_list)     /* Traverse subclasses.  */
638     for (next = class->subclass_list; next; next = next->sibling_class)
639       __objc_update_dispatch_table_for_class (next);
640
641   objc_mutex_unlock (__objc_runtime_mutex);
642 }
643
644 /* This function adds a method list to a class.  This function is
645    typically called by another function specific to the run-time.  As
646    such this function does not worry about thread safe issues.
647
648    This one is only called for categories. Class objects have their
649    methods installed right away, and their selectors are made into
650    SEL's by the function __objc_register_selectors_from_class.  */
651 void
652 class_add_method_list (Class class, struct objc_method_list * list)
653 {
654   /* Passing of a linked list is not allowed.  Do multiple calls.  */
655   assert (! list->method_next);
656
657   __objc_register_selectors_from_list(list);
658
659   /* Add the methods to the class's method list.  */
660   list->method_next = class->methods;
661   class->methods = list;
662
663   /* Update the dispatch table of class.  */
664   __objc_update_dispatch_table_for_class (class);
665 }
666
667 struct objc_method *
668 class_get_instance_method (Class class, SEL op)
669 {
670   return search_for_method_in_hierarchy (class, op);
671 }
672
673 struct objc_method *
674 class_get_class_method (MetaClass class, SEL op)
675 {
676   return search_for_method_in_hierarchy (class, op);
677 }
678
679 struct objc_method *
680 class_getInstanceMethod (Class class_, SEL selector)
681 {
682   struct objc_method *m;
683
684   if (class_ == Nil  ||  selector == NULL)
685     return NULL;
686
687   m = search_for_method_in_hierarchy (class_, selector);
688   if (m)
689     return m;
690
691   /* Try going through +resolveInstanceMethod:, and do the search
692      again if successful.  */
693   if (__objc_resolve_instance_method (class_, selector))
694     return search_for_method_in_hierarchy (class_, selector);
695
696   return NULL;
697 }
698
699 struct objc_method *
700 class_getClassMethod (Class class_, SEL selector)
701 {
702   struct objc_method *m;
703
704   if (class_ == Nil  ||  selector == NULL)
705     return NULL;
706   
707   m = search_for_method_in_hierarchy (class_->class_pointer, 
708                                       selector);
709   if (m)
710     return m;
711
712   /* Try going through +resolveClassMethod:, and do the search again
713      if successful.  */
714   if (__objc_resolve_class_method (class_, selector))
715     return search_for_method_in_hierarchy (class_->class_pointer, 
716                                            selector);    
717
718   return NULL;
719 }
720
721 BOOL
722 class_addMethod (Class class_, SEL selector, IMP implementation,
723                  const char *method_types)
724 {
725   struct objc_method_list *method_list;
726   struct objc_method *method;
727   const char *method_name;
728
729   if (class_ == Nil  ||  selector == NULL  ||  implementation == NULL  
730       || method_types == NULL  || (strcmp (method_types, "") == 0))
731     return NO;
732
733   method_name = sel_getName (selector);
734   if (method_name == NULL)
735     return NO;
736
737   /* If the method already exists in the class, return NO.  It is fine
738      if the method already exists in the superclass; in that case, we
739      are overriding it.  */
740   if (CLS_IS_IN_CONSTRUCTION (class_))
741     {
742       /* The class only contains a list of methods; they have not been
743          registered yet, ie, the method_name of each of them is still
744          a string, not a selector.  Iterate manually over them to
745          check if we have already added the method.  */
746       struct objc_method_list * method_list = class_->methods;
747       while (method_list)
748         {
749           int i;
750           
751           /* Search the method list.  */
752           for (i = 0; i < method_list->method_count; ++i)
753             {
754               struct objc_method * method = &method_list->method_list[i];
755               
756               if (method->method_name
757                   && strcmp ((char *)method->method_name, method_name) == 0)
758                 return NO;
759             }
760           
761           /* The method wasn't found.  Follow the link to the next list of
762              methods.  */
763           method_list = method_list->method_next;
764         }
765       /* The method wasn't found.  It's a new one.  Go ahead and add
766          it.  */
767     }
768   else
769     {
770       /* Do the standard lookup.  This assumes the selectors are
771          mapped.  */
772       if (search_for_method_in_list (class_->methods, selector))
773         return NO;
774     }
775
776   method_list = (struct objc_method_list *)objc_calloc (1, sizeof (struct objc_method_list));
777   method_list->method_count = 1;
778
779   method = &(method_list->method_list[0]);
780   method->method_name = objc_malloc (strlen (method_name) + 1);
781   strcpy ((char *)method->method_name, method_name);
782
783   method->method_types = objc_malloc (strlen (method_types) + 1);
784   strcpy ((char *)method->method_types, method_types);
785   
786   method->method_imp = implementation;
787   
788   if (CLS_IS_IN_CONSTRUCTION (class_))
789     {
790       /* We only need to add the method to the list.  It will be
791          registered with the runtime when the class pair is registered
792          (if ever).  */
793       method_list->method_next = class_->methods;
794       class_->methods = method_list;
795     }
796   else
797     {
798       /* Add the method to a live class.  */
799       objc_mutex_lock (__objc_runtime_mutex);
800       class_add_method_list (class_, method_list);
801       objc_mutex_unlock (__objc_runtime_mutex);
802     }
803
804   return YES;
805 }
806
807 IMP
808 class_replaceMethod (Class class_, SEL selector, IMP implementation,
809                      const char *method_types)
810 {
811   struct objc_method * method;
812
813   if (class_ == Nil  ||  selector == NULL  ||  implementation == NULL
814       || method_types == NULL)
815     return NULL;
816
817   method = search_for_method_in_hierarchy (class_, selector);
818
819   if (method)
820     {
821       return method_setImplementation (method, implementation);
822     }
823   else
824     {
825       class_addMethod (class_, selector, implementation, method_types);
826       return NULL;
827     }
828 }
829
830 /* Search for a method starting from the current class up its
831    hierarchy.  Return a pointer to the method's method structure if
832    found.  NULL otherwise.  */
833 static struct objc_method *
834 search_for_method_in_hierarchy (Class cls, SEL sel)
835 {
836   struct objc_method * method = NULL;
837   Class class;
838
839   if (! sel_is_mapped (sel))
840     return NULL;
841
842   /* Scan the method list of the class.  If the method isn't found in
843      the list then step to its super class.  */
844   for (class = cls; ((! method) && class); class = class->super_class)
845     method = search_for_method_in_list (class->methods, sel);
846
847   return method;
848 }
849
850
851
852 /* Given a linked list of method and a method's name.  Search for the
853    named method's method structure.  Return a pointer to the method's
854    method structure if found.  NULL otherwise.  */  
855 struct objc_method *
856 search_for_method_in_list (struct objc_method_list * list, SEL op)
857 {
858   struct objc_method_list * method_list = list;
859
860   if (! sel_is_mapped (op))
861     return NULL;
862
863   /* If not found then we'll search the list.  */
864   while (method_list)
865     {
866       int i;
867
868       /* Search the method list.  */
869       for (i = 0; i < method_list->method_count; ++i)
870         {
871           struct objc_method * method = &method_list->method_list[i];
872
873           if (method->method_name)
874             if (method->method_name->sel_id == op->sel_id)
875               return method;
876         }
877
878       /* The method wasn't found.  Follow the link to the next list of
879          methods.  */
880       method_list = method_list->method_next;
881     }
882
883   return NULL;
884 }
885
886 static retval_t __objc_forward (id object, SEL sel, arglist_t args);
887
888 /* Forwarding pointers/integers through the normal registers.  */
889 static id
890 __objc_word_forward (id rcv, SEL op, ...)
891 {
892   void *args, *res;
893
894   args = __builtin_apply_args ();
895   res = __objc_forward (rcv, op, args);
896   if (res)
897     __builtin_return (res);
898   else
899     return res;
900 }
901
902 /* Specific routine for forwarding floats/double because of
903    architectural differences on some processors.  i386s for example
904    which uses a floating point stack versus general registers for
905    floating point numbers.  This forward routine makes sure that GCC
906    restores the proper return values.  */
907 static double
908 __objc_double_forward (id rcv, SEL op, ...)
909 {
910   void *args, *res;
911
912   args = __builtin_apply_args ();
913   res = __objc_forward (rcv, op, args);
914   __builtin_return (res);
915 }
916
917 #if INVISIBLE_STRUCT_RETURN
918 static __big
919 #else
920 static id
921 #endif
922 __objc_block_forward (id rcv, SEL op, ...)
923 {
924   void *args, *res;
925
926   args = __builtin_apply_args ();
927   res = __objc_forward (rcv, op, args);
928   if (res)
929     __builtin_return (res);
930   else
931 #if INVISIBLE_STRUCT_RETURN
932     return (__big) {{0, 0, 0, 0, 0, 0, 0, 0}};
933 #else
934     return nil;
935 #endif
936 }
937
938
939 /* This function is installed in the dispatch table for all methods
940    which are not implemented.  Thus, it is called when a selector is
941    not recognized.  */
942 static retval_t
943 __objc_forward (id object, SEL sel, arglist_t args)
944 {
945   IMP imp;
946   static SEL frwd_sel = 0;                      /* !T:SAFE2 */
947   SEL err_sel;
948
949   /* First try if the object understands forward::.  */
950   if (! frwd_sel)
951     frwd_sel = sel_get_any_uid ("forward::");
952
953   if (__objc_responds_to (object, frwd_sel))
954     {
955       imp = get_implementation (object, object->class_pointer, frwd_sel);
956       return (*imp) (object, frwd_sel, sel, args);
957     }
958
959   /* If the object recognizes the doesNotRecognize: method then we're
960      going to send it.  */
961   err_sel = sel_get_any_uid ("doesNotRecognize:");
962   if (__objc_responds_to (object, err_sel))
963     {
964       imp = get_implementation (object, object->class_pointer, err_sel);
965       return (*imp) (object, err_sel, sel);
966     }
967   
968   /* The object doesn't recognize the method.  Check for responding to
969      error:.  If it does then sent it.  */
970   {
971     char msg[256 + strlen ((const char *) sel_getName (sel))
972              + strlen ((const char *) object->class_pointer->name)];
973
974     sprintf (msg, "(%s) %s does not recognize %s",
975              (CLS_ISMETA (object->class_pointer)
976               ? "class"
977               : "instance" ),
978              object->class_pointer->name, sel_getName (sel));
979
980     /* TODO: support for error: is surely deprecated ? */
981     err_sel = sel_get_any_uid ("error:");
982     if (__objc_responds_to (object, err_sel))
983       {
984         imp = get_implementation (object, object->class_pointer, err_sel);
985         return (*imp) (object, sel_get_any_uid ("error:"), msg);
986       }
987
988     /* The object doesn't respond to doesNotRecognize: or error:;
989        Therefore, a default action is taken.  */
990     _objc_abort ("%s\n", msg);
991
992     return 0;
993   }
994 }
995
996 void
997 __objc_print_dtable_stats (void)
998 {
999   int total = 0;
1000
1001   objc_mutex_lock (__objc_runtime_mutex);
1002
1003 #ifdef OBJC_SPARSE2
1004   printf ("memory usage: (%s)\n", "2-level sparse arrays");
1005 #else
1006   printf ("memory usage: (%s)\n", "3-level sparse arrays");
1007 #endif
1008
1009   printf ("arrays: %d = %ld bytes\n", narrays, 
1010           (long) ((size_t) narrays * sizeof (struct sarray)));
1011   total += narrays * sizeof (struct sarray);
1012   printf ("buckets: %d = %ld bytes\n", nbuckets, 
1013           (long) ((size_t) nbuckets * sizeof (struct sbucket)));
1014   total += nbuckets * sizeof (struct sbucket);
1015
1016   printf ("idxtables: %d = %ld bytes\n",
1017           idxsize, (long) ((size_t) idxsize * sizeof (void *)));
1018   total += idxsize * sizeof (void *);
1019   printf ("-----------------------------------\n");
1020   printf ("total: %d bytes\n", total);
1021   printf ("===================================\n");
1022
1023   objc_mutex_unlock (__objc_runtime_mutex);
1024 }
1025
1026 /* Returns the uninstalled dispatch table indicator.  If a class'
1027    dispatch table points to __objc_uninstalled_dtable then that means
1028    it needs its dispatch table to be installed.  */
1029 struct sarray *
1030 objc_get_uninstalled_dtable (void)
1031 {
1032   return __objc_uninstalled_dtable;
1033 }
1034
1035 static cache_ptr prepared_dtable_table = 0;
1036
1037 /* This function is called by: objc_msg_lookup, get_imp and
1038    __objc_responds_to (and the dispatch table installation functions
1039    themselves) to install a dispatch table for a class.
1040
1041    If CLS is a class, it installs instance methods.
1042    If CLS is a meta class, it installs class methods.
1043
1044    In either case +initialize is invoked for the corresponding class.
1045
1046    The implementation must insure that the dispatch table is not
1047    installed until +initialize completes.  Otherwise it opens a
1048    potential race since the installation of the dispatch table is used
1049    as gate in regular method dispatch and we need to guarantee that
1050    +initialize is the first method invoked an that no other thread my
1051    dispatch messages to the class before +initialize completes.  */
1052 static void
1053 __objc_install_dtable_for_class (Class cls)
1054 {
1055   /* If the class has not yet had its class links resolved, we must
1056      re-compute all class links.  */
1057   if (! CLS_ISRESOLV (cls))
1058     __objc_resolve_class_links ();
1059
1060   /* Make sure the super class has its dispatch table installed or is
1061      at least preparing.  We do not need to send initialize for the
1062      super class since __objc_send_initialize will insure that.  */
1063   if (cls->super_class
1064       && cls->super_class->dtable == __objc_uninstalled_dtable
1065       && !__objc_prepared_dtable_for_class (cls->super_class))
1066     {
1067       __objc_install_dtable_for_class (cls->super_class);
1068       /* The superclass initialisation may have also initialised the
1069          current class, in which case there is no more to do.  */
1070       if (cls->dtable != __objc_uninstalled_dtable)
1071         return;
1072     }
1073
1074   /* We have already been prepared but +initialize hasn't completed.
1075      The +initialize implementation is probably sending 'self'
1076      messages.  We rely on _objc_get_prepared_imp to retrieve the
1077      implementation pointers.  */
1078   if (__objc_prepared_dtable_for_class (cls))
1079     return;
1080
1081   /* We have this function cache the implementation pointers for
1082      _objc_get_prepared_imp but the dispatch table won't be initilized
1083      until __objc_send_initialize completes.  */
1084   __objc_prepare_dtable_for_class (cls);
1085
1086   /* We may have already invoked +initialize but
1087      __objc_update_dispatch_table_for_class invoked by
1088      class_add_method_list may have reset dispatch table.  */
1089
1090   /* Call +initialize.  If we are a real class, we are installing
1091      instance methods.  If we are a meta class, we are installing
1092      class methods.  The __objc_send_initialize itself will insure
1093      that the message is called only once per class.  */
1094   if (CLS_ISCLASS (cls))
1095     __objc_send_initialize (cls);
1096   else
1097     {
1098       /* Retrieve the class from the meta class.  */
1099       Class c = objc_getClass (cls->name);
1100       assert (CLS_ISMETA (cls));
1101       assert (c);
1102       __objc_send_initialize (c);
1103     }
1104
1105   /* We install the dispatch table correctly when +initialize completed.  */
1106   __objc_install_prepared_dtable_for_class (cls);
1107 }
1108
1109 /* Builds the dispatch table for the class CLS and stores it in a
1110    place where it can be retrieved by __objc_get_prepared_imp until
1111    __objc_install_prepared_dtable_for_class installs it into the
1112    class.  The dispatch table should not be installed into the class
1113    until +initialize has completed.  */
1114 static void
1115 __objc_prepare_dtable_for_class (Class cls)
1116 {
1117   struct sarray *dtable;
1118   struct sarray *super_dtable;
1119
1120   /* This table could be initialized in init.c.  We can not use the
1121      class name since the class maintains the instance methods and the
1122      meta class maintains the the class methods yet both share the
1123      same name.  Classes should be unique in any program.  */
1124   if (! prepared_dtable_table)
1125     prepared_dtable_table 
1126       = objc_hash_new (32,
1127                        (hash_func_type) objc_hash_ptr,
1128                        (compare_func_type) objc_compare_ptrs);
1129   
1130   /* If the class has not yet had its class links resolved, we must
1131      re-compute all class links.  */
1132   if (! CLS_ISRESOLV (cls))
1133     __objc_resolve_class_links ();
1134
1135   assert (cls);
1136   assert (cls->dtable == __objc_uninstalled_dtable);
1137
1138   /* If there is already a prepared dtable for this class, we must
1139      replace it with a new version (since there must have been methods
1140      added to or otherwise modified in the class while executing
1141      +initialize, and the table needs to be recomputed.  */
1142   dtable = __objc_prepared_dtable_for_class (cls);
1143   if (dtable != 0)
1144     {
1145       objc_hash_remove (prepared_dtable_table, cls);
1146       sarray_free (dtable);
1147     }
1148
1149   /* Now prepare the dtable for population.  */
1150   assert (cls != cls->super_class);
1151   if (cls->super_class)
1152     {
1153       /* Inherit the method list from the super class.  Yet the super
1154          class may still be initializing in the case when a class
1155          cluster sub class initializes its super classes.  */
1156       if (cls->super_class->dtable == __objc_uninstalled_dtable)
1157         __objc_install_dtable_for_class (cls->super_class);
1158
1159       super_dtable = cls->super_class->dtable;
1160       /* If the dispatch table is not yet installed, we are still in
1161          the process of executing +initialize.  Yet the dispatch table
1162          should be available.  */
1163       if (super_dtable == __objc_uninstalled_dtable)
1164         super_dtable = __objc_prepared_dtable_for_class (cls->super_class);
1165
1166       assert (super_dtable);
1167       dtable = sarray_lazy_copy (super_dtable);
1168     }
1169   else
1170     dtable = sarray_new (__objc_selector_max_index, 0);
1171
1172   __objc_install_methods_in_dtable (dtable, cls->methods);
1173
1174   objc_hash_add (&prepared_dtable_table,
1175                  cls,
1176                  dtable);
1177 }
1178
1179 /* This wrapper only exists to allow an easy replacement of the lookup
1180    implementation and it is expected that the compiler will optimize
1181    it away.  */
1182 static struct sarray *
1183 __objc_prepared_dtable_for_class (Class cls)
1184 {
1185   struct sarray *dtable = 0;
1186   assert (cls);
1187   if (prepared_dtable_table)
1188     dtable = objc_hash_value_for_key (prepared_dtable_table, cls);
1189   /* dtable my be nil, since we call this to check whether we are
1190      currently preparing before we start preparing.  */
1191   return dtable;
1192 }
1193
1194 /* Helper function for messages sent to CLS or implementation pointers
1195    retrieved from CLS during +initialize before the dtable is
1196    installed.  When a class implicitly initializes another class which
1197    in turn implicitly invokes methods in this class, before the
1198    implementation of +initialize of CLS completes, this returns the
1199    expected implementation.  Forwarding remains the responsibility of
1200    objc_msg_lookup.  This function should only be called under the
1201    global lock.  */
1202 static IMP
1203 __objc_get_prepared_imp (Class cls,SEL sel)
1204 {
1205   struct sarray *dtable;
1206   IMP imp;
1207
1208   assert (cls);
1209   assert (sel);
1210   assert (cls->dtable == __objc_uninstalled_dtable);
1211   dtable = __objc_prepared_dtable_for_class (cls);
1212
1213   assert (dtable);
1214   assert (dtable != __objc_uninstalled_dtable);
1215   imp = sarray_get_safe (dtable, (size_t) sel->sel_id);
1216
1217   /* imp may be Nil if the method does not exist and we may fallback
1218      to the forwarding implementation later.  */
1219   return imp;  
1220 }
1221
1222 /* When this function is called +initialize should be completed.  So
1223    now we are safe to install the dispatch table for the class so that
1224    they become available for other threads that may be waiting in the
1225    lock.  */
1226 static void
1227 __objc_install_prepared_dtable_for_class (Class cls)
1228 {
1229   assert (cls);
1230   assert (cls->dtable == __objc_uninstalled_dtable);
1231   cls->dtable = __objc_prepared_dtable_for_class (cls);
1232
1233   assert (cls->dtable);
1234   assert (cls->dtable != __objc_uninstalled_dtable);
1235   objc_hash_remove (prepared_dtable_table, cls);
1236 }