OSDN Git Service

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