Merge branch 'master' of ssh://crater.dragonflybsd.org/repository/git/dragonfly
[dragonfly.git] / contrib / gcc-3.4 / gcc / cp / search.c
1 /* Breadth-first and depth-first routines for
2    searching multiple-inheritance lattice for GNU C++.
3    Copyright (C) 1987, 1989, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
4    1999, 2000, 2002, 2003 Free Software Foundation, Inc.
5    Contributed by Michael Tiemann (tiemann@cygnus.com)
6
7 This file is part of GCC.
8
9 GCC is free software; you can redistribute it and/or modify
10 it under the terms of the GNU General Public License as published by
11 the Free Software Foundation; either version 2, or (at your option)
12 any later version.
13
14 GCC is distributed in the hope that it will be useful,
15 but WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
17 GNU General Public License for more details.
18
19 You should have received a copy of the GNU General Public License
20 along with GCC; see the file COPYING.  If not, write to
21 the Free Software Foundation, 59 Temple Place - Suite 330,
22 Boston, MA 02111-1307, USA.  */
23
24 /* High-level class interface.  */
25
26 #include "config.h"
27 #include "system.h"
28 #include "coretypes.h"
29 #include "tm.h"
30 #include "tree.h"
31 #include "cp-tree.h"
32 #include "obstack.h"
33 #include "flags.h"
34 #include "rtl.h"
35 #include "output.h"
36 #include "toplev.h"
37 #include "stack.h"
38
39 /* Obstack used for remembering decision points of breadth-first.  */
40
41 static struct obstack search_obstack;
42
43 /* Methods for pushing and popping objects to and from obstacks.  */
44
45 struct stack_level *
46 push_stack_level (struct obstack *obstack, char *tp,/* Sony NewsOS 5.0 compiler doesn't like void * here.  */
47                   int size)
48 {
49   struct stack_level *stack;
50   obstack_grow (obstack, tp, size);
51   stack = (struct stack_level *) ((char*)obstack_next_free (obstack) - size);
52   obstack_finish (obstack);
53   stack->obstack = obstack;
54   stack->first = (tree *) obstack_base (obstack);
55   stack->limit = obstack_room (obstack) / sizeof (tree *);
56   return stack;
57 }
58
59 struct stack_level *
60 pop_stack_level (struct stack_level *stack)
61 {
62   struct stack_level *tem = stack;
63   struct obstack *obstack = tem->obstack;
64   stack = tem->prev;
65   obstack_free (obstack, tem);
66   return stack;
67 }
68
69 #define search_level stack_level
70 static struct search_level *search_stack;
71
72 struct vbase_info 
73 {
74   /* The class dominating the hierarchy.  */
75   tree type;
76   /* A pointer to a complete object of the indicated TYPE.  */
77   tree decl_ptr;
78   tree inits;
79 };
80
81 static int is_subobject_of_p (tree, tree);
82 static tree dfs_check_overlap (tree, void *);
83 static tree dfs_no_overlap_yet (tree, int, void *);
84 static base_kind lookup_base_r (tree, tree, base_access, bool, tree *);
85 static int dynamic_cast_base_recurse (tree, tree, bool, tree *);
86 static tree marked_pushdecls_p (tree, int, void *);
87 static tree unmarked_pushdecls_p (tree, int, void *);
88 static tree dfs_debug_unmarkedp (tree, int, void *);
89 static tree dfs_debug_mark (tree, void *);
90 static tree dfs_push_type_decls (tree, void *);
91 static tree dfs_push_decls (tree, void *);
92 static tree dfs_unuse_fields (tree, void *);
93 static tree add_conversions (tree, void *);
94 static int look_for_overrides_r (tree, tree);
95 static struct search_level *push_search_level (struct stack_level *,
96                                                struct obstack *);
97 static struct search_level *pop_search_level (struct stack_level *);
98 static tree bfs_walk (tree, tree (*) (tree, void *),
99                       tree (*) (tree, int, void *), void *);
100 static tree lookup_field_queue_p (tree, int, void *);
101 static tree lookup_field_r (tree, void *);
102 static tree dfs_accessible_queue_p (tree, int, void *);
103 static tree dfs_accessible_p (tree, void *);
104 static tree dfs_access_in_type (tree, void *);
105 static access_kind access_in_type (tree, tree);
106 static int protected_accessible_p (tree, tree, tree);
107 static int friend_accessible_p (tree, tree, tree);
108 static void setup_class_bindings (tree, int);
109 static int template_self_reference_p (tree, tree);
110 static tree dfs_get_pure_virtuals (tree, void *);
111
112 /* Allocate a level of searching.  */
113
114 static struct search_level *
115 push_search_level (struct stack_level *stack, struct obstack *obstack)
116 {
117   struct search_level tem;
118
119   tem.prev = stack;
120   return push_stack_level (obstack, (char *)&tem, sizeof (tem));
121 }
122
123 /* Discard a level of search allocation.  */
124
125 static struct search_level *
126 pop_search_level (struct stack_level *obstack)
127 {
128   struct search_level *stack = pop_stack_level (obstack);
129
130   return stack;
131 }
132 \f
133 /* Variables for gathering statistics.  */
134 #ifdef GATHER_STATISTICS
135 static int n_fields_searched;
136 static int n_calls_lookup_field, n_calls_lookup_field_1;
137 static int n_calls_lookup_fnfields, n_calls_lookup_fnfields_1;
138 static int n_calls_get_base_type;
139 static int n_outer_fields_searched;
140 static int n_contexts_saved;
141 #endif /* GATHER_STATISTICS */
142
143 \f
144 /* Worker for lookup_base.  BINFO is the binfo we are searching at,
145    BASE is the RECORD_TYPE we are searching for.  ACCESS is the
146    required access checks.  IS_VIRTUAL indicates if BINFO is morally
147    virtual.
148
149    If BINFO is of the required type, then *BINFO_PTR is examined to
150    compare with any other instance of BASE we might have already
151    discovered. *BINFO_PTR is initialized and a base_kind return value
152    indicates what kind of base was located.
153
154    Otherwise BINFO's bases are searched.  */
155
156 static base_kind
157 lookup_base_r (tree binfo, tree base, base_access access,
158                bool is_virtual,                 /* inside a virtual part */
159                tree *binfo_ptr)
160 {
161   int i;
162   tree bases, accesses;
163   base_kind found = bk_not_base;
164   
165   if (same_type_p (BINFO_TYPE (binfo), base))
166     {
167       /* We have found a base. Check against what we have found
168          already.  */
169       found = bk_same_type;
170       if (is_virtual)
171         found = bk_via_virtual;
172       
173       if (!*binfo_ptr)
174         *binfo_ptr = binfo;
175       else if (binfo != *binfo_ptr)
176         {
177           if (access != ba_any)
178             *binfo_ptr = NULL;
179           else if (!is_virtual)
180             /* Prefer a non-virtual base.  */
181             *binfo_ptr = binfo;
182           found = bk_ambig;
183         }
184       
185       return found;
186     }
187   
188   bases = BINFO_BASETYPES (binfo);
189   accesses = BINFO_BASEACCESSES (binfo);
190   if (!bases)
191     return bk_not_base;
192   
193   for (i = TREE_VEC_LENGTH (bases); i--;)
194     {
195       tree base_binfo = TREE_VEC_ELT (bases, i);
196       base_kind bk;
197
198       bk = lookup_base_r (base_binfo, base,
199                           access,
200                           is_virtual || TREE_VIA_VIRTUAL (base_binfo),
201                           binfo_ptr);
202
203       switch (bk)
204         {
205         case bk_ambig:
206           if (access != ba_any)
207             return bk;
208           found = bk;
209           break;
210           
211         case bk_same_type:
212           bk = bk_proper_base;
213           /* FALLTHROUGH */
214         case bk_proper_base:
215           my_friendly_assert (found == bk_not_base, 20010723);
216           found = bk;
217           break;
218           
219         case bk_via_virtual:
220           if (found != bk_ambig)
221             found = bk;
222           break;
223           
224         case bk_not_base:
225           break;
226
227         default:
228           abort ();
229         }
230     }
231   return found;
232 }
233
234 /* Returns true if type BASE is accessible in T.  (BASE is known to be
235    a (possibly non-proper) base class of T.)  */
236
237 bool
238 accessible_base_p (tree t, tree base)
239 {
240   tree decl;
241
242   /* [class.access.base]
243
244      A base class is said to be accessible if an invented public
245      member of the base class is accessible.  
246
247      If BASE is a non-proper base, this condition is trivially
248      true.  */
249   if (same_type_p (t, base))
250     return true;
251   /* Rather than inventing a public member, we use the implicit
252      public typedef created in the scope of every class.  */
253   decl = TYPE_FIELDS (base);
254   while (!DECL_SELF_REFERENCE_P (decl))
255     decl = TREE_CHAIN (decl);
256   while (ANON_AGGR_TYPE_P (t))
257     t = TYPE_CONTEXT (t);
258   return accessible_p (t, decl);
259 }
260
261 /* Lookup BASE in the hierarchy dominated by T.  Do access checking as
262    ACCESS specifies.  Return the binfo we discover.  If KIND_PTR is
263    non-NULL, fill with information about what kind of base we
264    discovered.
265
266    If the base is inaccessible, or ambiguous, and the ba_quiet bit is
267    not set in ACCESS, then an error is issued and error_mark_node is
268    returned.  If the ba_quiet bit is set, then no error is issued and
269    NULL_TREE is returned.  */
270
271 tree
272 lookup_base (tree t, tree base, base_access access, base_kind *kind_ptr)
273 {
274   tree binfo = NULL;            /* The binfo we've found so far.  */
275   tree t_binfo = NULL;
276   base_kind bk;
277   
278   if (t == error_mark_node || base == error_mark_node)
279     {
280       if (kind_ptr)
281         *kind_ptr = bk_not_base;
282       return error_mark_node;
283     }
284   my_friendly_assert (TYPE_P (base), 20011127);
285   
286   if (!TYPE_P (t))
287     {
288       t_binfo = t;
289       t = BINFO_TYPE (t);
290     }
291   else 
292     t_binfo = TYPE_BINFO (t);
293
294   /* Ensure that the types are instantiated.  */
295   t = complete_type (TYPE_MAIN_VARIANT (t));
296   base = complete_type (TYPE_MAIN_VARIANT (base));
297   
298   bk = lookup_base_r (t_binfo, base, access, 0, &binfo);
299
300   /* Check that the base is unambiguous and accessible.  */
301   if (access != ba_any)
302     switch (bk)
303       {
304       case bk_not_base:
305         break;
306
307       case bk_ambig:
308         binfo = NULL_TREE;
309         if (!(access & ba_quiet))
310           {
311             error ("`%T' is an ambiguous base of `%T'", base, t);
312             binfo = error_mark_node;
313           }
314         break;
315
316       default:
317         if ((access & ~ba_quiet) != ba_ignore
318             /* If BASE is incomplete, then BASE and TYPE are probably
319                the same, in which case BASE is accessible.  If they
320                are not the same, then TYPE is invalid.  In that case,
321                there's no need to issue another error here, and
322                there's no implicit typedef to use in the code that
323                follows, so we skip the check.  */
324             && COMPLETE_TYPE_P (base)
325             && !accessible_base_p (t, base))
326           {
327             if (!(access & ba_quiet))
328               {
329                 error ("`%T' is an inaccessible base of `%T'", base, t);
330                 binfo = error_mark_node;
331               }
332             else
333               binfo = NULL_TREE;
334             bk = bk_inaccessible;
335           }
336         break;
337       }
338
339   if (kind_ptr)
340     *kind_ptr = bk;
341   
342   return binfo;
343 }
344
345 /* Worker function for get_dynamic_cast_base_type.  */
346
347 static int
348 dynamic_cast_base_recurse (tree subtype, tree binfo, bool is_via_virtual,
349                            tree *offset_ptr)
350 {
351   tree binfos, accesses;
352   int i, n_baselinks;
353   int worst = -2;
354   
355   if (BINFO_TYPE (binfo) == subtype)
356     {
357       if (is_via_virtual)
358         return -1;
359       else
360         {
361           *offset_ptr = BINFO_OFFSET (binfo);
362           return 0;
363         }
364     }
365   
366   binfos = BINFO_BASETYPES (binfo);
367   accesses = BINFO_BASEACCESSES (binfo);
368   n_baselinks = binfos ? TREE_VEC_LENGTH (binfos) : 0;
369   for (i = 0; i < n_baselinks; i++)
370     {
371       tree base_binfo = TREE_VEC_ELT (binfos, i);
372       tree base_access = TREE_VEC_ELT (accesses, i);
373       int rval;
374       
375       if (base_access != access_public_node)
376         continue;
377       rval = dynamic_cast_base_recurse
378              (subtype, base_binfo,
379               is_via_virtual || TREE_VIA_VIRTUAL (base_binfo), offset_ptr);
380       if (worst == -2)
381         worst = rval;
382       else if (rval >= 0)
383         worst = worst >= 0 ? -3 : worst;
384       else if (rval == -1)
385         worst = -1;
386       else if (rval == -3 && worst != -1)
387         worst = -3;
388     }
389   return worst;
390 }
391
392 /* The dynamic cast runtime needs a hint about how the static SUBTYPE type
393    started from is related to the required TARGET type, in order to optimize
394    the inheritance graph search. This information is independent of the
395    current context, and ignores private paths, hence get_base_distance is
396    inappropriate. Return a TREE specifying the base offset, BOFF.
397    BOFF >= 0, there is only one public non-virtual SUBTYPE base at offset BOFF,
398       and there are no public virtual SUBTYPE bases.
399    BOFF == -1, SUBTYPE occurs as multiple public virtual or non-virtual bases.
400    BOFF == -2, SUBTYPE is not a public base.
401    BOFF == -3, SUBTYPE occurs as multiple public non-virtual bases.  */
402
403 tree
404 get_dynamic_cast_base_type (tree subtype, tree target)
405 {
406   tree offset = NULL_TREE;
407   int boff = dynamic_cast_base_recurse (subtype, TYPE_BINFO (target),
408                                         false, &offset);
409   
410   if (!boff)
411     return offset;
412   offset = build_int_2 (boff, -1);
413   TREE_TYPE (offset) = ssizetype;
414   return offset;
415 }
416
417 /* Search for a member with name NAME in a multiple inheritance
418    lattice specified by TYPE.  If it does not exist, return NULL_TREE.
419    If the member is ambiguously referenced, return `error_mark_node'.
420    Otherwise, return a DECL with the indicated name.  If WANT_TYPE is
421    true, type declarations are preferred.  */
422
423 /* Do a 1-level search for NAME as a member of TYPE.  The caller must
424    figure out whether it can access this field.  (Since it is only one
425    level, this is reasonable.)  */
426
427 tree
428 lookup_field_1 (tree type, tree name, bool want_type)
429 {
430   tree field;
431
432   if (TREE_CODE (type) == TEMPLATE_TYPE_PARM
433       || TREE_CODE (type) == BOUND_TEMPLATE_TEMPLATE_PARM
434       || TREE_CODE (type) == TYPENAME_TYPE)
435     /* The TYPE_FIELDS of a TEMPLATE_TYPE_PARM and 
436        BOUND_TEMPLATE_TEMPLATE_PARM are not fields at all;
437        instead TYPE_FIELDS is the TEMPLATE_PARM_INDEX.  (Miraculously,
438        the code often worked even when we treated the index as a list
439        of fields!)
440        The TYPE_FIELDS of TYPENAME_TYPE is its TYPENAME_TYPE_FULLNAME.  */
441     return NULL_TREE;
442
443   if (TYPE_NAME (type)
444       && DECL_LANG_SPECIFIC (TYPE_NAME (type))
445       && DECL_SORTED_FIELDS (TYPE_NAME (type)))
446     {
447       tree *fields = &DECL_SORTED_FIELDS (TYPE_NAME (type))->elts[0];
448       int lo = 0, hi = DECL_SORTED_FIELDS (TYPE_NAME (type))->len;
449       int i;
450
451       while (lo < hi)
452         {
453           i = (lo + hi) / 2;
454
455 #ifdef GATHER_STATISTICS
456           n_fields_searched++;
457 #endif /* GATHER_STATISTICS */
458
459           if (DECL_NAME (fields[i]) > name)
460             hi = i;
461           else if (DECL_NAME (fields[i]) < name)
462             lo = i + 1;
463           else
464             {
465               field = NULL_TREE;
466
467               /* We might have a nested class and a field with the
468                  same name; we sorted them appropriately via
469                  field_decl_cmp, so just look for the first or last
470                  field with this name.  */
471               if (want_type)
472                 {
473                   do
474                     field = fields[i--];
475                   while (i >= lo && DECL_NAME (fields[i]) == name);
476                   if (TREE_CODE (field) != TYPE_DECL
477                       && !DECL_CLASS_TEMPLATE_P (field))
478                     field = NULL_TREE;
479                 }
480               else
481                 {
482                   do
483                     field = fields[i++];
484                   while (i < hi && DECL_NAME (fields[i]) == name);
485                 }
486               return field;
487             }
488         }
489       return NULL_TREE;
490     }
491
492   field = TYPE_FIELDS (type);
493
494 #ifdef GATHER_STATISTICS
495   n_calls_lookup_field_1++;
496 #endif /* GATHER_STATISTICS */
497   for (field = TYPE_FIELDS (type); field; field = TREE_CHAIN (field))
498     {
499 #ifdef GATHER_STATISTICS
500       n_fields_searched++;
501 #endif /* GATHER_STATISTICS */
502       my_friendly_assert (DECL_P (field), 0);
503       if (DECL_NAME (field) == NULL_TREE
504           && ANON_AGGR_TYPE_P (TREE_TYPE (field)))
505         {
506           tree temp = lookup_field_1 (TREE_TYPE (field), name, want_type);
507           if (temp)
508             return temp;
509         }
510       if (TREE_CODE (field) == USING_DECL)
511         /* For now, we're just treating member using declarations as
512            old ARM-style access declarations.  Thus, there's no reason
513            to return a USING_DECL, and the rest of the compiler can't
514            handle it.  Once the class is defined, these are purged
515            from TYPE_FIELDS anyhow; see handle_using_decl.  */
516         continue;
517
518       if (DECL_NAME (field) == name
519           && (!want_type 
520               || TREE_CODE (field) == TYPE_DECL
521               || DECL_CLASS_TEMPLATE_P (field)))
522         return field;
523     }
524   /* Not found.  */
525   if (name == vptr_identifier)
526     {
527       /* Give the user what s/he thinks s/he wants.  */
528       if (TYPE_POLYMORPHIC_P (type))
529         return TYPE_VFIELD (type);
530     }
531   return NULL_TREE;
532 }
533
534 /* There are a number of cases we need to be aware of here:
535                          current_class_type     current_function_decl
536      global                     NULL                    NULL
537      fn-local                   NULL                    SET
538      class-local                SET                     NULL
539      class->fn                  SET                     SET
540      fn->class                  SET                     SET
541
542    Those last two make life interesting.  If we're in a function which is
543    itself inside a class, we need decls to go into the fn's decls (our
544    second case below).  But if we're in a class and the class itself is
545    inside a function, we need decls to go into the decls for the class.  To
546    achieve this last goal, we must see if, when both current_class_ptr and
547    current_function_decl are set, the class was declared inside that
548    function.  If so, we know to put the decls into the class's scope.  */
549
550 tree
551 current_scope (void)
552 {
553   if (current_function_decl == NULL_TREE)
554     return current_class_type;
555   if (current_class_type == NULL_TREE)
556     return current_function_decl;
557   if ((DECL_FUNCTION_MEMBER_P (current_function_decl)
558        && same_type_p (DECL_CONTEXT (current_function_decl),
559                        current_class_type))
560       || (DECL_FRIEND_CONTEXT (current_function_decl)
561           && same_type_p (DECL_FRIEND_CONTEXT (current_function_decl),
562                           current_class_type)))
563     return current_function_decl;
564
565   return current_class_type;
566 }
567
568 /* Returns nonzero if we are currently in a function scope.  Note
569    that this function returns zero if we are within a local class, but
570    not within a member function body of the local class.  */
571
572 int
573 at_function_scope_p (void)
574 {
575   tree cs = current_scope ();
576   return cs && TREE_CODE (cs) == FUNCTION_DECL;
577 }
578
579 /* Returns true if the innermost active scope is a class scope.  */
580
581 bool
582 at_class_scope_p (void)
583 {
584   tree cs = current_scope ();
585   return cs && TYPE_P (cs);
586 }
587
588 /* Returns true if the innermost active scope is a namespace scope.  */
589
590 bool
591 at_namespace_scope_p (void)
592 {
593   /* We are in a namespace scope if we are not it a class scope or a
594      function scope.  */
595   return !current_scope();
596 }
597
598 /* Return the scope of DECL, as appropriate when doing name-lookup.  */
599
600 tree
601 context_for_name_lookup (tree decl)
602 {
603   /* [class.union]
604      
605      For the purposes of name lookup, after the anonymous union
606      definition, the members of the anonymous union are considered to
607      have been defined in the scope in which the anonymous union is
608      declared.  */ 
609   tree context = DECL_CONTEXT (decl);
610
611   while (context && TYPE_P (context) && ANON_AGGR_TYPE_P (context))
612     context = TYPE_CONTEXT (context);
613   if (!context)
614     context = global_namespace;
615
616   return context;
617 }
618
619 /* The accessibility routines use BINFO_ACCESS for scratch space
620    during the computation of the accessibility of some declaration.  */
621
622 #define BINFO_ACCESS(NODE) \
623   ((access_kind) ((TREE_PUBLIC (NODE) << 1) | TREE_PRIVATE (NODE)))
624
625 /* Set the access associated with NODE to ACCESS.  */
626
627 #define SET_BINFO_ACCESS(NODE, ACCESS)                  \
628   ((TREE_PUBLIC (NODE) = ((ACCESS) & 2) != 0),  \
629    (TREE_PRIVATE (NODE) = ((ACCESS) & 1) != 0))
630
631 /* Called from access_in_type via dfs_walk.  Calculate the access to
632    DATA (which is really a DECL) in BINFO.  */
633
634 static tree
635 dfs_access_in_type (tree binfo, void *data)
636 {
637   tree decl = (tree) data;
638   tree type = BINFO_TYPE (binfo);
639   access_kind access = ak_none;
640
641   if (context_for_name_lookup (decl) == type)
642     {
643       /* If we have descended to the scope of DECL, just note the
644          appropriate access.  */
645       if (TREE_PRIVATE (decl))
646         access = ak_private;
647       else if (TREE_PROTECTED (decl))
648         access = ak_protected;
649       else
650         access = ak_public;
651     }
652   else 
653     {
654       /* First, check for an access-declaration that gives us more
655          access to the DECL.  The CONST_DECL for an enumeration
656          constant will not have DECL_LANG_SPECIFIC, and thus no
657          DECL_ACCESS.  */
658       if (DECL_LANG_SPECIFIC (decl) && !DECL_DISCRIMINATOR_P (decl))
659         {
660           tree decl_access = purpose_member (type, DECL_ACCESS (decl));
661           
662           if (decl_access)
663             {
664               decl_access = TREE_VALUE (decl_access);
665               
666               if (decl_access == access_public_node)
667                 access = ak_public;
668               else if (decl_access == access_protected_node)
669                 access = ak_protected;
670               else if (decl_access == access_private_node)
671                 access = ak_private;
672               else
673                 my_friendly_assert (false, 20030217);
674             }
675         }
676
677       if (!access)
678         {
679           int i;
680           int n_baselinks;
681           tree binfos, accesses;
682           
683           /* Otherwise, scan our baseclasses, and pick the most favorable
684              access.  */
685           binfos = BINFO_BASETYPES (binfo);
686           accesses = BINFO_BASEACCESSES (binfo);
687           n_baselinks = binfos ? TREE_VEC_LENGTH (binfos) : 0;
688           for (i = 0; i < n_baselinks; ++i)
689             {
690               tree base_binfo = TREE_VEC_ELT (binfos, i);
691               tree base_access = TREE_VEC_ELT (accesses, i);
692               access_kind base_access_now = BINFO_ACCESS (base_binfo);
693
694               if (base_access_now == ak_none || base_access_now == ak_private)
695                 /* If it was not accessible in the base, or only
696                    accessible as a private member, we can't access it
697                    all.  */
698                 base_access_now = ak_none;
699               else if (base_access == access_protected_node)
700                 /* Public and protected members in the base become
701                    protected here.  */
702                 base_access_now = ak_protected;
703               else if (base_access == access_private_node)
704                 /* Public and protected members in the base become
705                    private here.  */
706                 base_access_now = ak_private;
707
708               /* See if the new access, via this base, gives more
709                  access than our previous best access.  */
710               if (base_access_now != ak_none
711                   && (access == ak_none || base_access_now < access))
712                 {
713                   access = base_access_now;
714
715                   /* If the new access is public, we can't do better.  */
716                   if (access == ak_public)
717                     break;
718                 }
719             }
720         }
721     }
722
723   /* Note the access to DECL in TYPE.  */
724   SET_BINFO_ACCESS (binfo, access);
725
726   /* Mark TYPE as visited so that if we reach it again we do not
727      duplicate our efforts here.  */
728   BINFO_MARKED (binfo) = 1;
729
730   return NULL_TREE;
731 }
732
733 /* Return the access to DECL in TYPE.  */
734
735 static access_kind
736 access_in_type (tree type, tree decl)
737 {
738   tree binfo = TYPE_BINFO (type);
739
740   /* We must take into account
741
742        [class.paths]
743
744        If a name can be reached by several paths through a multiple
745        inheritance graph, the access is that of the path that gives
746        most access.  
747
748     The algorithm we use is to make a post-order depth-first traversal
749     of the base-class hierarchy.  As we come up the tree, we annotate
750     each node with the most lenient access.  */
751   dfs_walk_real (binfo, 0, dfs_access_in_type, unmarkedp, decl);
752   dfs_walk (binfo, dfs_unmark, markedp,  0);
753
754   return BINFO_ACCESS (binfo);
755 }
756
757 /* Called from accessible_p via dfs_walk.  */
758
759 static tree
760 dfs_accessible_queue_p (tree derived, int ix, void *data ATTRIBUTE_UNUSED)
761 {
762   tree binfo = BINFO_BASETYPE (derived, ix);
763   
764   if (BINFO_MARKED (binfo))
765     return NULL_TREE;
766
767   /* If this class is inherited via private or protected inheritance,
768      then we can't see it, unless we are a friend of the derived class.  */
769   if (BINFO_BASEACCESS (derived, ix) != access_public_node
770       && !is_friend (BINFO_TYPE (derived), current_scope ()))
771     return NULL_TREE;
772
773   return binfo;
774 }
775
776 /* Called from accessible_p via dfs_walk.  */
777
778 static tree
779 dfs_accessible_p (tree binfo, void *data ATTRIBUTE_UNUSED)
780 {
781   access_kind access;
782
783   BINFO_MARKED (binfo) = 1;
784   access = BINFO_ACCESS (binfo);
785   if (access != ak_none
786       && is_friend (BINFO_TYPE (binfo), current_scope ()))
787     return binfo;
788
789   return NULL_TREE;
790 }
791
792 /* Returns nonzero if it is OK to access DECL through an object
793    indicated by BINFO in the context of DERIVED.  */
794
795 static int
796 protected_accessible_p (tree decl, tree derived, tree binfo)
797 {
798   access_kind access;
799
800   /* We're checking this clause from [class.access.base]
801
802        m as a member of N is protected, and the reference occurs in a
803        member or friend of class N, or in a member or friend of a
804        class P derived from N, where m as a member of P is private or
805        protected.  
806
807     Here DERIVED is a possible P and DECL is m.  accessible_p will
808     iterate over various values of N, but the access to m in DERIVED
809     does not change.
810
811     Note that I believe that the passage above is wrong, and should read
812     "...is private or protected or public"; otherwise you get bizarre results
813     whereby a public using-decl can prevent you from accessing a protected
814     member of a base.  (jason 2000/02/28)  */
815
816   /* If DERIVED isn't derived from m's class, then it can't be a P.  */
817   if (!DERIVED_FROM_P (context_for_name_lookup (decl), derived))
818     return 0;
819
820   access = access_in_type (derived, decl);
821
822   /* If m is inaccessible in DERIVED, then it's not a P.  */
823   if (access == ak_none)
824     return 0;
825   
826   /* [class.protected]
827
828      When a friend or a member function of a derived class references
829      a protected nonstatic member of a base class, an access check
830      applies in addition to those described earlier in clause
831      _class.access_) Except when forming a pointer to member
832      (_expr.unary.op_), the access must be through a pointer to,
833      reference to, or object of the derived class itself (or any class
834      derived from that class) (_expr.ref_).  If the access is to form
835      a pointer to member, the nested-name-specifier shall name the
836      derived class (or any class derived from that class).  */
837   if (DECL_NONSTATIC_MEMBER_P (decl))
838     {
839       /* We can tell through what the reference is occurring by
840          chasing BINFO up to the root.  */
841       tree t = binfo;
842       while (BINFO_INHERITANCE_CHAIN (t))
843         t = BINFO_INHERITANCE_CHAIN (t);
844       
845       if (!DERIVED_FROM_P (derived, BINFO_TYPE (t)))
846         return 0;
847     }
848
849   return 1;
850 }
851
852 /* Returns nonzero if SCOPE is a friend of a type which would be able
853    to access DECL through the object indicated by BINFO.  */
854
855 static int
856 friend_accessible_p (tree scope, tree decl, tree binfo)
857 {
858   tree befriending_classes;
859   tree t;
860
861   if (!scope)
862     return 0;
863
864   if (TREE_CODE (scope) == FUNCTION_DECL
865       || DECL_FUNCTION_TEMPLATE_P (scope))
866     befriending_classes = DECL_BEFRIENDING_CLASSES (scope);
867   else if (TYPE_P (scope))
868     befriending_classes = CLASSTYPE_BEFRIENDING_CLASSES (scope);
869   else
870     return 0;
871
872   for (t = befriending_classes; t; t = TREE_CHAIN (t))
873     if (protected_accessible_p (decl, TREE_VALUE (t), binfo))
874       return 1;
875
876   /* Nested classes are implicitly friends of their enclosing types, as
877      per core issue 45 (this is a change from the standard).  */
878   if (TYPE_P (scope))
879     for (t = TYPE_CONTEXT (scope); t && TYPE_P (t); t = TYPE_CONTEXT (t))
880       if (protected_accessible_p (decl, t, binfo))
881         return 1;
882
883   if (TREE_CODE (scope) == FUNCTION_DECL
884       || DECL_FUNCTION_TEMPLATE_P (scope))
885     {
886       /* Perhaps this SCOPE is a member of a class which is a 
887          friend.  */ 
888       if (DECL_CLASS_SCOPE_P (decl)
889           && friend_accessible_p (DECL_CONTEXT (scope), decl, binfo))
890         return 1;
891
892       /* Or an instantiation of something which is a friend.  */
893       if (DECL_TEMPLATE_INFO (scope))
894         {
895           int ret;
896           /* Increment processing_template_decl to make sure that
897              dependent_type_p works correctly.  */
898           ++processing_template_decl;
899           ret = friend_accessible_p (DECL_TI_TEMPLATE (scope), decl, binfo);
900           --processing_template_decl;
901           return ret;
902         }
903     }
904   else if (CLASSTYPE_TEMPLATE_INFO (scope))
905     {
906       int ret;
907       /* Increment processing_template_decl to make sure that
908          dependent_type_p works correctly.  */
909       ++processing_template_decl;
910       ret = friend_accessible_p (CLASSTYPE_TI_TEMPLATE (scope), decl, binfo);
911       --processing_template_decl;
912       return ret;
913     }
914
915   return 0;
916 }
917
918 /* DECL is a declaration from a base class of TYPE, which was the
919    class used to name DECL.  Return nonzero if, in the current
920    context, DECL is accessible.  If TYPE is actually a BINFO node,
921    then we can tell in what context the access is occurring by looking
922    at the most derived class along the path indicated by BINFO.  */
923
924 int 
925 accessible_p (tree type, tree decl)
926 {
927   tree binfo;
928   tree t;
929   tree scope;
930   access_kind access;
931
932   /* Nonzero if it's OK to access DECL if it has protected
933      accessibility in TYPE.  */
934   int protected_ok = 0;
935
936   /* If this declaration is in a block or namespace scope, there's no
937      access control.  */
938   if (!TYPE_P (context_for_name_lookup (decl)))
939     return 1;
940
941   /* There is no need to perform access checks inside a thunk.  */
942   scope = current_scope ();
943   if (scope && DECL_THUNK_P (scope))
944     return 1;
945
946   /* In a template declaration, we cannot be sure whether the
947      particular specialization that is instantiated will be a friend
948      or not.  Therefore, all access checks are deferred until
949      instantiation.  However, PROCESSING_TEMPLATE_DECL is set in the
950      parameter list for a template (because we may see dependent types
951      in default arguments for template parameters), and access
952      checking should be performed in the outermost parameter list.  */ 
953   if (processing_template_decl 
954       && (!processing_template_parmlist || processing_template_decl > 1))
955     return 1;
956
957   if (!TYPE_P (type))
958     {
959       binfo = type;
960       type = BINFO_TYPE (type);
961     }
962   else
963     binfo = TYPE_BINFO (type);
964
965   /* [class.access.base]
966
967      A member m is accessible when named in class N if
968
969      --m as a member of N is public, or
970
971      --m as a member of N is private, and the reference occurs in a
972        member or friend of class N, or
973
974      --m as a member of N is protected, and the reference occurs in a
975        member or friend of class N, or in a member or friend of a
976        class P derived from N, where m as a member of P is private or
977        protected, or
978
979      --there exists a base class B of N that is accessible at the point
980        of reference, and m is accessible when named in class B.  
981
982     We walk the base class hierarchy, checking these conditions.  */
983
984   /* Figure out where the reference is occurring.  Check to see if
985      DECL is private or protected in this scope, since that will
986      determine whether protected access is allowed.  */
987   if (current_class_type)
988     protected_ok = protected_accessible_p (decl, current_class_type, binfo);
989
990   /* Now, loop through the classes of which we are a friend.  */
991   if (!protected_ok)
992     protected_ok = friend_accessible_p (scope, decl, binfo);
993
994   /* Standardize the binfo that access_in_type will use.  We don't
995      need to know what path was chosen from this point onwards.  */
996   binfo = TYPE_BINFO (type);
997
998   /* Compute the accessibility of DECL in the class hierarchy
999      dominated by type.  */
1000   access = access_in_type (type, decl);
1001   if (access == ak_public
1002       || (access == ak_protected && protected_ok))
1003     return 1;
1004   else
1005     {
1006       /* Walk the hierarchy again, looking for a base class that allows
1007          access.  */
1008       t = dfs_walk (binfo, dfs_accessible_p, dfs_accessible_queue_p, 0);
1009       /* Clear any mark bits.  Note that we have to walk the whole tree
1010          here, since we have aborted the previous walk from some point
1011          deep in the tree.  */
1012       dfs_walk (binfo, dfs_unmark, 0,  0);
1013
1014       return t != NULL_TREE;
1015     }
1016 }
1017
1018 struct lookup_field_info {
1019   /* The type in which we're looking.  */
1020   tree type;
1021   /* The name of the field for which we're looking.  */
1022   tree name;
1023   /* If non-NULL, the current result of the lookup.  */
1024   tree rval;
1025   /* The path to RVAL.  */
1026   tree rval_binfo;
1027   /* If non-NULL, the lookup was ambiguous, and this is a list of the
1028      candidates.  */
1029   tree ambiguous;
1030   /* If nonzero, we are looking for types, not data members.  */
1031   int want_type;
1032   /* If something went wrong, a message indicating what.  */
1033   const char *errstr;
1034 };
1035
1036 /* Returns nonzero if BINFO is not hidden by the value found by the
1037    lookup so far.  If BINFO is hidden, then there's no need to look in
1038    it.  DATA is really a struct lookup_field_info.  Called from
1039    lookup_field via breadth_first_search.  */
1040
1041 static tree
1042 lookup_field_queue_p (tree derived, int ix, void *data)
1043 {
1044   tree binfo = BINFO_BASETYPE (derived, ix);
1045   struct lookup_field_info *lfi = (struct lookup_field_info *) data;
1046
1047   /* Don't look for constructors or destructors in base classes.  */
1048   if (IDENTIFIER_CTOR_OR_DTOR_P (lfi->name))
1049     return NULL_TREE;
1050
1051   /* If this base class is hidden by the best-known value so far, we
1052      don't need to look.  */
1053   if (lfi->rval_binfo && original_binfo (binfo, lfi->rval_binfo))
1054     return NULL_TREE;
1055
1056   /* If this is a dependent base, don't look in it.  */
1057   if (BINFO_DEPENDENT_BASE_P (binfo))
1058     return NULL_TREE;
1059   
1060   return binfo;
1061 }
1062
1063 /* Within the scope of a template class, you can refer to the to the
1064    current specialization with the name of the template itself.  For
1065    example:
1066    
1067      template <typename T> struct S { S* sp; }
1068
1069    Returns nonzero if DECL is such a declaration in a class TYPE.  */
1070
1071 static int
1072 template_self_reference_p (tree type, tree decl)
1073 {
1074   return  (CLASSTYPE_USE_TEMPLATE (type)
1075            && PRIMARY_TEMPLATE_P (CLASSTYPE_TI_TEMPLATE (type))
1076            && TREE_CODE (decl) == TYPE_DECL
1077            && DECL_ARTIFICIAL (decl)
1078            && DECL_NAME (decl) == constructor_name (type));
1079 }
1080
1081 /* Nonzero for a class member means that it is shared between all objects
1082    of that class.
1083
1084    [class.member.lookup]:If the resulting set of declarations are not all
1085    from sub-objects of the same type, or the set has a  nonstatic  member
1086    and  includes members from distinct sub-objects, there is an ambiguity
1087    and the program is ill-formed.
1088
1089    This function checks that T contains no nonstatic members.  */
1090
1091 int
1092 shared_member_p (tree t)
1093 {
1094   if (TREE_CODE (t) == VAR_DECL || TREE_CODE (t) == TYPE_DECL \
1095       || TREE_CODE (t) == CONST_DECL)
1096     return 1;
1097   if (is_overloaded_fn (t))
1098     {
1099       for (; t; t = OVL_NEXT (t))
1100         {
1101           tree fn = OVL_CURRENT (t);
1102           if (DECL_NONSTATIC_MEMBER_FUNCTION_P (fn))
1103             return 0;
1104         }
1105       return 1;
1106     }
1107   return 0;
1108 }
1109
1110 /* Routine to see if the sub-object denoted by the binfo PARENT can be
1111    found as a base class and sub-object of the object denoted by
1112    BINFO.  */
1113
1114 static int
1115 is_subobject_of_p (tree parent, tree binfo)
1116 {
1117   tree probe;
1118   
1119   for (probe = parent; probe; probe = BINFO_INHERITANCE_CHAIN (probe))
1120     {
1121       if (probe == binfo)
1122         return 1;
1123       if (TREE_VIA_VIRTUAL (probe))
1124         return (purpose_member (BINFO_TYPE (probe),
1125                                 CLASSTYPE_VBASECLASSES (BINFO_TYPE (binfo)))
1126                 != NULL_TREE);
1127     }
1128   return 0;
1129 }
1130
1131 /* DATA is really a struct lookup_field_info.  Look for a field with
1132    the name indicated there in BINFO.  If this function returns a
1133    non-NULL value it is the result of the lookup.  Called from
1134    lookup_field via breadth_first_search.  */
1135
1136 static tree
1137 lookup_field_r (tree binfo, void *data)
1138 {
1139   struct lookup_field_info *lfi = (struct lookup_field_info *) data;
1140   tree type = BINFO_TYPE (binfo);
1141   tree nval = NULL_TREE;
1142
1143   /* First, look for a function.  There can't be a function and a data
1144      member with the same name, and if there's a function and a type
1145      with the same name, the type is hidden by the function.  */
1146   if (!lfi->want_type)
1147     {
1148       int idx = lookup_fnfields_1 (type, lfi->name);
1149       if (idx >= 0)
1150         nval = TREE_VEC_ELT (CLASSTYPE_METHOD_VEC (type), idx);
1151     }
1152
1153   if (!nval)
1154     /* Look for a data member or type.  */
1155     nval = lookup_field_1 (type, lfi->name, lfi->want_type);
1156
1157   /* If there is no declaration with the indicated name in this type,
1158      then there's nothing to do.  */
1159   if (!nval)
1160     return NULL_TREE;
1161
1162   /* If we're looking up a type (as with an elaborated type specifier)
1163      we ignore all non-types we find.  */
1164   if (lfi->want_type && TREE_CODE (nval) != TYPE_DECL
1165       && !DECL_CLASS_TEMPLATE_P (nval))
1166     {
1167       if (lfi->name == TYPE_IDENTIFIER (type))
1168         {
1169           /* If the aggregate has no user defined constructors, we allow
1170              it to have fields with the same name as the enclosing type.
1171              If we are looking for that name, find the corresponding
1172              TYPE_DECL.  */
1173           for (nval = TREE_CHAIN (nval); nval; nval = TREE_CHAIN (nval))
1174             if (DECL_NAME (nval) == lfi->name
1175                 && TREE_CODE (nval) == TYPE_DECL)
1176               break;
1177         }
1178       else
1179         nval = NULL_TREE;
1180       if (!nval && CLASSTYPE_NESTED_UTDS (type) != NULL)
1181         {
1182           binding_entry e = binding_table_find (CLASSTYPE_NESTED_UTDS (type),
1183                                                 lfi->name);
1184           if (e != NULL)
1185             nval = TYPE_MAIN_DECL (e->type);
1186           else 
1187             return NULL_TREE;
1188         }
1189     }
1190
1191   /* You must name a template base class with a template-id.  */
1192   if (!same_type_p (type, lfi->type) 
1193       && template_self_reference_p (type, nval))
1194     return NULL_TREE;
1195
1196   /* If the lookup already found a match, and the new value doesn't
1197      hide the old one, we might have an ambiguity.  */
1198   if (lfi->rval_binfo
1199       && !is_subobject_of_p (lfi->rval_binfo, binfo))
1200     
1201     {
1202       if (nval == lfi->rval && shared_member_p (nval))
1203         /* The two things are really the same.  */
1204         ;
1205       else if (is_subobject_of_p (binfo, lfi->rval_binfo))
1206         /* The previous value hides the new one.  */
1207         ;
1208       else
1209         {
1210           /* We have a real ambiguity.  We keep a chain of all the
1211              candidates.  */
1212           if (!lfi->ambiguous && lfi->rval)
1213             {
1214               /* This is the first time we noticed an ambiguity.  Add
1215                  what we previously thought was a reasonable candidate
1216                  to the list.  */
1217               lfi->ambiguous = tree_cons (NULL_TREE, lfi->rval, NULL_TREE);
1218               TREE_TYPE (lfi->ambiguous) = error_mark_node;
1219             }
1220
1221           /* Add the new value.  */
1222           lfi->ambiguous = tree_cons (NULL_TREE, nval, lfi->ambiguous);
1223           TREE_TYPE (lfi->ambiguous) = error_mark_node;
1224           lfi->errstr = "request for member `%D' is ambiguous";
1225         }
1226     }
1227   else
1228     {
1229       lfi->rval = nval;
1230       lfi->rval_binfo = binfo;
1231     }
1232
1233   return NULL_TREE;
1234 }
1235
1236 /* Return a "baselink" which BASELINK_BINFO, BASELINK_ACCESS_BINFO,
1237    BASELINK_FUNCTIONS, and BASELINK_OPTYPE set to BINFO, ACCESS_BINFO,
1238    FUNCTIONS, and OPTYPE respectively.  */
1239
1240 tree
1241 build_baselink (tree binfo, tree access_binfo, tree functions, tree optype)
1242 {
1243   tree baselink;
1244
1245   my_friendly_assert (TREE_CODE (functions) == FUNCTION_DECL
1246                       || TREE_CODE (functions) == TEMPLATE_DECL
1247                       || TREE_CODE (functions) == TEMPLATE_ID_EXPR
1248                       || TREE_CODE (functions) == OVERLOAD,
1249                       20020730);
1250   my_friendly_assert (!optype || TYPE_P (optype), 20020730);
1251   my_friendly_assert (TREE_TYPE (functions), 20020805);
1252
1253   baselink = make_node (BASELINK);
1254   TREE_TYPE (baselink) = TREE_TYPE (functions);
1255   BASELINK_BINFO (baselink) = binfo;
1256   BASELINK_ACCESS_BINFO (baselink) = access_binfo;
1257   BASELINK_FUNCTIONS (baselink) = functions;
1258   BASELINK_OPTYPE (baselink) = optype;
1259
1260   return baselink;
1261 }
1262
1263 /* Look for a member named NAME in an inheritance lattice dominated by
1264    XBASETYPE.  If PROTECT is 0 or two, we do not check access.  If it
1265    is 1, we enforce accessibility.  If PROTECT is zero, then, for an
1266    ambiguous lookup, we return NULL.  If PROTECT is 1, we issue error
1267    messages about inaccessible or ambiguous lookup.  If PROTECT is 2,
1268    we return a TREE_LIST whose TREE_TYPE is error_mark_node and whose
1269    TREE_VALUEs are the list of ambiguous candidates.
1270
1271    WANT_TYPE is 1 when we should only return TYPE_DECLs.
1272
1273    If nothing can be found return NULL_TREE and do not issue an error.  */
1274
1275 tree
1276 lookup_member (tree xbasetype, tree name, int protect, bool want_type)
1277 {
1278   tree rval, rval_binfo = NULL_TREE;
1279   tree type = NULL_TREE, basetype_path = NULL_TREE;
1280   struct lookup_field_info lfi;
1281
1282   /* rval_binfo is the binfo associated with the found member, note,
1283      this can be set with useful information, even when rval is not
1284      set, because it must deal with ALL members, not just non-function
1285      members.  It is used for ambiguity checking and the hidden
1286      checks.  Whereas rval is only set if a proper (not hidden)
1287      non-function member is found.  */
1288
1289   const char *errstr = 0;
1290
1291   my_friendly_assert (TREE_CODE (name) == IDENTIFIER_NODE, 20030624);
1292
1293   if (TREE_CODE (xbasetype) == TREE_VEC)
1294     {
1295       type = BINFO_TYPE (xbasetype);
1296       basetype_path = xbasetype;
1297     }
1298   else
1299     {
1300       my_friendly_assert (IS_AGGR_TYPE_CODE (TREE_CODE (xbasetype)), 20030624);
1301       type = xbasetype;
1302       basetype_path = TYPE_BINFO (type);
1303       my_friendly_assert (!BINFO_INHERITANCE_CHAIN (basetype_path), 980827);
1304     }
1305
1306   if (type == current_class_type && TYPE_BEING_DEFINED (type)
1307       && IDENTIFIER_CLASS_VALUE (name))
1308     {
1309       tree field = IDENTIFIER_CLASS_VALUE (name);
1310       if (! is_overloaded_fn (field)
1311           && ! (want_type && TREE_CODE (field) != TYPE_DECL))
1312         /* We're in the scope of this class, and the value has already
1313            been looked up.  Just return the cached value.  */
1314         return field;
1315     }
1316
1317   complete_type (type);
1318
1319 #ifdef GATHER_STATISTICS
1320   n_calls_lookup_field++;
1321 #endif /* GATHER_STATISTICS */
1322
1323   memset (&lfi, 0, sizeof (lfi));
1324   lfi.type = type;
1325   lfi.name = name;
1326   lfi.want_type = want_type;
1327   bfs_walk (basetype_path, &lookup_field_r, &lookup_field_queue_p, &lfi);
1328   rval = lfi.rval;
1329   rval_binfo = lfi.rval_binfo;
1330   if (rval_binfo)
1331     type = BINFO_TYPE (rval_binfo);
1332   errstr = lfi.errstr;
1333
1334   /* If we are not interested in ambiguities, don't report them;
1335      just return NULL_TREE.  */
1336   if (!protect && lfi.ambiguous)
1337     return NULL_TREE;
1338   
1339   if (protect == 2) 
1340     {
1341       if (lfi.ambiguous)
1342         return lfi.ambiguous;
1343       else
1344         protect = 0;
1345     }
1346
1347   /* [class.access]
1348
1349      In the case of overloaded function names, access control is
1350      applied to the function selected by overloaded resolution.  */
1351   if (rval && protect && !is_overloaded_fn (rval))
1352     perform_or_defer_access_check (basetype_path, rval);
1353
1354   if (errstr && protect)
1355     {
1356       error (errstr, name, type);
1357       if (lfi.ambiguous)
1358         print_candidates (lfi.ambiguous);
1359       rval = error_mark_node;
1360     }
1361
1362   if (rval && is_overloaded_fn (rval)) 
1363     rval = build_baselink (rval_binfo, basetype_path, rval,
1364                            (IDENTIFIER_TYPENAME_P (name)
1365                            ? TREE_TYPE (name): NULL_TREE));
1366   return rval;
1367 }
1368
1369 /* Like lookup_member, except that if we find a function member we
1370    return NULL_TREE.  */
1371
1372 tree
1373 lookup_field (tree xbasetype, tree name, int protect, bool want_type)
1374 {
1375   tree rval = lookup_member (xbasetype, name, protect, want_type);
1376   
1377   /* Ignore functions.  */
1378   if (rval && BASELINK_P (rval))
1379     return NULL_TREE;
1380
1381   return rval;
1382 }
1383
1384 /* Like lookup_member, except that if we find a non-function member we
1385    return NULL_TREE.  */
1386
1387 tree
1388 lookup_fnfields (tree xbasetype, tree name, int protect)
1389 {
1390   tree rval = lookup_member (xbasetype, name, protect, /*want_type=*/false);
1391
1392   /* Ignore non-functions.  */
1393   if (rval && !BASELINK_P (rval))
1394     return NULL_TREE;
1395
1396   return rval;
1397 }
1398
1399 /* Return the index in the CLASSTYPE_METHOD_VEC for CLASS_TYPE
1400    corresponding to "operator TYPE ()", or -1 if there is no such
1401    operator.  Only CLASS_TYPE itself is searched; this routine does
1402    not scan the base classes of CLASS_TYPE.  */
1403
1404 static int
1405 lookup_conversion_operator (tree class_type, tree type)
1406 {
1407   int pass;
1408   int i;
1409
1410   tree methods = CLASSTYPE_METHOD_VEC (class_type);
1411
1412   for (pass = 0; pass < 2; ++pass)
1413     for (i = CLASSTYPE_FIRST_CONVERSION_SLOT; 
1414          i < TREE_VEC_LENGTH (methods);
1415          ++i)
1416       {
1417         tree fn = TREE_VEC_ELT (methods, i);
1418         /* The size of the vector may have some unused slots at the
1419            end.  */
1420         if (!fn)
1421           break;
1422
1423         /* All the conversion operators come near the beginning of the
1424            class.  Therefore, if FN is not a conversion operator, there
1425            is no matching conversion operator in CLASS_TYPE.  */
1426         fn = OVL_CURRENT (fn);
1427         if (!DECL_CONV_FN_P (fn))
1428           break;
1429         
1430         if (pass == 0)
1431           {
1432             /* On the first pass we only consider exact matches.  If
1433                the types match, this slot is the one where the right
1434                conversion operators can be found.  */
1435             if (TREE_CODE (fn) != TEMPLATE_DECL
1436                 && same_type_p (DECL_CONV_FN_TYPE (fn), type))
1437               return i;
1438           }
1439         else
1440           {
1441             /* On the second pass we look for template conversion
1442                operators.  It may be possible to instantiate the
1443                template to get the type desired.  All of the template
1444                conversion operators share a slot.  By looking for
1445                templates second we ensure that specializations are
1446                preferred over templates.  */
1447             if (TREE_CODE (fn) == TEMPLATE_DECL)
1448               return i;
1449           }
1450       }
1451
1452   return -1;
1453 }
1454
1455 /* TYPE is a class type. Return the index of the fields within
1456    the method vector with name NAME, or -1 is no such field exists.  */
1457
1458 int
1459 lookup_fnfields_1 (tree type, tree name)
1460 {
1461   tree method_vec;
1462   tree *methods;
1463   tree tmp;
1464   int i;
1465   int len;
1466
1467   if (!CLASS_TYPE_P (type))
1468     return -1;
1469
1470   method_vec = CLASSTYPE_METHOD_VEC (type);
1471
1472   if (!method_vec)
1473     return -1;
1474
1475   methods = &TREE_VEC_ELT (method_vec, 0);
1476   len = TREE_VEC_LENGTH (method_vec);
1477
1478 #ifdef GATHER_STATISTICS
1479   n_calls_lookup_fnfields_1++;
1480 #endif /* GATHER_STATISTICS */
1481
1482   /* Constructors are first...  */
1483   if (name == ctor_identifier)
1484     return (methods[CLASSTYPE_CONSTRUCTOR_SLOT] 
1485             ? CLASSTYPE_CONSTRUCTOR_SLOT : -1);
1486   /* and destructors are second.  */
1487   if (name == dtor_identifier)
1488     return (methods[CLASSTYPE_DESTRUCTOR_SLOT]
1489             ? CLASSTYPE_DESTRUCTOR_SLOT : -1);
1490   if (IDENTIFIER_TYPENAME_P (name))
1491     return lookup_conversion_operator (type, TREE_TYPE (name));
1492
1493   /* Skip the conversion operators.  */
1494   i = CLASSTYPE_FIRST_CONVERSION_SLOT;
1495   while (i < len && methods[i] && DECL_CONV_FN_P (OVL_CURRENT (methods[i])))
1496     i++;
1497
1498   /* If the type is complete, use binary search.  */
1499   if (COMPLETE_TYPE_P (type))
1500     {
1501       int lo = i;
1502       int hi = len;
1503
1504       while (lo < hi)
1505         {
1506           i = (lo + hi) / 2;
1507
1508 #ifdef GATHER_STATISTICS
1509           n_outer_fields_searched++;
1510 #endif /* GATHER_STATISTICS */
1511
1512           tmp = methods[i];
1513           /* This slot may be empty; we allocate more slots than we
1514              need.  In that case, the entry we're looking for is
1515              closer to the beginning of the list.  */
1516           if (tmp)
1517             tmp = DECL_NAME (OVL_CURRENT (tmp));
1518           if (!tmp || tmp > name)
1519             hi = i;
1520           else if (tmp < name)
1521             lo = i + 1;
1522           else
1523             return i;
1524         }
1525     }
1526   else
1527     for (; i < len && methods[i]; ++i)
1528       {
1529 #ifdef GATHER_STATISTICS
1530         n_outer_fields_searched++;
1531 #endif /* GATHER_STATISTICS */
1532         
1533         tmp = OVL_CURRENT (methods[i]);
1534         if (DECL_NAME (tmp) == name)
1535           return i;
1536       }
1537
1538   return -1;
1539 }
1540
1541 /* DECL is the result of a qualified name lookup.  QUALIFYING_SCOPE is
1542    the class or namespace used to qualify the name.  CONTEXT_CLASS is
1543    the class corresponding to the object in which DECL will be used.
1544    Return a possibly modified version of DECL that takes into account
1545    the CONTEXT_CLASS.
1546
1547    In particular, consider an expression like `B::m' in the context of
1548    a derived class `D'.  If `B::m' has been resolved to a BASELINK,
1549    then the most derived class indicated by the BASELINK_BINFO will be
1550    `B', not `D'.  This function makes that adjustment.  */
1551
1552 tree
1553 adjust_result_of_qualified_name_lookup (tree decl, 
1554                                         tree qualifying_scope,
1555                                         tree context_class)
1556 {
1557   if (context_class && CLASS_TYPE_P (qualifying_scope) 
1558       && DERIVED_FROM_P (qualifying_scope, context_class)
1559       && BASELINK_P (decl))
1560     {
1561       tree base;
1562
1563       my_friendly_assert (CLASS_TYPE_P (context_class), 20020808);
1564
1565       /* Look for the QUALIFYING_SCOPE as a base of the CONTEXT_CLASS.
1566          Because we do not yet know which function will be chosen by
1567          overload resolution, we cannot yet check either accessibility
1568          or ambiguity -- in either case, the choice of a static member
1569          function might make the usage valid.  */
1570       base = lookup_base (context_class, qualifying_scope,
1571                           ba_ignore | ba_quiet, NULL);
1572       if (base)
1573         {
1574           BASELINK_ACCESS_BINFO (decl) = base;
1575           BASELINK_BINFO (decl) 
1576             = lookup_base (base, BINFO_TYPE (BASELINK_BINFO (decl)),
1577                            ba_ignore | ba_quiet,
1578                            NULL);
1579         }
1580     }
1581
1582   return decl;
1583 }
1584
1585 \f
1586 /* Walk the class hierarchy dominated by TYPE.  FN is called for each
1587    type in the hierarchy, in a breadth-first preorder traversal.
1588    If it ever returns a non-NULL value, that value is immediately
1589    returned and the walk is terminated.  At each node, FN is passed a
1590    BINFO indicating the path from the currently visited base-class to
1591    TYPE.  Before each base-class is walked QFN is called.  If the
1592    value returned is nonzero, the base-class is walked; otherwise it
1593    is not.  If QFN is NULL, it is treated as a function which always
1594    returns 1.  Both FN and QFN are passed the DATA whenever they are
1595    called.
1596
1597    Implementation notes: Uses a circular queue, which starts off on
1598    the stack but gets moved to the malloc arena if it needs to be
1599    enlarged.  The underflow and overflow conditions are
1600    indistinguishable except by context: if head == tail and we just
1601    moved the head pointer, the queue is empty, but if we just moved
1602    the tail pointer, the queue is full.  
1603    Start with enough room for ten concurrent base classes.  That
1604    will be enough for most hierarchies.  */
1605 #define BFS_WALK_INITIAL_QUEUE_SIZE 10
1606
1607 static tree
1608 bfs_walk (tree binfo,
1609           tree (*fn) (tree, void *),
1610           tree (*qfn) (tree, int, void *),
1611           void *data)
1612 {
1613   tree rval = NULL_TREE;
1614
1615   tree bases_initial[BFS_WALK_INITIAL_QUEUE_SIZE];
1616   /* A circular queue of the base classes of BINFO.  These will be
1617      built up in breadth-first order, except where QFN prunes the
1618      search.  */
1619   size_t head, tail;
1620   size_t base_buffer_size = BFS_WALK_INITIAL_QUEUE_SIZE;
1621   tree *base_buffer = bases_initial;
1622
1623   head = tail = 0;
1624   base_buffer[tail++] = binfo;
1625
1626   while (head != tail)
1627     {
1628       int n_bases, ix;
1629       tree binfo = base_buffer[head++];
1630       if (head == base_buffer_size)
1631         head = 0;
1632
1633       /* Is this the one we're looking for?  If so, we're done.  */
1634       rval = fn (binfo, data);
1635       if (rval)
1636         goto done;
1637
1638       n_bases = BINFO_N_BASETYPES (binfo);
1639       for (ix = 0; ix != n_bases; ix++)
1640         {
1641           tree base_binfo;
1642           
1643           if (qfn)
1644             base_binfo = (*qfn) (binfo, ix, data);
1645           else
1646             base_binfo = BINFO_BASETYPE (binfo, ix);
1647           
1648           if (base_binfo)
1649             {
1650               base_buffer[tail++] = base_binfo;
1651               if (tail == base_buffer_size)
1652                 tail = 0;
1653               if (tail == head)
1654                 {
1655                   tree *new_buffer = xmalloc (2 * base_buffer_size
1656                                               * sizeof (tree));
1657                   memcpy (&new_buffer[0], &base_buffer[0],
1658                           tail * sizeof (tree));
1659                   memcpy (&new_buffer[head + base_buffer_size],
1660                           &base_buffer[head],
1661                           (base_buffer_size - head) * sizeof (tree));
1662                   if (base_buffer_size != BFS_WALK_INITIAL_QUEUE_SIZE)
1663                     free (base_buffer);
1664                   base_buffer = new_buffer;
1665                   head += base_buffer_size;
1666                   base_buffer_size *= 2;
1667                 }
1668             }
1669         }
1670     }
1671
1672  done:
1673   if (base_buffer_size != BFS_WALK_INITIAL_QUEUE_SIZE)
1674     free (base_buffer);
1675   return rval;
1676 }
1677
1678 /* Exactly like bfs_walk, except that a depth-first traversal is
1679    performed, and PREFN is called in preorder, while POSTFN is called
1680    in postorder.  */
1681
1682 tree
1683 dfs_walk_real (tree binfo,
1684                tree (*prefn) (tree, void *),
1685                tree (*postfn) (tree, void *),
1686                tree (*qfn) (tree, int, void *),
1687                void *data)
1688 {
1689   tree rval = NULL_TREE;
1690
1691   /* Call the pre-order walking function.  */
1692   if (prefn)
1693     {
1694       rval = (*prefn) (binfo, data);
1695       if (rval)
1696         return rval;
1697     }
1698
1699   /* Process the basetypes.  */
1700   if (BINFO_BASETYPES (binfo))
1701     {
1702       int i, n = TREE_VEC_LENGTH (BINFO_BASETYPES (binfo));
1703       for (i = 0; i != n; i++)
1704         {
1705           tree base_binfo;
1706       
1707           if (qfn)
1708             base_binfo = (*qfn) (binfo, i, data);
1709           else
1710             base_binfo = BINFO_BASETYPE (binfo, i);
1711           
1712           if (base_binfo)
1713             {
1714               rval = dfs_walk_real (base_binfo, prefn, postfn, qfn, data);
1715               if (rval)
1716                 return rval;
1717             }
1718         }
1719     }
1720
1721   /* Call the post-order walking function.  */
1722   if (postfn)
1723     rval = (*postfn) (binfo, data);
1724   
1725   return rval;
1726 }
1727
1728 /* Exactly like bfs_walk, except that a depth-first post-order traversal is
1729    performed.  */
1730
1731 tree
1732 dfs_walk (tree binfo,
1733           tree (*fn) (tree, void *),
1734           tree (*qfn) (tree, int, void *),
1735           void *data)
1736 {
1737   return dfs_walk_real (binfo, 0, fn, qfn, data);
1738 }
1739
1740 /* Check that virtual overrider OVERRIDER is acceptable for base function
1741    BASEFN. Issue diagnostic, and return zero, if unacceptable.  */
1742
1743 int
1744 check_final_overrider (tree overrider, tree basefn)
1745 {
1746   tree over_type = TREE_TYPE (overrider);
1747   tree base_type = TREE_TYPE (basefn);
1748   tree over_return = TREE_TYPE (over_type);
1749   tree base_return = TREE_TYPE (base_type);
1750   tree over_throw = TYPE_RAISES_EXCEPTIONS (over_type);
1751   tree base_throw = TYPE_RAISES_EXCEPTIONS (base_type);
1752   int fail = 0;
1753   
1754   if (same_type_p (base_return, over_return))
1755     /* OK */;
1756   else if ((CLASS_TYPE_P (over_return) && CLASS_TYPE_P (base_return))
1757            || (TREE_CODE (base_return) == TREE_CODE (over_return)
1758                && POINTER_TYPE_P (base_return)))
1759     {
1760       /* Potentially covariant.  */
1761       unsigned base_quals, over_quals;
1762       
1763       fail = !POINTER_TYPE_P (base_return);
1764       if (!fail)
1765         {
1766           fail = cp_type_quals (base_return) != cp_type_quals (over_return);
1767           
1768           base_return = TREE_TYPE (base_return);
1769           over_return = TREE_TYPE (over_return);
1770         }
1771       base_quals = cp_type_quals (base_return);
1772       over_quals = cp_type_quals (over_return);
1773
1774       if ((base_quals & over_quals) != over_quals)
1775         fail = 1;
1776       
1777       if (CLASS_TYPE_P (base_return) && CLASS_TYPE_P (over_return))
1778         {
1779           tree binfo = lookup_base (over_return, base_return,
1780                                     ba_check | ba_quiet, NULL);
1781
1782           if (!binfo)
1783             fail = 1;
1784         }
1785       else if (!pedantic
1786                && can_convert (TREE_TYPE (base_type), TREE_TYPE (over_type)))
1787         /* GNU extension, allow trivial pointer conversions such as
1788            converting to void *, or qualification conversion.  */
1789         {
1790           /* can_convert will permit user defined conversion from a
1791              (reference to) class type. We must reject them.  */
1792           over_return = non_reference (TREE_TYPE (over_type));
1793           if (CLASS_TYPE_P (over_return))
1794             fail = 2;
1795         }
1796       else
1797         fail = 2;
1798     }
1799   else
1800     fail = 2;
1801   if (!fail)
1802     /* OK */;
1803   else if (IDENTIFIER_ERROR_LOCUS (DECL_ASSEMBLER_NAME (overrider)))
1804     return 0;
1805   else
1806     {
1807       if (fail == 1)
1808         {
1809           cp_error_at ("invalid covariant return type for `%#D'", overrider);
1810           cp_error_at ("  overriding `%#D'", basefn);
1811         }
1812       else
1813         {
1814           cp_error_at ("conflicting return type specified for `%#D'",
1815                        overrider);
1816           cp_error_at ("  overriding `%#D'", basefn);
1817         }
1818       SET_IDENTIFIER_ERROR_LOCUS (DECL_ASSEMBLER_NAME (overrider),
1819                                   DECL_CONTEXT (overrider));
1820       return 0;
1821     }
1822   
1823   /* Check throw specifier is at least as strict.  */
1824   if (!comp_except_specs (base_throw, over_throw, 0))
1825     {
1826       if (!IDENTIFIER_ERROR_LOCUS (DECL_ASSEMBLER_NAME (overrider)))
1827         {
1828           cp_error_at ("looser throw specifier for `%#F'", overrider);
1829           cp_error_at ("  overriding `%#F'", basefn);
1830           SET_IDENTIFIER_ERROR_LOCUS (DECL_ASSEMBLER_NAME (overrider),
1831                                       DECL_CONTEXT (overrider));
1832         }
1833       return 0;
1834     }
1835   
1836   return 1;
1837 }
1838
1839 /* Given a class TYPE, and a function decl FNDECL, look for
1840    virtual functions in TYPE's hierarchy which FNDECL overrides.
1841    We do not look in TYPE itself, only its bases.
1842    
1843    Returns nonzero, if we find any. Set FNDECL's DECL_VIRTUAL_P, if we
1844    find that it overrides anything.
1845    
1846    We check that every function which is overridden, is correctly
1847    overridden.  */
1848
1849 int
1850 look_for_overrides (tree type, tree fndecl)
1851 {
1852   tree binfo = TYPE_BINFO (type);
1853   tree basebinfos = BINFO_BASETYPES (binfo);
1854   int nbasebinfos = basebinfos ? TREE_VEC_LENGTH (basebinfos) : 0;
1855   int ix;
1856   int found = 0;
1857
1858   for (ix = 0; ix != nbasebinfos; ix++)
1859     {
1860       tree basetype = BINFO_TYPE (TREE_VEC_ELT (basebinfos, ix));
1861       
1862       if (TYPE_POLYMORPHIC_P (basetype))
1863         found += look_for_overrides_r (basetype, fndecl);
1864     }
1865   return found;
1866 }
1867
1868 /* Look in TYPE for virtual functions with the same signature as
1869    FNDECL.  */
1870
1871 tree
1872 look_for_overrides_here (tree type, tree fndecl)
1873 {
1874   int ix;
1875
1876   if (DECL_MAYBE_IN_CHARGE_DESTRUCTOR_P (fndecl))
1877     ix = CLASSTYPE_DESTRUCTOR_SLOT;
1878   else
1879     ix = lookup_fnfields_1 (type, DECL_NAME (fndecl));
1880   if (ix >= 0)
1881     {
1882       tree fns = TREE_VEC_ELT (CLASSTYPE_METHOD_VEC (type), ix);
1883   
1884       for (; fns; fns = OVL_NEXT (fns))
1885         {
1886           tree fn = OVL_CURRENT (fns);
1887
1888           if (!DECL_VIRTUAL_P (fn))
1889             /* Not a virtual.  */;
1890           else if (DECL_CONTEXT (fn) != type)
1891             /* Introduced with a using declaration.  */;
1892           else if (DECL_STATIC_FUNCTION_P (fndecl))
1893             {
1894               tree btypes = TYPE_ARG_TYPES (TREE_TYPE (fn));
1895               tree dtypes = TYPE_ARG_TYPES (TREE_TYPE (fndecl));
1896               if (compparms (TREE_CHAIN (btypes), dtypes))
1897                 return fn;
1898             }
1899           else if (same_signature_p (fndecl, fn))
1900             return fn;
1901         }
1902     }
1903   return NULL_TREE;
1904 }
1905
1906 /* Look in TYPE for virtual functions overridden by FNDECL. Check both
1907    TYPE itself and its bases.  */
1908
1909 static int
1910 look_for_overrides_r (tree type, tree fndecl)
1911 {
1912   tree fn = look_for_overrides_here (type, fndecl);
1913   if (fn)
1914     {
1915       if (DECL_STATIC_FUNCTION_P (fndecl))
1916         {
1917           /* A static member function cannot match an inherited
1918              virtual member function.  */
1919           cp_error_at ("`%#D' cannot be declared", fndecl);
1920           cp_error_at ("  since `%#D' declared in base class", fn);
1921         }
1922       else
1923         {
1924           /* It's definitely virtual, even if not explicitly set.  */
1925           DECL_VIRTUAL_P (fndecl) = 1;
1926           check_final_overrider (fndecl, fn);
1927         }
1928       return 1;
1929     }
1930
1931   /* We failed to find one declared in this class. Look in its bases.  */
1932   return look_for_overrides (type, fndecl);
1933 }
1934
1935 /* Called via dfs_walk from dfs_get_pure_virtuals.  */
1936
1937 static tree
1938 dfs_get_pure_virtuals (tree binfo, void *data)
1939 {
1940   tree type = (tree) data;
1941
1942   /* We're not interested in primary base classes; the derived class
1943      of which they are a primary base will contain the information we
1944      need.  */
1945   if (!BINFO_PRIMARY_P (binfo))
1946     {
1947       tree virtuals;
1948       
1949       for (virtuals = BINFO_VIRTUALS (binfo);
1950            virtuals;
1951            virtuals = TREE_CHAIN (virtuals))
1952         if (DECL_PURE_VIRTUAL_P (BV_FN (virtuals)))
1953           CLASSTYPE_PURE_VIRTUALS (type) 
1954             = tree_cons (NULL_TREE, BV_FN (virtuals),
1955                          CLASSTYPE_PURE_VIRTUALS (type));
1956     }
1957   
1958   BINFO_MARKED (binfo) = 1;
1959
1960   return NULL_TREE;
1961 }
1962
1963 /* Set CLASSTYPE_PURE_VIRTUALS for TYPE.  */
1964
1965 void
1966 get_pure_virtuals (tree type)
1967 {
1968   tree vbases;
1969
1970   /* Clear the CLASSTYPE_PURE_VIRTUALS list; whatever is already there
1971      is going to be overridden.  */
1972   CLASSTYPE_PURE_VIRTUALS (type) = NULL_TREE;
1973   /* Now, run through all the bases which are not primary bases, and
1974      collect the pure virtual functions.  We look at the vtable in
1975      each class to determine what pure virtual functions are present.
1976      (A primary base is not interesting because the derived class of
1977      which it is a primary base will contain vtable entries for the
1978      pure virtuals in the base class.  */
1979   dfs_walk (TYPE_BINFO (type), dfs_get_pure_virtuals, unmarkedp, type);
1980   dfs_walk (TYPE_BINFO (type), dfs_unmark, markedp, type);
1981
1982   /* Put the pure virtuals in dfs order.  */
1983   CLASSTYPE_PURE_VIRTUALS (type) = nreverse (CLASSTYPE_PURE_VIRTUALS (type));
1984
1985   for (vbases = CLASSTYPE_VBASECLASSES (type); 
1986        vbases; 
1987        vbases = TREE_CHAIN (vbases))
1988     {
1989       tree virtuals;
1990
1991       for (virtuals = BINFO_VIRTUALS (TREE_VALUE (vbases));
1992            virtuals;
1993            virtuals = TREE_CHAIN (virtuals))
1994         {
1995           tree base_fndecl = BV_FN (virtuals);
1996           if (DECL_NEEDS_FINAL_OVERRIDER_P (base_fndecl))
1997             error ("`%#D' needs a final overrider", base_fndecl);
1998         }
1999     }
2000 }
2001 \f
2002 /* DEPTH-FIRST SEARCH ROUTINES.  */
2003
2004 tree 
2005 markedp (tree derived, int ix, void *data ATTRIBUTE_UNUSED) 
2006 {
2007   tree binfo = BINFO_BASETYPE (derived, ix);
2008   
2009   return BINFO_MARKED (binfo) ? binfo : NULL_TREE; 
2010 }
2011
2012 tree
2013 unmarkedp (tree derived, int ix, void *data ATTRIBUTE_UNUSED) 
2014 {
2015   tree binfo = BINFO_BASETYPE (derived, ix);
2016   
2017   return !BINFO_MARKED (binfo) ? binfo : NULL_TREE; 
2018 }
2019
2020 static tree
2021 marked_pushdecls_p (tree derived, int ix, void *data ATTRIBUTE_UNUSED)
2022 {
2023   tree binfo = BINFO_BASETYPE (derived, ix);
2024   
2025   return (!BINFO_DEPENDENT_BASE_P (binfo)
2026           && BINFO_PUSHDECLS_MARKED (binfo)) ? binfo : NULL_TREE; 
2027 }
2028
2029 static tree
2030 unmarked_pushdecls_p (tree derived, int ix, void *data ATTRIBUTE_UNUSED)
2031
2032   tree binfo = BINFO_BASETYPE (derived, ix);
2033   
2034   return (!BINFO_DEPENDENT_BASE_P (binfo)
2035           && !BINFO_PUSHDECLS_MARKED (binfo)) ? binfo : NULL_TREE;
2036 }
2037
2038 /* The worker functions for `dfs_walk'.  These do not need to
2039    test anything (vis a vis marking) if they are paired with
2040    a predicate function (above).  */
2041
2042 tree
2043 dfs_unmark (tree binfo, void *data ATTRIBUTE_UNUSED)
2044 {
2045   BINFO_MARKED (binfo) = 0;
2046   return NULL_TREE;
2047 }
2048
2049 \f
2050 /* Debug info for C++ classes can get very large; try to avoid
2051    emitting it everywhere.
2052
2053    Note that this optimization wins even when the target supports
2054    BINCL (if only slightly), and reduces the amount of work for the
2055    linker.  */
2056
2057 void
2058 maybe_suppress_debug_info (tree t)
2059 {
2060   /* We can't do the usual TYPE_DECL_SUPPRESS_DEBUG thing with DWARF, which
2061      does not support name references between translation units.  It supports
2062      symbolic references between translation units, but only within a single
2063      executable or shared library.
2064
2065      For DWARF 2, we handle TYPE_DECL_SUPPRESS_DEBUG by pretending
2066      that the type was never defined, so we only get the members we
2067      actually define.  */
2068   if (write_symbols == DWARF_DEBUG || write_symbols == NO_DEBUG)
2069     return;
2070
2071   /* We might have set this earlier in cp_finish_decl.  */
2072   TYPE_DECL_SUPPRESS_DEBUG (TYPE_MAIN_DECL (t)) = 0;
2073
2074   /* If we already know how we're handling this class, handle debug info
2075      the same way.  */
2076   if (CLASSTYPE_INTERFACE_KNOWN (t))
2077     {
2078       if (CLASSTYPE_INTERFACE_ONLY (t))
2079         TYPE_DECL_SUPPRESS_DEBUG (TYPE_MAIN_DECL (t)) = 1;
2080       /* else don't set it.  */
2081     }
2082   /* If the class has a vtable, write out the debug info along with
2083      the vtable.  */
2084   else if (TYPE_CONTAINS_VPTR_P (t))
2085     TYPE_DECL_SUPPRESS_DEBUG (TYPE_MAIN_DECL (t)) = 1;
2086
2087   /* Otherwise, just emit the debug info normally.  */
2088 }
2089
2090 /* Note that we want debugging information for a base class of a class
2091    whose vtable is being emitted.  Normally, this would happen because
2092    calling the constructor for a derived class implies calling the
2093    constructors for all bases, which involve initializing the
2094    appropriate vptr with the vtable for the base class; but in the
2095    presence of optimization, this initialization may be optimized
2096    away, so we tell finish_vtable_vardecl that we want the debugging
2097    information anyway.  */
2098
2099 static tree
2100 dfs_debug_mark (tree binfo, void *data ATTRIBUTE_UNUSED)
2101 {
2102   tree t = BINFO_TYPE (binfo);
2103
2104   CLASSTYPE_DEBUG_REQUESTED (t) = 1;
2105
2106   return NULL_TREE;
2107 }
2108
2109 /* Returns BINFO if we haven't already noted that we want debugging
2110    info for this base class.  */
2111
2112 static tree 
2113 dfs_debug_unmarkedp (tree derived, int ix, void *data ATTRIBUTE_UNUSED)
2114 {
2115   tree binfo = BINFO_BASETYPE (derived, ix);
2116   
2117   return (!CLASSTYPE_DEBUG_REQUESTED (BINFO_TYPE (binfo)) 
2118           ? binfo : NULL_TREE);
2119 }
2120
2121 /* Write out the debugging information for TYPE, whose vtable is being
2122    emitted.  Also walk through our bases and note that we want to
2123    write out information for them.  This avoids the problem of not
2124    writing any debug info for intermediate basetypes whose
2125    constructors, and thus the references to their vtables, and thus
2126    the vtables themselves, were optimized away.  */
2127
2128 void
2129 note_debug_info_needed (tree type)
2130 {
2131   if (TYPE_DECL_SUPPRESS_DEBUG (TYPE_NAME (type)))
2132     {
2133       TYPE_DECL_SUPPRESS_DEBUG (TYPE_NAME (type)) = 0;
2134       rest_of_type_compilation (type, toplevel_bindings_p ());
2135     }
2136
2137   dfs_walk (TYPE_BINFO (type), dfs_debug_mark, dfs_debug_unmarkedp, 0);
2138 }
2139 \f
2140 /* Subroutines of push_class_decls ().  */
2141
2142 static void
2143 setup_class_bindings (tree name, int type_binding_p)
2144 {
2145   tree type_binding = NULL_TREE;
2146   tree value_binding;
2147
2148   /* If we've already done the lookup for this declaration, we're
2149      done.  */
2150   if (IDENTIFIER_CLASS_VALUE (name))
2151     return;
2152
2153   /* First, deal with the type binding.  */
2154   if (type_binding_p)
2155     {
2156       type_binding = lookup_member (current_class_type, name,
2157                                     /*protect=*/2, /*want_type=*/true);
2158       if (TREE_CODE (type_binding) == TREE_LIST 
2159           && TREE_TYPE (type_binding) == error_mark_node)
2160         /* NAME is ambiguous.  */
2161         push_class_level_binding (name, type_binding);
2162       else
2163         pushdecl_class_level (type_binding);
2164     }
2165
2166   /* Now, do the value binding.  */
2167   value_binding = lookup_member (current_class_type, name,
2168                                  /*protect=*/2, /*want_type=*/false);
2169
2170   if (type_binding_p
2171       && (TREE_CODE (value_binding) == TYPE_DECL
2172           || DECL_CLASS_TEMPLATE_P (value_binding)
2173           || (TREE_CODE (value_binding) == TREE_LIST
2174               && TREE_TYPE (value_binding) == error_mark_node
2175               && (TREE_CODE (TREE_VALUE (value_binding))
2176                   == TYPE_DECL))))
2177     /* We found a type-binding, even when looking for a non-type
2178        binding.  This means that we already processed this binding
2179        above.  */;
2180   else if (value_binding)
2181     {
2182       if (TREE_CODE (value_binding) == TREE_LIST 
2183           && TREE_TYPE (value_binding) == error_mark_node)
2184         /* NAME is ambiguous.  */
2185         push_class_level_binding (name, value_binding);
2186       else
2187         {
2188           if (BASELINK_P (value_binding))
2189             /* NAME is some overloaded functions.  */
2190             value_binding = BASELINK_FUNCTIONS (value_binding);
2191           /* Two conversion operators that convert to the same type
2192              may have different names.  (See
2193              mangle_conv_op_name_for_type.)  To avoid recording the
2194              same conversion operator declaration more than once we
2195              must check to see that the same operator was not already
2196              found under another name.  */
2197           if (IDENTIFIER_TYPENAME_P (name)
2198               && is_overloaded_fn (value_binding))
2199             {
2200               tree fns;
2201               for (fns = value_binding; fns; fns = OVL_NEXT (fns))
2202                 if (IDENTIFIER_CLASS_VALUE (DECL_NAME (OVL_CURRENT (fns))))
2203                   return;
2204             }
2205           pushdecl_class_level (value_binding);
2206         }
2207     }
2208 }
2209
2210 /* Push class-level declarations for any names appearing in BINFO that
2211    are TYPE_DECLS.  */
2212
2213 static tree
2214 dfs_push_type_decls (tree binfo, void *data ATTRIBUTE_UNUSED)
2215 {
2216   tree type;
2217   tree fields;
2218
2219   type = BINFO_TYPE (binfo);
2220   for (fields = TYPE_FIELDS (type); fields; fields = TREE_CHAIN (fields))
2221     if (DECL_NAME (fields) && TREE_CODE (fields) == TYPE_DECL
2222         && !(!same_type_p (type, current_class_type)
2223              && template_self_reference_p (type, fields)))
2224       setup_class_bindings (DECL_NAME (fields), /*type_binding_p=*/1);
2225
2226   /* We can't just use BINFO_MARKED because envelope_add_decl uses
2227      DERIVED_FROM_P, which calls get_base_distance.  */
2228   BINFO_PUSHDECLS_MARKED (binfo) = 1;
2229
2230   return NULL_TREE;
2231 }
2232
2233 /* Push class-level declarations for any names appearing in BINFO that
2234    are not TYPE_DECLS.  */
2235
2236 static tree
2237 dfs_push_decls (tree binfo, void *data)
2238 {
2239   tree type = BINFO_TYPE (binfo);
2240   tree method_vec;
2241   tree fields;
2242   
2243   for (fields = TYPE_FIELDS (type); fields; fields = TREE_CHAIN (fields))
2244     if (DECL_NAME (fields) 
2245         && TREE_CODE (fields) != TYPE_DECL
2246         && TREE_CODE (fields) != USING_DECL
2247         && !DECL_ARTIFICIAL (fields))
2248       setup_class_bindings (DECL_NAME (fields), /*type_binding_p=*/0);
2249     else if (TREE_CODE (fields) == FIELD_DECL
2250              && ANON_AGGR_TYPE_P (TREE_TYPE (fields)))
2251       dfs_push_decls (TYPE_BINFO (TREE_TYPE (fields)), data);
2252   
2253   method_vec = (CLASS_TYPE_P (type) 
2254                 ? CLASSTYPE_METHOD_VEC (type) : NULL_TREE);
2255   
2256   if (method_vec && TREE_VEC_LENGTH (method_vec) >= 3)
2257     {
2258       tree *methods;
2259       tree *end;
2260       
2261       /* Farm out constructors and destructors.  */
2262       end = TREE_VEC_END (method_vec);
2263       
2264       for (methods = &TREE_VEC_ELT (method_vec, 2);
2265            methods < end && *methods;
2266            methods++)
2267         setup_class_bindings (DECL_NAME (OVL_CURRENT (*methods)), 
2268                               /*type_binding_p=*/0);
2269     }
2270
2271   BINFO_PUSHDECLS_MARKED (binfo) = 0;
2272
2273   return NULL_TREE;
2274 }
2275
2276 /* When entering the scope of a class, we cache all of the
2277    fields that that class provides within its inheritance
2278    lattice.  Where ambiguities result, we mark them
2279    with `error_mark_node' so that if they are encountered
2280    without explicit qualification, we can emit an error
2281    message.  */
2282
2283 void
2284 push_class_decls (tree type)
2285 {
2286   search_stack = push_search_level (search_stack, &search_obstack);
2287
2288   /* Enter type declarations and mark.  */
2289   dfs_walk (TYPE_BINFO (type), dfs_push_type_decls, unmarked_pushdecls_p, 0);
2290
2291   /* Enter non-type declarations and unmark.  */
2292   dfs_walk (TYPE_BINFO (type), dfs_push_decls, marked_pushdecls_p, 0);
2293 }
2294
2295 /* Here's a subroutine we need because C lacks lambdas.  */
2296
2297 static tree
2298 dfs_unuse_fields (tree binfo, void *data ATTRIBUTE_UNUSED)
2299 {
2300   tree type = TREE_TYPE (binfo);
2301   tree fields;
2302
2303   for (fields = TYPE_FIELDS (type); fields; fields = TREE_CHAIN (fields))
2304     {
2305       if (TREE_CODE (fields) != FIELD_DECL || DECL_ARTIFICIAL (fields))
2306         continue;
2307
2308       TREE_USED (fields) = 0;
2309       if (DECL_NAME (fields) == NULL_TREE
2310           && ANON_AGGR_TYPE_P (TREE_TYPE (fields)))
2311         unuse_fields (TREE_TYPE (fields));
2312     }
2313
2314   return NULL_TREE;
2315 }
2316
2317 void
2318 unuse_fields (tree type)
2319 {
2320   dfs_walk (TYPE_BINFO (type), dfs_unuse_fields, unmarkedp, 0);
2321 }
2322
2323 void
2324 pop_class_decls (void)
2325 {
2326   /* We haven't pushed a search level when dealing with cached classes,
2327      so we'd better not try to pop it.  */
2328   if (search_stack)
2329     search_stack = pop_search_level (search_stack);
2330 }
2331
2332 void
2333 print_search_statistics (void)
2334 {
2335 #ifdef GATHER_STATISTICS
2336   fprintf (stderr, "%d fields searched in %d[%d] calls to lookup_field[_1]\n",
2337            n_fields_searched, n_calls_lookup_field, n_calls_lookup_field_1);
2338   fprintf (stderr, "%d fnfields searched in %d calls to lookup_fnfields\n",
2339            n_outer_fields_searched, n_calls_lookup_fnfields);
2340   fprintf (stderr, "%d calls to get_base_type\n", n_calls_get_base_type);
2341 #else /* GATHER_STATISTICS */
2342   fprintf (stderr, "no search statistics\n");
2343 #endif /* GATHER_STATISTICS */
2344 }
2345
2346 void
2347 init_search_processing (void)
2348 {
2349   gcc_obstack_init (&search_obstack);
2350 }
2351
2352 void
2353 reinit_search_statistics (void)
2354 {
2355 #ifdef GATHER_STATISTICS
2356   n_fields_searched = 0;
2357   n_calls_lookup_field = 0, n_calls_lookup_field_1 = 0;
2358   n_calls_lookup_fnfields = 0, n_calls_lookup_fnfields_1 = 0;
2359   n_calls_get_base_type = 0;
2360   n_outer_fields_searched = 0;
2361   n_contexts_saved = 0;
2362 #endif /* GATHER_STATISTICS */
2363 }
2364
2365 static tree
2366 add_conversions (tree binfo, void *data)
2367 {
2368   int i;
2369   tree method_vec = CLASSTYPE_METHOD_VEC (BINFO_TYPE (binfo));
2370   tree *conversions = (tree *) data;
2371
2372   /* Some builtin types have no method vector, not even an empty one.  */
2373   if (!method_vec)
2374     return NULL_TREE;
2375
2376   for (i = 2; i < TREE_VEC_LENGTH (method_vec); ++i)
2377     {
2378       tree tmp = TREE_VEC_ELT (method_vec, i);
2379       tree name;
2380
2381       if (!tmp || ! DECL_CONV_FN_P (OVL_CURRENT (tmp)))
2382         break;
2383
2384       name = DECL_NAME (OVL_CURRENT (tmp));
2385
2386       /* Make sure we don't already have this conversion.  */
2387       if (! IDENTIFIER_MARKED (name))
2388         {
2389           tree t;
2390
2391           /* Make sure that we do not already have a conversion
2392              operator for this type.  Merely checking the NAME is not
2393              enough because two conversion operators to the same type
2394              may not have the same NAME.  */
2395           for (t = *conversions; t; t = TREE_CHAIN (t))
2396             {
2397               tree fn;
2398               for (fn = TREE_VALUE (t); fn; fn = OVL_NEXT (fn))
2399                 if (same_type_p (TREE_TYPE (name),
2400                                  DECL_CONV_FN_TYPE (OVL_CURRENT (fn))))
2401                   break;
2402               if (fn)
2403                 break;
2404             }
2405           if (!t)
2406             {
2407               *conversions = tree_cons (binfo, tmp, *conversions);
2408               IDENTIFIER_MARKED (name) = 1;
2409             }
2410         }
2411     }
2412   return NULL_TREE;
2413 }
2414
2415 /* Return a TREE_LIST containing all the non-hidden user-defined
2416    conversion functions for TYPE (and its base-classes).  The
2417    TREE_VALUE of each node is a FUNCTION_DECL or an OVERLOAD
2418    containing the conversion functions.  The TREE_PURPOSE is the BINFO
2419    from which the conversion functions in this node were selected.  */
2420
2421 tree
2422 lookup_conversions (tree type)
2423 {
2424   tree t;
2425   tree conversions = NULL_TREE;
2426
2427   complete_type (type);
2428   bfs_walk (TYPE_BINFO (type), add_conversions, 0, &conversions);
2429
2430   for (t = conversions; t; t = TREE_CHAIN (t))
2431     IDENTIFIER_MARKED (DECL_NAME (OVL_CURRENT (TREE_VALUE (t)))) = 0;
2432
2433   return conversions;
2434 }
2435
2436 struct overlap_info 
2437 {
2438   tree compare_type;
2439   int found_overlap;
2440 };
2441
2442 /* Check whether the empty class indicated by EMPTY_BINFO is also present
2443    at offset 0 in COMPARE_TYPE, and set found_overlap if so.  */
2444
2445 static tree
2446 dfs_check_overlap (tree empty_binfo, void *data)
2447 {
2448   struct overlap_info *oi = (struct overlap_info *) data;
2449   tree binfo;
2450   for (binfo = TYPE_BINFO (oi->compare_type); 
2451        ; 
2452        binfo = BINFO_BASETYPE (binfo, 0))
2453     {
2454       if (BINFO_TYPE (binfo) == BINFO_TYPE (empty_binfo))
2455         {
2456           oi->found_overlap = 1;
2457           break;
2458         }
2459       else if (BINFO_BASETYPES (binfo) == NULL_TREE)
2460         break;
2461     }
2462
2463   return NULL_TREE;
2464 }
2465
2466 /* Trivial function to stop base traversal when we find something.  */
2467
2468 static tree
2469 dfs_no_overlap_yet (tree derived, int ix, void *data)
2470 {
2471   tree binfo = BINFO_BASETYPE (derived, ix);
2472   struct overlap_info *oi = (struct overlap_info *) data;
2473   
2474   return !oi->found_overlap ? binfo : NULL_TREE;
2475 }
2476
2477 /* Returns nonzero if EMPTY_TYPE or any of its bases can also be found at
2478    offset 0 in NEXT_TYPE.  Used in laying out empty base class subobjects.  */
2479
2480 int
2481 types_overlap_p (tree empty_type, tree next_type)
2482 {
2483   struct overlap_info oi;
2484
2485   if (! IS_AGGR_TYPE (next_type))
2486     return 0;
2487   oi.compare_type = next_type;
2488   oi.found_overlap = 0;
2489   dfs_walk (TYPE_BINFO (empty_type), dfs_check_overlap,
2490             dfs_no_overlap_yet, &oi);
2491   return oi.found_overlap;
2492 }
2493
2494 /* Given a vtable VAR, determine which of the inherited classes the vtable
2495    inherits (in a loose sense) functions from.
2496
2497    FIXME: This does not work with the new ABI.  */
2498
2499 tree
2500 binfo_for_vtable (tree var)
2501 {
2502   tree main_binfo = TYPE_BINFO (DECL_CONTEXT (var));
2503   tree binfos = TYPE_BINFO_BASETYPES (BINFO_TYPE (main_binfo));
2504   int n_baseclasses = CLASSTYPE_N_BASECLASSES (BINFO_TYPE (main_binfo));
2505   int i;
2506
2507   for (i = 0; i < n_baseclasses; i++)
2508     {
2509       tree base_binfo = TREE_VEC_ELT (binfos, i);
2510       if (base_binfo != NULL_TREE && BINFO_VTABLE (base_binfo) == var)
2511         return base_binfo;
2512     }
2513
2514   /* If no secondary base classes matched, return the primary base, if
2515      there is one.  */
2516   if (CLASSTYPE_HAS_PRIMARY_BASE_P (BINFO_TYPE (main_binfo)))
2517     return get_primary_binfo (main_binfo);
2518
2519   return main_binfo;
2520 }
2521
2522 /* Returns the binfo of the first direct or indirect virtual base derived
2523    from BINFO, or NULL if binfo is not via virtual.  */
2524
2525 tree
2526 binfo_from_vbase (tree binfo)
2527 {
2528   for (; binfo; binfo = BINFO_INHERITANCE_CHAIN (binfo))
2529     {
2530       if (TREE_VIA_VIRTUAL (binfo))
2531         return binfo;
2532     }
2533   return NULL_TREE;
2534 }
2535
2536 /* Returns the binfo of the first direct or indirect virtual base derived
2537    from BINFO up to the TREE_TYPE, LIMIT, or NULL if binfo is not
2538    via virtual.  */
2539
2540 tree
2541 binfo_via_virtual (tree binfo, tree limit)
2542 {
2543   for (; binfo && (!limit || !same_type_p (BINFO_TYPE (binfo), limit));
2544        binfo = BINFO_INHERITANCE_CHAIN (binfo))
2545     {
2546       if (TREE_VIA_VIRTUAL (binfo))
2547         return binfo;
2548     }
2549   return NULL_TREE;
2550 }
2551
2552 /* BINFO is a base binfo in the complete type BINFO_TYPE (HERE).
2553    Find the equivalent binfo within whatever graph HERE is located.
2554    This is the inverse of original_binfo.  */
2555
2556 tree
2557 copied_binfo (tree binfo, tree here)
2558 {
2559   tree result = NULL_TREE;
2560   
2561   if (TREE_VIA_VIRTUAL (binfo))
2562     {
2563       tree t;
2564
2565       for (t = here; BINFO_INHERITANCE_CHAIN (t);
2566            t = BINFO_INHERITANCE_CHAIN (t))
2567         continue;
2568       
2569       result = purpose_member (BINFO_TYPE (binfo),
2570                                CLASSTYPE_VBASECLASSES (BINFO_TYPE (t)));
2571       result = TREE_VALUE (result);
2572     }
2573   else if (BINFO_INHERITANCE_CHAIN (binfo))
2574     {
2575       tree base_binfos;
2576       int ix, n;
2577       
2578       base_binfos = copied_binfo (BINFO_INHERITANCE_CHAIN (binfo), here);
2579       base_binfos = BINFO_BASETYPES (base_binfos);
2580       n = TREE_VEC_LENGTH (base_binfos);
2581       for (ix = 0; ix != n; ix++)
2582         {
2583           tree base = TREE_VEC_ELT (base_binfos, ix);
2584           
2585           if (BINFO_TYPE (base) == BINFO_TYPE (binfo))
2586             {
2587               result = base;
2588               break;
2589             }
2590         }
2591     }
2592   else
2593     {
2594       my_friendly_assert (BINFO_TYPE (here) == BINFO_TYPE (binfo), 20030202);
2595       result = here;
2596     }
2597
2598   my_friendly_assert (result, 20030202);
2599   return result;
2600 }
2601
2602 /* BINFO is some base binfo of HERE, within some other
2603    hierarchy. Return the equivalent binfo, but in the hierarchy
2604    dominated by HERE.  This is the inverse of copied_binfo.  If BINFO
2605    is not a base binfo of HERE, returns NULL_TREE.  */
2606
2607 tree
2608 original_binfo (tree binfo, tree here)
2609 {
2610   tree result = NULL;
2611   
2612   if (BINFO_TYPE (binfo) == BINFO_TYPE (here))
2613     result = here;
2614   else if (TREE_VIA_VIRTUAL (binfo))
2615     {
2616       result = purpose_member (BINFO_TYPE (binfo),
2617                                CLASSTYPE_VBASECLASSES (BINFO_TYPE (here)));
2618       if (result)
2619         result = TREE_VALUE (result);
2620     }
2621   else if (BINFO_INHERITANCE_CHAIN (binfo))
2622     {
2623       tree base_binfos;
2624       
2625       base_binfos = original_binfo (BINFO_INHERITANCE_CHAIN (binfo), here);
2626       if (base_binfos)
2627         {
2628           int ix, n;
2629           
2630           base_binfos = BINFO_BASETYPES (base_binfos);
2631           n = TREE_VEC_LENGTH (base_binfos);
2632           for (ix = 0; ix != n; ix++)
2633             {
2634               tree base = TREE_VEC_ELT (base_binfos, ix);
2635               
2636               if (BINFO_TYPE (base) == BINFO_TYPE (binfo))
2637                 {
2638                   result = base;
2639                   break;
2640                 }
2641             }
2642         }
2643     }
2644   
2645   return result;
2646 }
2647