OSDN Git Service

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