OSDN Git Service

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