OSDN Git Service

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