OSDN Git Service

2005-07-08 Daniel Berlin <dberlin@dberlin.org>
[pf3gnuchains/gcc-fork.git] / gcc / cp / class.c
1 /* Functions related to building classes and their related objects.
2    Copyright (C) 1987, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
3    1999, 2000, 2001, 2002, 2003, 2004, 2005  Free Software Foundation, Inc.
4    Contributed by Michael Tiemann (tiemann@cygnus.com)
5
6 This file is part of GCC.
7
8 GCC is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 2, or (at your option)
11 any later version.
12
13 GCC is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16 GNU General Public License for more details.
17
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING.  If not, write to
20 the Free Software Foundation, 51 Franklin Street, Fifth Floor,
21 Boston, MA 02110-1301, USA.  */
22
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 "flags.h"
33 #include "rtl.h"
34 #include "output.h"
35 #include "toplev.h"
36 #include "target.h"
37 #include "convert.h"
38 #include "cgraph.h"
39 #include "tree-dump.h"
40
41 /* The number of nested classes being processed.  If we are not in the
42    scope of any class, this is zero.  */
43
44 int current_class_depth;
45
46 /* In order to deal with nested classes, we keep a stack of classes.
47    The topmost entry is the innermost class, and is the entry at index
48    CURRENT_CLASS_DEPTH  */
49
50 typedef struct class_stack_node {
51   /* The name of the class.  */
52   tree name;
53
54   /* The _TYPE node for the class.  */
55   tree type;
56
57   /* The access specifier pending for new declarations in the scope of
58      this class.  */
59   tree access;
60
61   /* If were defining TYPE, the names used in this class.  */
62   splay_tree names_used;
63 }* class_stack_node_t;
64
65 typedef struct vtbl_init_data_s
66 {
67   /* The base for which we're building initializers.  */
68   tree binfo;
69   /* The type of the most-derived type.  */
70   tree derived;
71   /* The binfo for the dynamic type. This will be TYPE_BINFO (derived),
72      unless ctor_vtbl_p is true.  */
73   tree rtti_binfo;
74   /* The negative-index vtable initializers built up so far.  These
75      are in order from least negative index to most negative index.  */
76   tree inits;
77   /* The last (i.e., most negative) entry in INITS.  */
78   tree* last_init;
79   /* The binfo for the virtual base for which we're building
80      vcall offset initializers.  */
81   tree vbase;
82   /* The functions in vbase for which we have already provided vcall
83      offsets.  */
84   VEC(tree,gc) *fns;
85   /* The vtable index of the next vcall or vbase offset.  */
86   tree index;
87   /* Nonzero if we are building the initializer for the primary
88      vtable.  */
89   int primary_vtbl_p;
90   /* Nonzero if we are building the initializer for a construction
91      vtable.  */
92   int ctor_vtbl_p;
93   /* True when adding vcall offset entries to the vtable.  False when
94      merely computing the indices.  */
95   bool generate_vcall_entries;
96 } vtbl_init_data;
97
98 /* The type of a function passed to walk_subobject_offsets.  */
99 typedef int (*subobject_offset_fn) (tree, tree, splay_tree);
100
101 /* The stack itself.  This is a dynamically resized array.  The
102    number of elements allocated is CURRENT_CLASS_STACK_SIZE.  */
103 static int current_class_stack_size;
104 static class_stack_node_t current_class_stack;
105
106 /* An array of all local classes present in this translation unit, in
107    declaration order.  */
108 VEC(tree,gc) *local_classes;
109
110 static tree get_vfield_name (tree);
111 static void finish_struct_anon (tree);
112 static tree get_vtable_name (tree);
113 static tree get_basefndecls (tree, tree);
114 static int build_primary_vtable (tree, tree);
115 static int build_secondary_vtable (tree);
116 static void finish_vtbls (tree);
117 static void modify_vtable_entry (tree, tree, tree, tree, tree *);
118 static void finish_struct_bits (tree);
119 static int alter_access (tree, tree, tree);
120 static void handle_using_decl (tree, tree);
121 static tree dfs_modify_vtables (tree, void *);
122 static tree modify_all_vtables (tree, tree);
123 static void determine_primary_bases (tree);
124 static void finish_struct_methods (tree);
125 static void maybe_warn_about_overly_private_class (tree);
126 static int method_name_cmp (const void *, const void *);
127 static int resort_method_name_cmp (const void *, const void *);
128 static void add_implicitly_declared_members (tree, int, int);
129 static tree fixed_type_or_null (tree, int *, int *);
130 static tree resolve_address_of_overloaded_function (tree, tree, tsubst_flags_t,
131                                                     bool, tree);
132 static tree build_simple_base_path (tree expr, tree binfo);
133 static tree build_vtbl_ref_1 (tree, tree);
134 static tree build_vtbl_initializer (tree, tree, tree, tree, int *);
135 static int count_fields (tree);
136 static int add_fields_to_record_type (tree, struct sorted_fields_type*, int);
137 static void check_bitfield_decl (tree);
138 static void check_field_decl (tree, tree, int *, int *, int *);
139 static void check_field_decls (tree, tree *, int *, int *);
140 static tree *build_base_field (record_layout_info, tree, splay_tree, tree *);
141 static void build_base_fields (record_layout_info, splay_tree, tree *);
142 static void check_methods (tree);
143 static void remove_zero_width_bit_fields (tree);
144 static void check_bases (tree, int *, int *);
145 static void check_bases_and_members (tree);
146 static tree create_vtable_ptr (tree, tree *);
147 static void include_empty_classes (record_layout_info);
148 static void layout_class_type (tree, tree *);
149 static void fixup_pending_inline (tree);
150 static void fixup_inline_methods (tree);
151 static void propagate_binfo_offsets (tree, tree);
152 static void layout_virtual_bases (record_layout_info, splay_tree);
153 static void build_vbase_offset_vtbl_entries (tree, vtbl_init_data *);
154 static void add_vcall_offset_vtbl_entries_r (tree, vtbl_init_data *);
155 static void add_vcall_offset_vtbl_entries_1 (tree, vtbl_init_data *);
156 static void build_vcall_offset_vtbl_entries (tree, vtbl_init_data *);
157 static void add_vcall_offset (tree, tree, vtbl_init_data *);
158 static void layout_vtable_decl (tree, int);
159 static tree dfs_find_final_overrider_pre (tree, void *);
160 static tree dfs_find_final_overrider_post (tree, void *);
161 static tree find_final_overrider (tree, tree, tree);
162 static int make_new_vtable (tree, tree);
163 static int maybe_indent_hierarchy (FILE *, int, int);
164 static tree dump_class_hierarchy_r (FILE *, int, tree, tree, int);
165 static void dump_class_hierarchy (tree);
166 static void dump_class_hierarchy_1 (FILE *, int, tree);
167 static void dump_array (FILE *, tree);
168 static void dump_vtable (tree, tree, tree);
169 static void dump_vtt (tree, tree);
170 static void dump_thunk (FILE *, int, tree);
171 static tree build_vtable (tree, tree, tree);
172 static void initialize_vtable (tree, tree);
173 static void layout_nonempty_base_or_field (record_layout_info,
174                                            tree, tree, splay_tree);
175 static tree end_of_class (tree, int);
176 static bool layout_empty_base (tree, tree, splay_tree);
177 static void accumulate_vtbl_inits (tree, tree, tree, tree, tree);
178 static tree dfs_accumulate_vtbl_inits (tree, tree, tree, tree,
179                                                tree);
180 static void build_rtti_vtbl_entries (tree, vtbl_init_data *);
181 static void build_vcall_and_vbase_vtbl_entries (tree, vtbl_init_data *);
182 static void clone_constructors_and_destructors (tree);
183 static tree build_clone (tree, tree);
184 static void update_vtable_entry_for_fn (tree, tree, tree, tree *, unsigned);
185 static void build_ctor_vtbl_group (tree, tree);
186 static void build_vtt (tree);
187 static tree binfo_ctor_vtable (tree);
188 static tree *build_vtt_inits (tree, tree, tree *, tree *);
189 static tree dfs_build_secondary_vptr_vtt_inits (tree, void *);
190 static tree dfs_fixup_binfo_vtbls (tree, void *);
191 static int record_subobject_offset (tree, tree, splay_tree);
192 static int check_subobject_offset (tree, tree, splay_tree);
193 static int walk_subobject_offsets (tree, subobject_offset_fn,
194                                    tree, splay_tree, tree, int);
195 static void record_subobject_offsets (tree, tree, splay_tree, int);
196 static int layout_conflict_p (tree, tree, splay_tree, int);
197 static int splay_tree_compare_integer_csts (splay_tree_key k1,
198                                             splay_tree_key k2);
199 static void warn_about_ambiguous_bases (tree);
200 static bool type_requires_array_cookie (tree);
201 static bool contains_empty_class_p (tree);
202 static bool base_derived_from (tree, tree);
203 static int empty_base_at_nonzero_offset_p (tree, tree, splay_tree);
204 static tree end_of_base (tree);
205 static tree get_vcall_index (tree, tree);
206
207 /* Variables shared between class.c and call.c.  */
208
209 #ifdef GATHER_STATISTICS
210 int n_vtables = 0;
211 int n_vtable_entries = 0;
212 int n_vtable_searches = 0;
213 int n_vtable_elems = 0;
214 int n_convert_harshness = 0;
215 int n_compute_conversion_costs = 0;
216 int n_inner_fields_searched = 0;
217 #endif
218
219 /* Convert to or from a base subobject.  EXPR is an expression of type
220    `A' or `A*', an expression of type `B' or `B*' is returned.  To
221    convert A to a base B, CODE is PLUS_EXPR and BINFO is the binfo for
222    the B base instance within A.  To convert base A to derived B, CODE
223    is MINUS_EXPR and BINFO is the binfo for the A instance within B.
224    In this latter case, A must not be a morally virtual base of B.
225    NONNULL is true if EXPR is known to be non-NULL (this is only
226    needed when EXPR is of pointer type).  CV qualifiers are preserved
227    from EXPR.  */
228
229 tree
230 build_base_path (enum tree_code code,
231                  tree expr,
232                  tree binfo,
233                  int nonnull)
234 {
235   tree v_binfo = NULL_TREE;
236   tree d_binfo = NULL_TREE;
237   tree probe;
238   tree offset;
239   tree target_type;
240   tree null_test = NULL;
241   tree ptr_target_type;
242   int fixed_type_p;
243   int want_pointer = TREE_CODE (TREE_TYPE (expr)) == POINTER_TYPE;
244   bool has_empty = false;
245   bool virtual_access;
246
247   if (expr == error_mark_node || binfo == error_mark_node || !binfo)
248     return error_mark_node;
249
250   for (probe = binfo; probe; probe = BINFO_INHERITANCE_CHAIN (probe))
251     {
252       d_binfo = probe;
253       if (is_empty_class (BINFO_TYPE (probe)))
254         has_empty = true;
255       if (!v_binfo && BINFO_VIRTUAL_P (probe))
256         v_binfo = probe;
257     }
258
259   probe = TYPE_MAIN_VARIANT (TREE_TYPE (expr));
260   if (want_pointer)
261     probe = TYPE_MAIN_VARIANT (TREE_TYPE (probe));
262
263   gcc_assert ((code == MINUS_EXPR
264                && SAME_BINFO_TYPE_P (BINFO_TYPE (binfo), probe))
265               || (code == PLUS_EXPR
266                   && SAME_BINFO_TYPE_P (BINFO_TYPE (d_binfo), probe)));
267
268   if (binfo == d_binfo)
269     /* Nothing to do.  */
270     return expr;
271
272   if (code == MINUS_EXPR && v_binfo)
273     {
274       error ("cannot convert from base %qT to derived type %qT via virtual base %qT",
275              BINFO_TYPE (binfo), BINFO_TYPE (d_binfo), BINFO_TYPE (v_binfo));
276       return error_mark_node;
277     }
278
279   if (!want_pointer)
280     /* This must happen before the call to save_expr.  */
281     expr = build_unary_op (ADDR_EXPR, expr, 0);
282
283   offset = BINFO_OFFSET (binfo);
284   fixed_type_p = resolves_to_fixed_type_p (expr, &nonnull);
285
286   /* Do we need to look in the vtable for the real offset?  */
287   virtual_access = (v_binfo && fixed_type_p <= 0);
288
289   /* Do we need to check for a null pointer?  */
290   if (want_pointer && !nonnull && (virtual_access || !integer_zerop (offset)))
291     null_test = error_mark_node;
292
293   /* Protect against multiple evaluation if necessary.  */
294   if (TREE_SIDE_EFFECTS (expr) && (null_test || virtual_access))
295     expr = save_expr (expr);
296
297   /* Now that we've saved expr, build the real null test.  */
298   if (null_test)
299     {
300       tree zero = cp_convert (TREE_TYPE (expr), integer_zero_node);
301       null_test = fold_build2 (NE_EXPR, boolean_type_node,
302                                expr, zero);
303     }
304
305   /* If this is a simple base reference, express it as a COMPONENT_REF.  */
306   if (code == PLUS_EXPR && !virtual_access
307       /* We don't build base fields for empty bases, and they aren't very
308          interesting to the optimizers anyway.  */
309       && !has_empty)
310     {
311       expr = build_indirect_ref (expr, NULL);
312       expr = build_simple_base_path (expr, binfo);
313       if (want_pointer)
314         expr = build_address (expr);
315       target_type = TREE_TYPE (expr);
316       goto out;
317     }
318
319   if (virtual_access)
320     {
321       /* Going via virtual base V_BINFO.  We need the static offset
322          from V_BINFO to BINFO, and the dynamic offset from D_BINFO to
323          V_BINFO.  That offset is an entry in D_BINFO's vtable.  */
324       tree v_offset;
325
326       if (fixed_type_p < 0 && in_base_initializer)
327         {
328           /* In a base member initializer, we cannot rely on
329              the vtable being set up. We have to use the vtt_parm.  */
330           tree derived = BINFO_INHERITANCE_CHAIN (v_binfo);
331           tree t;
332
333           t = TREE_TYPE (TYPE_VFIELD (BINFO_TYPE (derived)));
334           t = build_pointer_type (t);
335           v_offset = convert (t, current_vtt_parm);
336           v_offset = build2 (PLUS_EXPR, t, v_offset,
337                              BINFO_VPTR_INDEX (derived));
338           v_offset = build_indirect_ref (v_offset, NULL);
339         }
340       else
341         v_offset = build_vfield_ref (build_indirect_ref (expr, NULL),
342                                      TREE_TYPE (TREE_TYPE (expr)));
343
344       v_offset = build2 (PLUS_EXPR, TREE_TYPE (v_offset),
345                          v_offset,  BINFO_VPTR_FIELD (v_binfo));
346       v_offset = build1 (NOP_EXPR,
347                          build_pointer_type (ptrdiff_type_node),
348                          v_offset);
349       v_offset = build_indirect_ref (v_offset, NULL);
350       TREE_CONSTANT (v_offset) = 1;
351       TREE_INVARIANT (v_offset) = 1;
352
353       offset = convert_to_integer (ptrdiff_type_node,
354                                    size_diffop (offset,
355                                                 BINFO_OFFSET (v_binfo)));
356
357       if (!integer_zerop (offset))
358         v_offset = build2 (code, ptrdiff_type_node, v_offset, offset);
359
360       if (fixed_type_p < 0)
361         /* Negative fixed_type_p means this is a constructor or destructor;
362            virtual base layout is fixed in in-charge [cd]tors, but not in
363            base [cd]tors.  */
364         offset = build3 (COND_EXPR, ptrdiff_type_node,
365                          build2 (EQ_EXPR, boolean_type_node,
366                                  current_in_charge_parm, integer_zero_node),
367                          v_offset,
368                          BINFO_OFFSET (binfo));
369       else
370         offset = v_offset;
371     }
372
373   target_type = code == PLUS_EXPR ? BINFO_TYPE (binfo) : BINFO_TYPE (d_binfo);
374
375   target_type = cp_build_qualified_type
376     (target_type, cp_type_quals (TREE_TYPE (TREE_TYPE (expr))));
377   ptr_target_type = build_pointer_type (target_type);
378   if (want_pointer)
379     target_type = ptr_target_type;
380
381   expr = build1 (NOP_EXPR, ptr_target_type, expr);
382
383   if (!integer_zerop (offset))
384     expr = build2 (code, ptr_target_type, expr, offset);
385   else
386     null_test = NULL;
387
388   if (!want_pointer)
389     expr = build_indirect_ref (expr, NULL);
390
391  out:
392   if (null_test)
393     expr = fold_build3 (COND_EXPR, target_type, null_test, expr,
394                         fold_build1 (NOP_EXPR, target_type,
395                                      integer_zero_node));
396
397   return expr;
398 }
399
400 /* Subroutine of build_base_path; EXPR and BINFO are as in that function.
401    Perform a derived-to-base conversion by recursively building up a
402    sequence of COMPONENT_REFs to the appropriate base fields.  */
403
404 static tree
405 build_simple_base_path (tree expr, tree binfo)
406 {
407   tree type = BINFO_TYPE (binfo);
408   tree d_binfo = BINFO_INHERITANCE_CHAIN (binfo);
409   tree field;
410
411   if (d_binfo == NULL_TREE)
412     {
413       tree temp;
414
415       gcc_assert (TYPE_MAIN_VARIANT (TREE_TYPE (expr)) == type);
416
417       /* Transform `(a, b).x' into `(*(a, &b)).x', `(a ? b : c).x'
418          into `(*(a ?  &b : &c)).x', and so on.  A COND_EXPR is only
419          an lvalue in the frontend; only _DECLs and _REFs are lvalues
420          in the backend.  */
421       temp = unary_complex_lvalue (ADDR_EXPR, expr);
422       if (temp)
423         expr = build_indirect_ref (temp, NULL);
424
425       return expr;
426     }
427
428   /* Recurse.  */
429   expr = build_simple_base_path (expr, d_binfo);
430
431   for (field = TYPE_FIELDS (BINFO_TYPE (d_binfo));
432        field; field = TREE_CHAIN (field))
433     /* Is this the base field created by build_base_field?  */
434     if (TREE_CODE (field) == FIELD_DECL
435         && DECL_FIELD_IS_BASE (field)
436         && TREE_TYPE (field) == type)
437       {
438         /* We don't use build_class_member_access_expr here, as that
439            has unnecessary checks, and more importantly results in
440            recursive calls to dfs_walk_once.  */
441         int type_quals = cp_type_quals (TREE_TYPE (expr));
442
443         expr = build3 (COMPONENT_REF,
444                        cp_build_qualified_type (type, type_quals),
445                        expr, field, NULL_TREE);
446         expr = fold_if_not_in_template (expr);
447
448         /* Mark the expression const or volatile, as appropriate.
449            Even though we've dealt with the type above, we still have
450            to mark the expression itself.  */
451         if (type_quals & TYPE_QUAL_CONST)
452           TREE_READONLY (expr) = 1;
453         if (type_quals & TYPE_QUAL_VOLATILE)
454           TREE_THIS_VOLATILE (expr) = 1;
455
456         return expr;
457       }
458
459   /* Didn't find the base field?!?  */
460   gcc_unreachable ();
461 }
462
463 /* Convert OBJECT to the base TYPE.  OBJECT is an expression whose
464    type is a class type or a pointer to a class type.  In the former
465    case, TYPE is also a class type; in the latter it is another
466    pointer type.  If CHECK_ACCESS is true, an error message is emitted
467    if TYPE is inaccessible.  If OBJECT has pointer type, the value is
468    assumed to be non-NULL.  */
469
470 tree
471 convert_to_base (tree object, tree type, bool check_access, bool nonnull)
472 {
473   tree binfo;
474   tree object_type;
475
476   if (TYPE_PTR_P (TREE_TYPE (object)))
477     {
478       object_type = TREE_TYPE (TREE_TYPE (object));
479       type = TREE_TYPE (type);
480     }
481   else
482     object_type = TREE_TYPE (object);
483
484   binfo = lookup_base (object_type, type,
485                        check_access ? ba_check : ba_unique,
486                        NULL);
487   if (!binfo || binfo == error_mark_node)
488     return error_mark_node;
489
490   return build_base_path (PLUS_EXPR, object, binfo, nonnull);
491 }
492
493 /* EXPR is an expression with unqualified class type.  BASE is a base
494    binfo of that class type.  Returns EXPR, converted to the BASE
495    type.  This function assumes that EXPR is the most derived class;
496    therefore virtual bases can be found at their static offsets.  */
497
498 tree
499 convert_to_base_statically (tree expr, tree base)
500 {
501   tree expr_type;
502
503   expr_type = TREE_TYPE (expr);
504   if (!SAME_BINFO_TYPE_P (BINFO_TYPE (base), expr_type))
505     {
506       tree pointer_type;
507
508       pointer_type = build_pointer_type (expr_type);
509       expr = build_unary_op (ADDR_EXPR, expr, /*noconvert=*/1);
510       if (!integer_zerop (BINFO_OFFSET (base)))
511           expr = build2 (PLUS_EXPR, pointer_type, expr,
512                          build_nop (pointer_type, BINFO_OFFSET (base)));
513       expr = build_nop (build_pointer_type (BINFO_TYPE (base)), expr);
514       expr = build1 (INDIRECT_REF, BINFO_TYPE (base), expr);
515     }
516
517   return expr;
518 }
519
520 \f
521 tree
522 build_vfield_ref (tree datum, tree type)
523 {
524   tree vfield, vcontext;
525
526   if (datum == error_mark_node)
527     return error_mark_node;
528
529   /* First, convert to the requested type.  */
530   if (!same_type_ignoring_top_level_qualifiers_p (TREE_TYPE (datum), type))
531     datum = convert_to_base (datum, type, /*check_access=*/false,
532                              /*nonnull=*/true);
533
534   /* Second, the requested type may not be the owner of its own vptr.
535      If not, convert to the base class that owns it.  We cannot use
536      convert_to_base here, because VCONTEXT may appear more than once
537      in the inheritance hierarchy of TYPE, and thus direct conversion
538      between the types may be ambiguous.  Following the path back up
539      one step at a time via primary bases avoids the problem.  */
540   vfield = TYPE_VFIELD (type);
541   vcontext = DECL_CONTEXT (vfield);
542   while (!same_type_ignoring_top_level_qualifiers_p (vcontext, type))
543     {
544       datum = build_simple_base_path (datum, CLASSTYPE_PRIMARY_BINFO (type));
545       type = TREE_TYPE (datum);
546     }
547
548   return build3 (COMPONENT_REF, TREE_TYPE (vfield), datum, vfield, NULL_TREE);
549 }
550
551 /* Given an object INSTANCE, return an expression which yields the
552    vtable element corresponding to INDEX.  There are many special
553    cases for INSTANCE which we take care of here, mainly to avoid
554    creating extra tree nodes when we don't have to.  */
555
556 static tree
557 build_vtbl_ref_1 (tree instance, tree idx)
558 {
559   tree aref;
560   tree vtbl = NULL_TREE;
561
562   /* Try to figure out what a reference refers to, and
563      access its virtual function table directly.  */
564
565   int cdtorp = 0;
566   tree fixed_type = fixed_type_or_null (instance, NULL, &cdtorp);
567
568   tree basetype = non_reference (TREE_TYPE (instance));
569
570   if (fixed_type && !cdtorp)
571     {
572       tree binfo = lookup_base (fixed_type, basetype,
573                                 ba_unique | ba_quiet, NULL);
574       if (binfo)
575         vtbl = unshare_expr (BINFO_VTABLE (binfo));
576     }
577
578   if (!vtbl)
579     vtbl = build_vfield_ref (instance, basetype);
580
581   assemble_external (vtbl);
582
583   aref = build_array_ref (vtbl, idx);
584   TREE_CONSTANT (aref) |= TREE_CONSTANT (vtbl) && TREE_CONSTANT (idx);
585   TREE_INVARIANT (aref) = TREE_CONSTANT (aref);
586
587   return aref;
588 }
589
590 tree
591 build_vtbl_ref (tree instance, tree idx)
592 {
593   tree aref = build_vtbl_ref_1 (instance, idx);
594
595   return aref;
596 }
597
598 /* Given a stable object pointer INSTANCE_PTR, return an expression which
599    yields a function pointer corresponding to vtable element INDEX.  */
600
601 tree
602 build_vfn_ref (tree instance_ptr, tree idx)
603 {
604   tree aref;
605
606   aref = build_vtbl_ref_1 (build_indirect_ref (instance_ptr, 0), idx);
607
608   /* When using function descriptors, the address of the
609      vtable entry is treated as a function pointer.  */
610   if (TARGET_VTABLE_USES_DESCRIPTORS)
611     aref = build1 (NOP_EXPR, TREE_TYPE (aref),
612                    build_unary_op (ADDR_EXPR, aref, /*noconvert=*/1));
613
614   /* Remember this as a method reference, for later devirtualization.  */
615   aref = build3 (OBJ_TYPE_REF, TREE_TYPE (aref), aref, instance_ptr, idx);
616
617   return aref;
618 }
619
620 /* Return the name of the virtual function table (as an IDENTIFIER_NODE)
621    for the given TYPE.  */
622
623 static tree
624 get_vtable_name (tree type)
625 {
626   return mangle_vtbl_for_type (type);
627 }
628
629 /* Return an IDENTIFIER_NODE for the name of the virtual table table
630    for TYPE.  */
631
632 tree
633 get_vtt_name (tree type)
634 {
635   return mangle_vtt_for_type (type);
636 }
637
638 /* DECL is an entity associated with TYPE, like a virtual table or an
639    implicitly generated constructor.  Determine whether or not DECL
640    should have external or internal linkage at the object file
641    level.  This routine does not deal with COMDAT linkage and other
642    similar complexities; it simply sets TREE_PUBLIC if it possible for
643    entities in other translation units to contain copies of DECL, in
644    the abstract.  */
645
646 void
647 set_linkage_according_to_type (tree type, tree decl)
648 {
649   /* If TYPE involves a local class in a function with internal
650      linkage, then DECL should have internal linkage too.  Other local
651      classes have no linkage -- but if their containing functions
652      have external linkage, it makes sense for DECL to have external
653      linkage too.  That will allow template definitions to be merged,
654      for example.  */
655   if (no_linkage_check (type, /*relaxed_p=*/true))
656     {
657       TREE_PUBLIC (decl) = 0;
658       DECL_INTERFACE_KNOWN (decl) = 1;
659     }
660   else
661     TREE_PUBLIC (decl) = 1;
662 }
663
664 /* Create a VAR_DECL for a primary or secondary vtable for CLASS_TYPE.
665    (For a secondary vtable for B-in-D, CLASS_TYPE should be D, not B.)
666    Use NAME for the name of the vtable, and VTABLE_TYPE for its type.  */
667
668 static tree
669 build_vtable (tree class_type, tree name, tree vtable_type)
670 {
671   tree decl;
672
673   decl = build_lang_decl (VAR_DECL, name, vtable_type);
674   /* vtable names are already mangled; give them their DECL_ASSEMBLER_NAME
675      now to avoid confusion in mangle_decl.  */
676   SET_DECL_ASSEMBLER_NAME (decl, name);
677   DECL_CONTEXT (decl) = class_type;
678   DECL_ARTIFICIAL (decl) = 1;
679   TREE_STATIC (decl) = 1;
680   TREE_READONLY (decl) = 1;
681   DECL_VIRTUAL_P (decl) = 1;
682   DECL_ALIGN (decl) = TARGET_VTABLE_ENTRY_ALIGN;
683   DECL_VTABLE_OR_VTT_P (decl) = 1;
684   /* At one time the vtable info was grabbed 2 words at a time.  This
685      fails on sparc unless you have 8-byte alignment.  (tiemann) */
686   DECL_ALIGN (decl) = MAX (TYPE_ALIGN (double_type_node),
687                            DECL_ALIGN (decl));
688   set_linkage_according_to_type (class_type, decl);
689   /* The vtable has not been defined -- yet.  */
690   DECL_EXTERNAL (decl) = 1;
691   DECL_NOT_REALLY_EXTERN (decl) = 1;
692
693   /* Mark the VAR_DECL node representing the vtable itself as a
694      "gratuitous" one, thereby forcing dwarfout.c to ignore it.  It
695      is rather important that such things be ignored because any
696      effort to actually generate DWARF for them will run into
697      trouble when/if we encounter code like:
698
699      #pragma interface
700      struct S { virtual void member (); };
701
702      because the artificial declaration of the vtable itself (as
703      manufactured by the g++ front end) will say that the vtable is
704      a static member of `S' but only *after* the debug output for
705      the definition of `S' has already been output.  This causes
706      grief because the DWARF entry for the definition of the vtable
707      will try to refer back to an earlier *declaration* of the
708      vtable as a static member of `S' and there won't be one.  We
709      might be able to arrange to have the "vtable static member"
710      attached to the member list for `S' before the debug info for
711      `S' get written (which would solve the problem) but that would
712      require more intrusive changes to the g++ front end.  */
713   DECL_IGNORED_P (decl) = 1;
714
715   return decl;
716 }
717
718 /* Get the VAR_DECL of the vtable for TYPE. TYPE need not be polymorphic,
719    or even complete.  If this does not exist, create it.  If COMPLETE is
720    nonzero, then complete the definition of it -- that will render it
721    impossible to actually build the vtable, but is useful to get at those
722    which are known to exist in the runtime.  */
723
724 tree
725 get_vtable_decl (tree type, int complete)
726 {
727   tree decl;
728
729   if (CLASSTYPE_VTABLES (type))
730     return CLASSTYPE_VTABLES (type);
731
732   decl = build_vtable (type, get_vtable_name (type), vtbl_type_node);
733   CLASSTYPE_VTABLES (type) = decl;
734
735   if (complete)
736     {
737       DECL_EXTERNAL (decl) = 1;
738       cp_finish_decl (decl, NULL_TREE, NULL_TREE, 0);
739     }
740
741   return decl;
742 }
743
744 /* Build the primary virtual function table for TYPE.  If BINFO is
745    non-NULL, build the vtable starting with the initial approximation
746    that it is the same as the one which is the head of the association
747    list.  Returns a nonzero value if a new vtable is actually
748    created.  */
749
750 static int
751 build_primary_vtable (tree binfo, tree type)
752 {
753   tree decl;
754   tree virtuals;
755
756   decl = get_vtable_decl (type, /*complete=*/0);
757
758   if (binfo)
759     {
760       if (BINFO_NEW_VTABLE_MARKED (binfo))
761         /* We have already created a vtable for this base, so there's
762            no need to do it again.  */
763         return 0;
764
765       virtuals = copy_list (BINFO_VIRTUALS (binfo));
766       TREE_TYPE (decl) = TREE_TYPE (get_vtbl_decl_for_binfo (binfo));
767       DECL_SIZE (decl) = TYPE_SIZE (TREE_TYPE (decl));
768       DECL_SIZE_UNIT (decl) = TYPE_SIZE_UNIT (TREE_TYPE (decl));
769     }
770   else
771     {
772       gcc_assert (TREE_TYPE (decl) == vtbl_type_node);
773       virtuals = NULL_TREE;
774     }
775
776 #ifdef GATHER_STATISTICS
777   n_vtables += 1;
778   n_vtable_elems += list_length (virtuals);
779 #endif
780
781   /* Initialize the association list for this type, based
782      on our first approximation.  */
783   BINFO_VTABLE (TYPE_BINFO (type)) = decl;
784   BINFO_VIRTUALS (TYPE_BINFO (type)) = virtuals;
785   SET_BINFO_NEW_VTABLE_MARKED (TYPE_BINFO (type));
786   return 1;
787 }
788
789 /* Give BINFO a new virtual function table which is initialized
790    with a skeleton-copy of its original initialization.  The only
791    entry that changes is the `delta' entry, so we can really
792    share a lot of structure.
793
794    FOR_TYPE is the most derived type which caused this table to
795    be needed.
796
797    Returns nonzero if we haven't met BINFO before.
798
799    The order in which vtables are built (by calling this function) for
800    an object must remain the same, otherwise a binary incompatibility
801    can result.  */
802
803 static int
804 build_secondary_vtable (tree binfo)
805 {
806   if (BINFO_NEW_VTABLE_MARKED (binfo))
807     /* We already created a vtable for this base.  There's no need to
808        do it again.  */
809     return 0;
810
811   /* Remember that we've created a vtable for this BINFO, so that we
812      don't try to do so again.  */
813   SET_BINFO_NEW_VTABLE_MARKED (binfo);
814
815   /* Make fresh virtual list, so we can smash it later.  */
816   BINFO_VIRTUALS (binfo) = copy_list (BINFO_VIRTUALS (binfo));
817
818   /* Secondary vtables are laid out as part of the same structure as
819      the primary vtable.  */
820   BINFO_VTABLE (binfo) = NULL_TREE;
821   return 1;
822 }
823
824 /* Create a new vtable for BINFO which is the hierarchy dominated by
825    T. Return nonzero if we actually created a new vtable.  */
826
827 static int
828 make_new_vtable (tree t, tree binfo)
829 {
830   if (binfo == TYPE_BINFO (t))
831     /* In this case, it is *type*'s vtable we are modifying.  We start
832        with the approximation that its vtable is that of the
833        immediate base class.  */
834     return build_primary_vtable (binfo, t);
835   else
836     /* This is our very own copy of `basetype' to play with.  Later,
837        we will fill in all the virtual functions that override the
838        virtual functions in these base classes which are not defined
839        by the current type.  */
840     return build_secondary_vtable (binfo);
841 }
842
843 /* Make *VIRTUALS, an entry on the BINFO_VIRTUALS list for BINFO
844    (which is in the hierarchy dominated by T) list FNDECL as its
845    BV_FN.  DELTA is the required constant adjustment from the `this'
846    pointer where the vtable entry appears to the `this' required when
847    the function is actually called.  */
848
849 static void
850 modify_vtable_entry (tree t,
851                      tree binfo,
852                      tree fndecl,
853                      tree delta,
854                      tree *virtuals)
855 {
856   tree v;
857
858   v = *virtuals;
859
860   if (fndecl != BV_FN (v)
861       || !tree_int_cst_equal (delta, BV_DELTA (v)))
862     {
863       /* We need a new vtable for BINFO.  */
864       if (make_new_vtable (t, binfo))
865         {
866           /* If we really did make a new vtable, we also made a copy
867              of the BINFO_VIRTUALS list.  Now, we have to find the
868              corresponding entry in that list.  */
869           *virtuals = BINFO_VIRTUALS (binfo);
870           while (BV_FN (*virtuals) != BV_FN (v))
871             *virtuals = TREE_CHAIN (*virtuals);
872           v = *virtuals;
873         }
874
875       BV_DELTA (v) = delta;
876       BV_VCALL_INDEX (v) = NULL_TREE;
877       BV_FN (v) = fndecl;
878     }
879 }
880
881 \f
882 /* Add method METHOD to class TYPE.  If USING_DECL is non-null, it is
883    the USING_DECL naming METHOD.  */
884
885 void
886 add_method (tree type, tree method, tree using_decl)
887 {
888   unsigned slot;
889   tree overload;
890   bool template_conv_p = false;
891   bool conv_p;
892   VEC(tree,gc) *method_vec;
893   bool complete_p;
894   bool insert_p = false;
895   tree current_fns;
896
897   if (method == error_mark_node)
898     return;
899
900   complete_p = COMPLETE_TYPE_P (type);
901   conv_p = DECL_CONV_FN_P (method);
902   if (conv_p)
903     template_conv_p = (TREE_CODE (method) == TEMPLATE_DECL
904                        && DECL_TEMPLATE_CONV_FN_P (method));
905
906   method_vec = CLASSTYPE_METHOD_VEC (type);
907   if (!method_vec)
908     {
909       /* Make a new method vector.  We start with 8 entries.  We must
910          allocate at least two (for constructors and destructors), and
911          we're going to end up with an assignment operator at some
912          point as well.  */
913       method_vec = VEC_alloc (tree, gc, 8);
914       /* Create slots for constructors and destructors.  */
915       VEC_quick_push (tree, method_vec, NULL_TREE);
916       VEC_quick_push (tree, method_vec, NULL_TREE);
917       CLASSTYPE_METHOD_VEC (type) = method_vec;
918     }
919
920   /* Constructors and destructors go in special slots.  */
921   if (DECL_MAYBE_IN_CHARGE_CONSTRUCTOR_P (method))
922     slot = CLASSTYPE_CONSTRUCTOR_SLOT;
923   else if (DECL_MAYBE_IN_CHARGE_DESTRUCTOR_P (method))
924     {
925       slot = CLASSTYPE_DESTRUCTOR_SLOT;
926
927       if (TYPE_FOR_JAVA (type))
928         {
929           if (!DECL_ARTIFICIAL (method))
930             error ("Java class %qT cannot have a destructor", type);
931           else if (TYPE_HAS_NONTRIVIAL_DESTRUCTOR (type))
932             error ("Java class %qT cannot have an implicit non-trivial "
933                    "destructor",
934                    type);
935         }
936     }
937   else
938     {
939       tree m;
940
941       insert_p = true;
942       /* See if we already have an entry with this name.  */
943       for (slot = CLASSTYPE_FIRST_CONVERSION_SLOT;
944            VEC_iterate (tree, method_vec, slot, m);
945            ++slot)
946         {
947           m = OVL_CURRENT (m);
948           if (template_conv_p)
949             {
950               if (TREE_CODE (m) == TEMPLATE_DECL
951                   && DECL_TEMPLATE_CONV_FN_P (m))
952                 insert_p = false;
953               break;
954             }
955           if (conv_p && !DECL_CONV_FN_P (m))
956             break;
957           if (DECL_NAME (m) == DECL_NAME (method))
958             {
959               insert_p = false;
960               break;
961             }
962           if (complete_p
963               && !DECL_CONV_FN_P (m)
964               && DECL_NAME (m) > DECL_NAME (method))
965             break;
966         }
967     }
968   current_fns = insert_p ? NULL_TREE : VEC_index (tree, method_vec, slot);
969
970   if (processing_template_decl)
971     /* TYPE is a template class.  Don't issue any errors now; wait
972        until instantiation time to complain.  */
973     ;
974   else
975     {
976       tree fns;
977
978       /* Check to see if we've already got this method.  */
979       for (fns = current_fns; fns; fns = OVL_NEXT (fns))
980         {
981           tree fn = OVL_CURRENT (fns);
982           tree parms1;
983           tree parms2;
984           bool same = 1;
985
986           if (TREE_CODE (fn) != TREE_CODE (method))
987             continue;
988
989           /* [over.load] Member function declarations with the
990              same name and the same parameter types cannot be
991              overloaded if any of them is a static member
992              function declaration.
993
994              [namespace.udecl] When a using-declaration brings names
995              from a base class into a derived class scope, member
996              functions in the derived class override and/or hide member
997              functions with the same name and parameter types in a base
998              class (rather than conflicting).  */
999           parms1 = TYPE_ARG_TYPES (TREE_TYPE (fn));
1000           parms2 = TYPE_ARG_TYPES (TREE_TYPE (method));
1001
1002           /* Compare the quals on the 'this' parm.  Don't compare
1003              the whole types, as used functions are treated as
1004              coming from the using class in overload resolution.  */
1005           if (! DECL_STATIC_FUNCTION_P (fn)
1006               && ! DECL_STATIC_FUNCTION_P (method)
1007               && (TYPE_QUALS (TREE_TYPE (TREE_VALUE (parms1)))
1008                   != TYPE_QUALS (TREE_TYPE (TREE_VALUE (parms2)))))
1009             same = 0;
1010
1011           /* For templates, the template parms must be identical.  */
1012           if (TREE_CODE (fn) == TEMPLATE_DECL
1013               && !comp_template_parms (DECL_TEMPLATE_PARMS (fn),
1014                                        DECL_TEMPLATE_PARMS (method)))
1015             same = 0;
1016
1017           if (! DECL_STATIC_FUNCTION_P (fn))
1018             parms1 = TREE_CHAIN (parms1);
1019           if (! DECL_STATIC_FUNCTION_P (method))
1020             parms2 = TREE_CHAIN (parms2);
1021
1022           if (same && compparms (parms1, parms2)
1023               && (!DECL_CONV_FN_P (fn)
1024                   || same_type_p (TREE_TYPE (TREE_TYPE (fn)),
1025                                   TREE_TYPE (TREE_TYPE (method)))))
1026             {
1027               if (using_decl)
1028                 {
1029                   if (DECL_CONTEXT (fn) == type)
1030                     /* Defer to the local function.  */
1031                     return;
1032                   if (DECL_CONTEXT (fn) == DECL_CONTEXT (method))
1033                     error ("repeated using declaration %q+D", using_decl);
1034                   else
1035                     error ("using declaration %q+D conflicts with a previous using declaration",
1036                            using_decl);
1037                 }
1038               else
1039                 {
1040                   error ("%q+#D cannot be overloaded", method);
1041                   error ("with %q+#D", fn);
1042                 }
1043
1044               /* We don't call duplicate_decls here to merge the
1045                  declarations because that will confuse things if the
1046                  methods have inline definitions.  In particular, we
1047                  will crash while processing the definitions.  */
1048               return;
1049             }
1050         }
1051     }
1052
1053   /* Add the new binding.  */
1054   overload = build_overload (method, current_fns);
1055
1056   if (!conv_p && slot >= CLASSTYPE_FIRST_CONVERSION_SLOT && !complete_p)
1057     push_class_level_binding (DECL_NAME (method), overload);
1058
1059   if (insert_p)
1060     {
1061       /* We only expect to add few methods in the COMPLETE_P case, so
1062          just make room for one more method in that case.  */
1063       if (VEC_reserve (tree, gc, method_vec, complete_p ? -1 : 1))
1064         CLASSTYPE_METHOD_VEC (type) = method_vec;
1065       if (slot == VEC_length (tree, method_vec))
1066         VEC_quick_push (tree, method_vec, overload);
1067       else
1068         VEC_quick_insert (tree, method_vec, slot, overload);
1069     }
1070   else
1071     /* Replace the current slot.  */
1072     VEC_replace (tree, method_vec, slot, overload);
1073 }
1074
1075 /* Subroutines of finish_struct.  */
1076
1077 /* Change the access of FDECL to ACCESS in T.  Return 1 if change was
1078    legit, otherwise return 0.  */
1079
1080 static int
1081 alter_access (tree t, tree fdecl, tree access)
1082 {
1083   tree elem;
1084
1085   if (!DECL_LANG_SPECIFIC (fdecl))
1086     retrofit_lang_decl (fdecl);
1087
1088   gcc_assert (!DECL_DISCRIMINATOR_P (fdecl));
1089
1090   elem = purpose_member (t, DECL_ACCESS (fdecl));
1091   if (elem)
1092     {
1093       if (TREE_VALUE (elem) != access)
1094         {
1095           if (TREE_CODE (TREE_TYPE (fdecl)) == FUNCTION_DECL)
1096             error ("conflicting access specifications for method"
1097                    " %q+D, ignored", TREE_TYPE (fdecl));
1098           else
1099             error ("conflicting access specifications for field %qE, ignored",
1100                    DECL_NAME (fdecl));
1101         }
1102       else
1103         {
1104           /* They're changing the access to the same thing they changed
1105              it to before.  That's OK.  */
1106           ;
1107         }
1108     }
1109   else
1110     {
1111       perform_or_defer_access_check (TYPE_BINFO (t), fdecl);
1112       DECL_ACCESS (fdecl) = tree_cons (t, access, DECL_ACCESS (fdecl));
1113       return 1;
1114     }
1115   return 0;
1116 }
1117
1118 /* Process the USING_DECL, which is a member of T.  */
1119
1120 static void
1121 handle_using_decl (tree using_decl, tree t)
1122 {
1123   tree decl = USING_DECL_DECLS (using_decl);
1124   tree name = DECL_NAME (using_decl);
1125   tree access
1126     = TREE_PRIVATE (using_decl) ? access_private_node
1127     : TREE_PROTECTED (using_decl) ? access_protected_node
1128     : access_public_node;
1129   tree flist = NULL_TREE;
1130   tree old_value;
1131
1132   gcc_assert (!processing_template_decl && decl);
1133
1134   old_value = lookup_member (t, name, /*protect=*/0, /*want_type=*/false);
1135   if (old_value)
1136     {
1137       if (is_overloaded_fn (old_value))
1138         old_value = OVL_CURRENT (old_value);
1139
1140       if (DECL_P (old_value) && DECL_CONTEXT (old_value) == t)
1141         /* OK */;
1142       else
1143         old_value = NULL_TREE;
1144     }
1145
1146   cp_emit_debug_info_for_using (decl, current_class_type);
1147
1148   if (is_overloaded_fn (decl))
1149     flist = decl;
1150
1151   if (! old_value)
1152     ;
1153   else if (is_overloaded_fn (old_value))
1154     {
1155       if (flist)
1156         /* It's OK to use functions from a base when there are functions with
1157            the same name already present in the current class.  */;
1158       else
1159         {
1160           error ("%q+D invalid in %q#T", using_decl, t);
1161           error ("  because of local method %q+#D with same name",
1162                  OVL_CURRENT (old_value));
1163           return;
1164         }
1165     }
1166   else if (!DECL_ARTIFICIAL (old_value))
1167     {
1168       error ("%q+D invalid in %q#T", using_decl, t);
1169       error ("  because of local member %q+#D with same name", old_value);
1170       return;
1171     }
1172
1173   /* Make type T see field decl FDECL with access ACCESS.  */
1174   if (flist)
1175     for (; flist; flist = OVL_NEXT (flist))
1176       {
1177         add_method (t, OVL_CURRENT (flist), using_decl);
1178         alter_access (t, OVL_CURRENT (flist), access);
1179       }
1180   else
1181     alter_access (t, decl, access);
1182 }
1183 \f
1184 /* Run through the base classes of T, updating CANT_HAVE_CONST_CTOR_P,
1185    and NO_CONST_ASN_REF_P.  Also set flag bits in T based on
1186    properties of the bases.  */
1187
1188 static void
1189 check_bases (tree t,
1190              int* cant_have_const_ctor_p,
1191              int* no_const_asn_ref_p)
1192 {
1193   int i;
1194   int seen_non_virtual_nearly_empty_base_p;
1195   tree base_binfo;
1196   tree binfo;
1197
1198   seen_non_virtual_nearly_empty_base_p = 0;
1199
1200   for (binfo = TYPE_BINFO (t), i = 0;
1201        BINFO_BASE_ITERATE (binfo, i, base_binfo); i++)
1202     {
1203       tree basetype = TREE_TYPE (base_binfo);
1204
1205       gcc_assert (COMPLETE_TYPE_P (basetype));
1206
1207       /* Effective C++ rule 14.  We only need to check TYPE_POLYMORPHIC_P
1208          here because the case of virtual functions but non-virtual
1209          dtor is handled in finish_struct_1.  */
1210       if (warn_ecpp && ! TYPE_POLYMORPHIC_P (basetype))
1211         warning (0, "base class %q#T has a non-virtual destructor", basetype);
1212
1213       /* If the base class doesn't have copy constructors or
1214          assignment operators that take const references, then the
1215          derived class cannot have such a member automatically
1216          generated.  */
1217       if (! TYPE_HAS_CONST_INIT_REF (basetype))
1218         *cant_have_const_ctor_p = 1;
1219       if (TYPE_HAS_ASSIGN_REF (basetype)
1220           && !TYPE_HAS_CONST_ASSIGN_REF (basetype))
1221         *no_const_asn_ref_p = 1;
1222
1223       if (BINFO_VIRTUAL_P (base_binfo))
1224         /* A virtual base does not effect nearly emptiness.  */
1225         ;
1226       else if (CLASSTYPE_NEARLY_EMPTY_P (basetype))
1227         {
1228           if (seen_non_virtual_nearly_empty_base_p)
1229             /* And if there is more than one nearly empty base, then the
1230                derived class is not nearly empty either.  */
1231             CLASSTYPE_NEARLY_EMPTY_P (t) = 0;
1232           else
1233             /* Remember we've seen one.  */
1234             seen_non_virtual_nearly_empty_base_p = 1;
1235         }
1236       else if (!is_empty_class (basetype))
1237         /* If the base class is not empty or nearly empty, then this
1238            class cannot be nearly empty.  */
1239         CLASSTYPE_NEARLY_EMPTY_P (t) = 0;
1240
1241       /* A lot of properties from the bases also apply to the derived
1242          class.  */
1243       TYPE_NEEDS_CONSTRUCTING (t) |= TYPE_NEEDS_CONSTRUCTING (basetype);
1244       TYPE_HAS_NONTRIVIAL_DESTRUCTOR (t)
1245         |= TYPE_HAS_NONTRIVIAL_DESTRUCTOR (basetype);
1246       TYPE_HAS_COMPLEX_ASSIGN_REF (t)
1247         |= TYPE_HAS_COMPLEX_ASSIGN_REF (basetype);
1248       TYPE_HAS_COMPLEX_INIT_REF (t) |= TYPE_HAS_COMPLEX_INIT_REF (basetype);
1249       TYPE_POLYMORPHIC_P (t) |= TYPE_POLYMORPHIC_P (basetype);
1250       CLASSTYPE_CONTAINS_EMPTY_CLASS_P (t)
1251         |= CLASSTYPE_CONTAINS_EMPTY_CLASS_P (basetype);
1252     }
1253 }
1254
1255 /* Determine all the primary bases within T.  Sets BINFO_PRIMARY_BASE_P for
1256    those that are primaries.  Sets BINFO_LOST_PRIMARY_P for those
1257    that have had a nearly-empty virtual primary base stolen by some
1258    other base in the hierarchy.  Determines CLASSTYPE_PRIMARY_BASE for
1259    T.  */
1260
1261 static void
1262 determine_primary_bases (tree t)
1263 {
1264   unsigned i;
1265   tree primary = NULL_TREE;
1266   tree type_binfo = TYPE_BINFO (t);
1267   tree base_binfo;
1268
1269   /* Determine the primary bases of our bases.  */
1270   for (base_binfo = TREE_CHAIN (type_binfo); base_binfo;
1271        base_binfo = TREE_CHAIN (base_binfo))
1272     {
1273       tree primary = CLASSTYPE_PRIMARY_BINFO (BINFO_TYPE (base_binfo));
1274
1275       /* See if we're the non-virtual primary of our inheritance
1276          chain.  */
1277       if (!BINFO_VIRTUAL_P (base_binfo))
1278         {
1279           tree parent = BINFO_INHERITANCE_CHAIN (base_binfo);
1280           tree parent_primary = CLASSTYPE_PRIMARY_BINFO (BINFO_TYPE (parent));
1281
1282           if (parent_primary
1283               && SAME_BINFO_TYPE_P (BINFO_TYPE (base_binfo),
1284                                     BINFO_TYPE (parent_primary)))
1285             /* We are the primary binfo.  */
1286             BINFO_PRIMARY_P (base_binfo) = 1;
1287         }
1288       /* Determine if we have a virtual primary base, and mark it so.
1289        */
1290       if (primary && BINFO_VIRTUAL_P (primary))
1291         {
1292           tree this_primary = copied_binfo (primary, base_binfo);
1293
1294           if (BINFO_PRIMARY_P (this_primary))
1295             /* Someone already claimed this base.  */
1296             BINFO_LOST_PRIMARY_P (base_binfo) = 1;
1297           else
1298             {
1299               tree delta;
1300
1301               BINFO_PRIMARY_P (this_primary) = 1;
1302               BINFO_INHERITANCE_CHAIN (this_primary) = base_binfo;
1303
1304               /* A virtual binfo might have been copied from within
1305                  another hierarchy. As we're about to use it as a
1306                  primary base, make sure the offsets match.  */
1307               delta = size_diffop (convert (ssizetype,
1308                                             BINFO_OFFSET (base_binfo)),
1309                                    convert (ssizetype,
1310                                             BINFO_OFFSET (this_primary)));
1311
1312               propagate_binfo_offsets (this_primary, delta);
1313             }
1314         }
1315     }
1316
1317   /* First look for a dynamic direct non-virtual base.  */
1318   for (i = 0; BINFO_BASE_ITERATE (type_binfo, i, base_binfo); i++)
1319     {
1320       tree basetype = BINFO_TYPE (base_binfo);
1321
1322       if (TYPE_CONTAINS_VPTR_P (basetype) && !BINFO_VIRTUAL_P (base_binfo))
1323         {
1324           primary = base_binfo;
1325           goto found;
1326         }
1327     }
1328
1329   /* A "nearly-empty" virtual base class can be the primary base
1330      class, if no non-virtual polymorphic base can be found.  Look for
1331      a nearly-empty virtual dynamic base that is not already a primary
1332      base of something in the hierarchy.  If there is no such base,
1333      just pick the first nearly-empty virtual base.  */
1334
1335   for (base_binfo = TREE_CHAIN (type_binfo); base_binfo;
1336        base_binfo = TREE_CHAIN (base_binfo))
1337     if (BINFO_VIRTUAL_P (base_binfo)
1338         && CLASSTYPE_NEARLY_EMPTY_P (BINFO_TYPE (base_binfo)))
1339       {
1340         if (!BINFO_PRIMARY_P (base_binfo))
1341           {
1342             /* Found one that is not primary.  */
1343             primary = base_binfo;
1344             goto found;
1345           }
1346         else if (!primary)
1347           /* Remember the first candidate.  */
1348           primary = base_binfo;
1349       }
1350
1351  found:
1352   /* If we've got a primary base, use it.  */
1353   if (primary)
1354     {
1355       tree basetype = BINFO_TYPE (primary);
1356
1357       CLASSTYPE_PRIMARY_BINFO (t) = primary;
1358       if (BINFO_PRIMARY_P (primary))
1359         /* We are stealing a primary base.  */
1360         BINFO_LOST_PRIMARY_P (BINFO_INHERITANCE_CHAIN (primary)) = 1;
1361       BINFO_PRIMARY_P (primary) = 1;
1362       if (BINFO_VIRTUAL_P (primary))
1363         {
1364           tree delta;
1365
1366           BINFO_INHERITANCE_CHAIN (primary) = type_binfo;
1367           /* A virtual binfo might have been copied from within
1368              another hierarchy. As we're about to use it as a primary
1369              base, make sure the offsets match.  */
1370           delta = size_diffop (ssize_int (0),
1371                                convert (ssizetype, BINFO_OFFSET (primary)));
1372
1373           propagate_binfo_offsets (primary, delta);
1374         }
1375
1376       primary = TYPE_BINFO (basetype);
1377
1378       TYPE_VFIELD (t) = TYPE_VFIELD (basetype);
1379       BINFO_VTABLE (type_binfo) = BINFO_VTABLE (primary);
1380       BINFO_VIRTUALS (type_binfo) = BINFO_VIRTUALS (primary);
1381     }
1382 }
1383 \f
1384 /* Set memoizing fields and bits of T (and its variants) for later
1385    use.  */
1386
1387 static void
1388 finish_struct_bits (tree t)
1389 {
1390   tree variants;
1391
1392   /* Fix up variants (if any).  */
1393   for (variants = TYPE_NEXT_VARIANT (t);
1394        variants;
1395        variants = TYPE_NEXT_VARIANT (variants))
1396     {
1397       /* These fields are in the _TYPE part of the node, not in
1398          the TYPE_LANG_SPECIFIC component, so they are not shared.  */
1399       TYPE_HAS_CONSTRUCTOR (variants) = TYPE_HAS_CONSTRUCTOR (t);
1400       TYPE_NEEDS_CONSTRUCTING (variants) = TYPE_NEEDS_CONSTRUCTING (t);
1401       TYPE_HAS_NONTRIVIAL_DESTRUCTOR (variants)
1402         = TYPE_HAS_NONTRIVIAL_DESTRUCTOR (t);
1403
1404       TYPE_POLYMORPHIC_P (variants) = TYPE_POLYMORPHIC_P (t);
1405
1406       TYPE_BINFO (variants) = TYPE_BINFO (t);
1407
1408       /* Copy whatever these are holding today.  */
1409       TYPE_VFIELD (variants) = TYPE_VFIELD (t);
1410       TYPE_METHODS (variants) = TYPE_METHODS (t);
1411       TYPE_FIELDS (variants) = TYPE_FIELDS (t);
1412       TYPE_SIZE (variants) = TYPE_SIZE (t);
1413       TYPE_SIZE_UNIT (variants) = TYPE_SIZE_UNIT (t);
1414     }
1415
1416   if (BINFO_N_BASE_BINFOS (TYPE_BINFO (t)) && TYPE_POLYMORPHIC_P (t))
1417     /* For a class w/o baseclasses, 'finish_struct' has set
1418        CLASSTYPE_PURE_VIRTUALS correctly (by definition).
1419        Similarly for a class whose base classes do not have vtables.
1420        When neither of these is true, we might have removed abstract
1421        virtuals (by providing a definition), added some (by declaring
1422        new ones), or redeclared ones from a base class.  We need to
1423        recalculate what's really an abstract virtual at this point (by
1424        looking in the vtables).  */
1425     get_pure_virtuals (t);
1426
1427   /* If this type has a copy constructor or a destructor, force its
1428      mode to be BLKmode, and force its TREE_ADDRESSABLE bit to be
1429      nonzero.  This will cause it to be passed by invisible reference
1430      and prevent it from being returned in a register.  */
1431   if (! TYPE_HAS_TRIVIAL_INIT_REF (t) || TYPE_HAS_NONTRIVIAL_DESTRUCTOR (t))
1432     {
1433       tree variants;
1434       DECL_MODE (TYPE_MAIN_DECL (t)) = BLKmode;
1435       for (variants = t; variants; variants = TYPE_NEXT_VARIANT (variants))
1436         {
1437           TYPE_MODE (variants) = BLKmode;
1438           TREE_ADDRESSABLE (variants) = 1;
1439         }
1440     }
1441 }
1442
1443 /* Issue warnings about T having private constructors, but no friends,
1444    and so forth.
1445
1446    HAS_NONPRIVATE_METHOD is nonzero if T has any non-private methods or
1447    static members.  HAS_NONPRIVATE_STATIC_FN is nonzero if T has any
1448    non-private static member functions.  */
1449
1450 static void
1451 maybe_warn_about_overly_private_class (tree t)
1452 {
1453   int has_member_fn = 0;
1454   int has_nonprivate_method = 0;
1455   tree fn;
1456
1457   if (!warn_ctor_dtor_privacy
1458       /* If the class has friends, those entities might create and
1459          access instances, so we should not warn.  */
1460       || (CLASSTYPE_FRIEND_CLASSES (t)
1461           || DECL_FRIENDLIST (TYPE_MAIN_DECL (t)))
1462       /* We will have warned when the template was declared; there's
1463          no need to warn on every instantiation.  */
1464       || CLASSTYPE_TEMPLATE_INSTANTIATION (t))
1465     /* There's no reason to even consider warning about this
1466        class.  */
1467     return;
1468
1469   /* We only issue one warning, if more than one applies, because
1470      otherwise, on code like:
1471
1472      class A {
1473        // Oops - forgot `public:'
1474        A();
1475        A(const A&);
1476        ~A();
1477      };
1478
1479      we warn several times about essentially the same problem.  */
1480
1481   /* Check to see if all (non-constructor, non-destructor) member
1482      functions are private.  (Since there are no friends or
1483      non-private statics, we can't ever call any of the private member
1484      functions.)  */
1485   for (fn = TYPE_METHODS (t); fn; fn = TREE_CHAIN (fn))
1486     /* We're not interested in compiler-generated methods; they don't
1487        provide any way to call private members.  */
1488     if (!DECL_ARTIFICIAL (fn))
1489       {
1490         if (!TREE_PRIVATE (fn))
1491           {
1492             if (DECL_STATIC_FUNCTION_P (fn))
1493               /* A non-private static member function is just like a
1494                  friend; it can create and invoke private member
1495                  functions, and be accessed without a class
1496                  instance.  */
1497               return;
1498
1499             has_nonprivate_method = 1;
1500             /* Keep searching for a static member function.  */
1501           }
1502         else if (!DECL_CONSTRUCTOR_P (fn) && !DECL_DESTRUCTOR_P (fn))
1503           has_member_fn = 1;
1504       }
1505
1506   if (!has_nonprivate_method && has_member_fn)
1507     {
1508       /* There are no non-private methods, and there's at least one
1509          private member function that isn't a constructor or
1510          destructor.  (If all the private members are
1511          constructors/destructors we want to use the code below that
1512          issues error messages specifically referring to
1513          constructors/destructors.)  */
1514       unsigned i;
1515       tree binfo = TYPE_BINFO (t);
1516
1517       for (i = 0; i != BINFO_N_BASE_BINFOS (binfo); i++)
1518         if (BINFO_BASE_ACCESS (binfo, i) != access_private_node)
1519           {
1520             has_nonprivate_method = 1;
1521             break;
1522           }
1523       if (!has_nonprivate_method)
1524         {
1525           warning (0, "all member functions in class %qT are private", t);
1526           return;
1527         }
1528     }
1529
1530   /* Even if some of the member functions are non-private, the class
1531      won't be useful for much if all the constructors or destructors
1532      are private: such an object can never be created or destroyed.  */
1533   fn = CLASSTYPE_DESTRUCTORS (t);
1534   if (fn && TREE_PRIVATE (fn))
1535     {
1536       warning (0, "%q#T only defines a private destructor and has no friends",
1537                t);
1538       return;
1539     }
1540
1541   if (TYPE_HAS_CONSTRUCTOR (t))
1542     {
1543       int nonprivate_ctor = 0;
1544
1545       /* If a non-template class does not define a copy
1546          constructor, one is defined for it, enabling it to avoid
1547          this warning.  For a template class, this does not
1548          happen, and so we would normally get a warning on:
1549
1550            template <class T> class C { private: C(); };
1551
1552          To avoid this asymmetry, we check TYPE_HAS_INIT_REF.  All
1553          complete non-template or fully instantiated classes have this
1554          flag set.  */
1555       if (!TYPE_HAS_INIT_REF (t))
1556         nonprivate_ctor = 1;
1557       else
1558         for (fn = CLASSTYPE_CONSTRUCTORS (t); fn; fn = OVL_NEXT (fn))
1559           {
1560             tree ctor = OVL_CURRENT (fn);
1561             /* Ideally, we wouldn't count copy constructors (or, in
1562                fact, any constructor that takes an argument of the
1563                class type as a parameter) because such things cannot
1564                be used to construct an instance of the class unless
1565                you already have one.  But, for now at least, we're
1566                more generous.  */
1567             if (! TREE_PRIVATE (ctor))
1568               {
1569                 nonprivate_ctor = 1;
1570                 break;
1571               }
1572           }
1573
1574       if (nonprivate_ctor == 0)
1575         {
1576           warning (0, "%q#T only defines private constructors and has no friends",
1577                    t);
1578           return;
1579         }
1580     }
1581 }
1582
1583 static struct {
1584   gt_pointer_operator new_value;
1585   void *cookie;
1586 } resort_data;
1587
1588 /* Comparison function to compare two TYPE_METHOD_VEC entries by name.  */
1589
1590 static int
1591 method_name_cmp (const void* m1_p, const void* m2_p)
1592 {
1593   const tree *const m1 = m1_p;
1594   const tree *const m2 = m2_p;
1595
1596   if (*m1 == NULL_TREE && *m2 == NULL_TREE)
1597     return 0;
1598   if (*m1 == NULL_TREE)
1599     return -1;
1600   if (*m2 == NULL_TREE)
1601     return 1;
1602   if (DECL_NAME (OVL_CURRENT (*m1)) < DECL_NAME (OVL_CURRENT (*m2)))
1603     return -1;
1604   return 1;
1605 }
1606
1607 /* This routine compares two fields like method_name_cmp but using the
1608    pointer operator in resort_field_decl_data.  */
1609
1610 static int
1611 resort_method_name_cmp (const void* m1_p, const void* m2_p)
1612 {
1613   const tree *const m1 = m1_p;
1614   const tree *const m2 = m2_p;
1615   if (*m1 == NULL_TREE && *m2 == NULL_TREE)
1616     return 0;
1617   if (*m1 == NULL_TREE)
1618     return -1;
1619   if (*m2 == NULL_TREE)
1620     return 1;
1621   {
1622     tree d1 = DECL_NAME (OVL_CURRENT (*m1));
1623     tree d2 = DECL_NAME (OVL_CURRENT (*m2));
1624     resort_data.new_value (&d1, resort_data.cookie);
1625     resort_data.new_value (&d2, resort_data.cookie);
1626     if (d1 < d2)
1627       return -1;
1628   }
1629   return 1;
1630 }
1631
1632 /* Resort TYPE_METHOD_VEC because pointers have been reordered.  */
1633
1634 void
1635 resort_type_method_vec (void* obj,
1636                         void* orig_obj ATTRIBUTE_UNUSED ,
1637                         gt_pointer_operator new_value,
1638                         void* cookie)
1639 {
1640   VEC(tree,gc) *method_vec = (VEC(tree,gc) *) obj;
1641   int len = VEC_length (tree, method_vec);
1642   size_t slot;
1643   tree fn;
1644
1645   /* The type conversion ops have to live at the front of the vec, so we
1646      can't sort them.  */
1647   for (slot = CLASSTYPE_FIRST_CONVERSION_SLOT;
1648        VEC_iterate (tree, method_vec, slot, fn);
1649        ++slot)
1650     if (!DECL_CONV_FN_P (OVL_CURRENT (fn)))
1651       break;
1652
1653   if (len - slot > 1)
1654     {
1655       resort_data.new_value = new_value;
1656       resort_data.cookie = cookie;
1657       qsort (VEC_address (tree, method_vec) + slot, len - slot, sizeof (tree),
1658              resort_method_name_cmp);
1659     }
1660 }
1661
1662 /* Warn about duplicate methods in fn_fields.
1663
1664    Sort methods that are not special (i.e., constructors, destructors,
1665    and type conversion operators) so that we can find them faster in
1666    search.  */
1667
1668 static void
1669 finish_struct_methods (tree t)
1670 {
1671   tree fn_fields;
1672   VEC(tree,gc) *method_vec;
1673   int slot, len;
1674
1675   method_vec = CLASSTYPE_METHOD_VEC (t);
1676   if (!method_vec)
1677     return;
1678
1679   len = VEC_length (tree, method_vec);
1680
1681   /* Clear DECL_IN_AGGR_P for all functions.  */
1682   for (fn_fields = TYPE_METHODS (t); fn_fields;
1683        fn_fields = TREE_CHAIN (fn_fields))
1684     DECL_IN_AGGR_P (fn_fields) = 0;
1685
1686   /* Issue warnings about private constructors and such.  If there are
1687      no methods, then some public defaults are generated.  */
1688   maybe_warn_about_overly_private_class (t);
1689
1690   /* The type conversion ops have to live at the front of the vec, so we
1691      can't sort them.  */
1692   for (slot = CLASSTYPE_FIRST_CONVERSION_SLOT;
1693        VEC_iterate (tree, method_vec, slot, fn_fields);
1694        ++slot)
1695     if (!DECL_CONV_FN_P (OVL_CURRENT (fn_fields)))
1696       break;
1697   if (len - slot > 1)
1698     qsort (VEC_address (tree, method_vec) + slot,
1699            len-slot, sizeof (tree), method_name_cmp);
1700 }
1701
1702 /* Make BINFO's vtable have N entries, including RTTI entries,
1703    vbase and vcall offsets, etc.  Set its type and call the backend
1704    to lay it out.  */
1705
1706 static void
1707 layout_vtable_decl (tree binfo, int n)
1708 {
1709   tree atype;
1710   tree vtable;
1711
1712   atype = build_cplus_array_type (vtable_entry_type,
1713                                   build_index_type (size_int (n - 1)));
1714   layout_type (atype);
1715
1716   /* We may have to grow the vtable.  */
1717   vtable = get_vtbl_decl_for_binfo (binfo);
1718   if (!same_type_p (TREE_TYPE (vtable), atype))
1719     {
1720       TREE_TYPE (vtable) = atype;
1721       DECL_SIZE (vtable) = DECL_SIZE_UNIT (vtable) = NULL_TREE;
1722       layout_decl (vtable, 0);
1723     }
1724 }
1725
1726 /* True iff FNDECL and BASE_FNDECL (both non-static member functions)
1727    have the same signature.  */
1728
1729 int
1730 same_signature_p (tree fndecl, tree base_fndecl)
1731 {
1732   /* One destructor overrides another if they are the same kind of
1733      destructor.  */
1734   if (DECL_DESTRUCTOR_P (base_fndecl) && DECL_DESTRUCTOR_P (fndecl)
1735       && special_function_p (base_fndecl) == special_function_p (fndecl))
1736     return 1;
1737   /* But a non-destructor never overrides a destructor, nor vice
1738      versa, nor do different kinds of destructors override
1739      one-another.  For example, a complete object destructor does not
1740      override a deleting destructor.  */
1741   if (DECL_DESTRUCTOR_P (base_fndecl) || DECL_DESTRUCTOR_P (fndecl))
1742     return 0;
1743
1744   if (DECL_NAME (fndecl) == DECL_NAME (base_fndecl)
1745       || (DECL_CONV_FN_P (fndecl)
1746           && DECL_CONV_FN_P (base_fndecl)
1747           && same_type_p (DECL_CONV_FN_TYPE (fndecl),
1748                           DECL_CONV_FN_TYPE (base_fndecl))))
1749     {
1750       tree types, base_types;
1751       types = TYPE_ARG_TYPES (TREE_TYPE (fndecl));
1752       base_types = TYPE_ARG_TYPES (TREE_TYPE (base_fndecl));
1753       if ((TYPE_QUALS (TREE_TYPE (TREE_VALUE (base_types)))
1754            == TYPE_QUALS (TREE_TYPE (TREE_VALUE (types))))
1755           && compparms (TREE_CHAIN (base_types), TREE_CHAIN (types)))
1756         return 1;
1757     }
1758   return 0;
1759 }
1760
1761 /* Returns TRUE if DERIVED is a binfo containing the binfo BASE as a
1762    subobject.  */
1763
1764 static bool
1765 base_derived_from (tree derived, tree base)
1766 {
1767   tree probe;
1768
1769   for (probe = base; probe; probe = BINFO_INHERITANCE_CHAIN (probe))
1770     {
1771       if (probe == derived)
1772         return true;
1773       else if (BINFO_VIRTUAL_P (probe))
1774         /* If we meet a virtual base, we can't follow the inheritance
1775            any more.  See if the complete type of DERIVED contains
1776            such a virtual base.  */
1777         return (binfo_for_vbase (BINFO_TYPE (probe), BINFO_TYPE (derived))
1778                 != NULL_TREE);
1779     }
1780   return false;
1781 }
1782
1783 typedef struct find_final_overrider_data_s {
1784   /* The function for which we are trying to find a final overrider.  */
1785   tree fn;
1786   /* The base class in which the function was declared.  */
1787   tree declaring_base;
1788   /* The candidate overriders.  */
1789   tree candidates;
1790   /* Path to most derived.  */
1791   VEC(tree,heap) *path;
1792 } find_final_overrider_data;
1793
1794 /* Add the overrider along the current path to FFOD->CANDIDATES.
1795    Returns true if an overrider was found; false otherwise.  */
1796
1797 static bool
1798 dfs_find_final_overrider_1 (tree binfo,
1799                             find_final_overrider_data *ffod,
1800                             unsigned depth)
1801 {
1802   tree method;
1803
1804   /* If BINFO is not the most derived type, try a more derived class.
1805      A definition there will overrider a definition here.  */
1806   if (depth)
1807     {
1808       depth--;
1809       if (dfs_find_final_overrider_1
1810           (VEC_index (tree, ffod->path, depth), ffod, depth))
1811         return true;
1812     }
1813
1814   method = look_for_overrides_here (BINFO_TYPE (binfo), ffod->fn);
1815   if (method)
1816     {
1817       tree *candidate = &ffod->candidates;
1818
1819       /* Remove any candidates overridden by this new function.  */
1820       while (*candidate)
1821         {
1822           /* If *CANDIDATE overrides METHOD, then METHOD
1823              cannot override anything else on the list.  */
1824           if (base_derived_from (TREE_VALUE (*candidate), binfo))
1825             return true;
1826           /* If METHOD overrides *CANDIDATE, remove *CANDIDATE.  */
1827           if (base_derived_from (binfo, TREE_VALUE (*candidate)))
1828             *candidate = TREE_CHAIN (*candidate);
1829           else
1830             candidate = &TREE_CHAIN (*candidate);
1831         }
1832
1833       /* Add the new function.  */
1834       ffod->candidates = tree_cons (method, binfo, ffod->candidates);
1835       return true;
1836     }
1837
1838   return false;
1839 }
1840
1841 /* Called from find_final_overrider via dfs_walk.  */
1842
1843 static tree
1844 dfs_find_final_overrider_pre (tree binfo, void *data)
1845 {
1846   find_final_overrider_data *ffod = (find_final_overrider_data *) data;
1847
1848   if (binfo == ffod->declaring_base)
1849     dfs_find_final_overrider_1 (binfo, ffod, VEC_length (tree, ffod->path));
1850   VEC_safe_push (tree, heap, ffod->path, binfo);
1851
1852   return NULL_TREE;
1853 }
1854
1855 static tree
1856 dfs_find_final_overrider_post (tree binfo ATTRIBUTE_UNUSED, void *data)
1857 {
1858   find_final_overrider_data *ffod = (find_final_overrider_data *) data;
1859   VEC_pop (tree, ffod->path);
1860
1861   return NULL_TREE;
1862 }
1863
1864 /* Returns a TREE_LIST whose TREE_PURPOSE is the final overrider for
1865    FN and whose TREE_VALUE is the binfo for the base where the
1866    overriding occurs.  BINFO (in the hierarchy dominated by the binfo
1867    DERIVED) is the base object in which FN is declared.  */
1868
1869 static tree
1870 find_final_overrider (tree derived, tree binfo, tree fn)
1871 {
1872   find_final_overrider_data ffod;
1873
1874   /* Getting this right is a little tricky.  This is valid:
1875
1876        struct S { virtual void f (); };
1877        struct T { virtual void f (); };
1878        struct U : public S, public T { };
1879
1880      even though calling `f' in `U' is ambiguous.  But,
1881
1882        struct R { virtual void f(); };
1883        struct S : virtual public R { virtual void f (); };
1884        struct T : virtual public R { virtual void f (); };
1885        struct U : public S, public T { };
1886
1887      is not -- there's no way to decide whether to put `S::f' or
1888      `T::f' in the vtable for `R'.
1889
1890      The solution is to look at all paths to BINFO.  If we find
1891      different overriders along any two, then there is a problem.  */
1892   if (DECL_THUNK_P (fn))
1893     fn = THUNK_TARGET (fn);
1894
1895   /* Determine the depth of the hierarchy.  */
1896   ffod.fn = fn;
1897   ffod.declaring_base = binfo;
1898   ffod.candidates = NULL_TREE;
1899   ffod.path = VEC_alloc (tree, heap, 30);
1900
1901   dfs_walk_all (derived, dfs_find_final_overrider_pre,
1902                 dfs_find_final_overrider_post, &ffod);
1903
1904   VEC_free (tree, heap, ffod.path);
1905
1906   /* If there was no winner, issue an error message.  */
1907   if (!ffod.candidates || TREE_CHAIN (ffod.candidates))
1908     {
1909       error ("no unique final overrider for %qD in %qT", fn,
1910              BINFO_TYPE (derived));
1911       return error_mark_node;
1912     }
1913
1914   return ffod.candidates;
1915 }
1916
1917 /* Return the index of the vcall offset for FN when TYPE is used as a
1918    virtual base.  */
1919
1920 static tree
1921 get_vcall_index (tree fn, tree type)
1922 {
1923   VEC(tree_pair_s,gc) *indices = CLASSTYPE_VCALL_INDICES (type);
1924   tree_pair_p p;
1925   unsigned ix;
1926
1927   for (ix = 0; VEC_iterate (tree_pair_s, indices, ix, p); ix++)
1928     if ((DECL_DESTRUCTOR_P (fn) && DECL_DESTRUCTOR_P (p->purpose))
1929         || same_signature_p (fn, p->purpose))
1930       return p->value;
1931
1932   /* There should always be an appropriate index.  */
1933   gcc_unreachable ();
1934 }
1935
1936 /* Update an entry in the vtable for BINFO, which is in the hierarchy
1937    dominated by T.  FN has been overridden in BINFO; VIRTUALS points to the
1938    corresponding position in the BINFO_VIRTUALS list.  */
1939
1940 static void
1941 update_vtable_entry_for_fn (tree t, tree binfo, tree fn, tree* virtuals,
1942                             unsigned ix)
1943 {
1944   tree b;
1945   tree overrider;
1946   tree delta;
1947   tree virtual_base;
1948   tree first_defn;
1949   tree overrider_fn, overrider_target;
1950   tree target_fn = DECL_THUNK_P (fn) ? THUNK_TARGET (fn) : fn;
1951   tree over_return, base_return;
1952   bool lost = false;
1953
1954   /* Find the nearest primary base (possibly binfo itself) which defines
1955      this function; this is the class the caller will convert to when
1956      calling FN through BINFO.  */
1957   for (b = binfo; ; b = get_primary_binfo (b))
1958     {
1959       gcc_assert (b);
1960       if (look_for_overrides_here (BINFO_TYPE (b), target_fn))
1961         break;
1962
1963       /* The nearest definition is from a lost primary.  */
1964       if (BINFO_LOST_PRIMARY_P (b))
1965         lost = true;
1966     }
1967   first_defn = b;
1968
1969   /* Find the final overrider.  */
1970   overrider = find_final_overrider (TYPE_BINFO (t), b, target_fn);
1971   if (overrider == error_mark_node)
1972     return;
1973   overrider_target = overrider_fn = TREE_PURPOSE (overrider);
1974
1975   /* Check for adjusting covariant return types.  */
1976   over_return = TREE_TYPE (TREE_TYPE (overrider_target));
1977   base_return = TREE_TYPE (TREE_TYPE (target_fn));
1978
1979   if (POINTER_TYPE_P (over_return)
1980       && TREE_CODE (over_return) == TREE_CODE (base_return)
1981       && CLASS_TYPE_P (TREE_TYPE (over_return))
1982       && CLASS_TYPE_P (TREE_TYPE (base_return)))
1983     {
1984       /* If FN is a covariant thunk, we must figure out the adjustment
1985          to the final base FN was converting to. As OVERRIDER_TARGET might
1986          also be converting to the return type of FN, we have to
1987          combine the two conversions here.  */
1988       tree fixed_offset, virtual_offset;
1989
1990       over_return = TREE_TYPE (over_return);
1991       base_return = TREE_TYPE (base_return);
1992
1993       if (DECL_THUNK_P (fn))
1994         {
1995           gcc_assert (DECL_RESULT_THUNK_P (fn));
1996           fixed_offset = ssize_int (THUNK_FIXED_OFFSET (fn));
1997           virtual_offset = THUNK_VIRTUAL_OFFSET (fn);
1998         }
1999       else
2000         fixed_offset = virtual_offset = NULL_TREE;
2001
2002       if (virtual_offset)
2003         /* Find the equivalent binfo within the return type of the
2004            overriding function. We will want the vbase offset from
2005            there.  */
2006         virtual_offset = binfo_for_vbase (BINFO_TYPE (virtual_offset),
2007                                           over_return);
2008       else if (!same_type_ignoring_top_level_qualifiers_p
2009                (over_return, base_return))
2010         {
2011           /* There was no existing virtual thunk (which takes
2012              precedence).  So find the binfo of the base function's
2013              return type within the overriding function's return type.
2014              We cannot call lookup base here, because we're inside a
2015              dfs_walk, and will therefore clobber the BINFO_MARKED
2016              flags.  Fortunately we know the covariancy is valid (it
2017              has already been checked), so we can just iterate along
2018              the binfos, which have been chained in inheritance graph
2019              order.  Of course it is lame that we have to repeat the
2020              search here anyway -- we should really be caching pieces
2021              of the vtable and avoiding this repeated work.  */
2022           tree thunk_binfo, base_binfo;
2023
2024           /* Find the base binfo within the overriding function's
2025              return type.  We will always find a thunk_binfo, except
2026              when the covariancy is invalid (which we will have
2027              already diagnosed).  */
2028           for (base_binfo = TYPE_BINFO (base_return),
2029                thunk_binfo = TYPE_BINFO (over_return);
2030                thunk_binfo;
2031                thunk_binfo = TREE_CHAIN (thunk_binfo))
2032             if (SAME_BINFO_TYPE_P (BINFO_TYPE (thunk_binfo),
2033                                    BINFO_TYPE (base_binfo)))
2034               break;
2035
2036           /* See if virtual inheritance is involved.  */
2037           for (virtual_offset = thunk_binfo;
2038                virtual_offset;
2039                virtual_offset = BINFO_INHERITANCE_CHAIN (virtual_offset))
2040             if (BINFO_VIRTUAL_P (virtual_offset))
2041               break;
2042
2043           if (virtual_offset
2044               || (thunk_binfo && !BINFO_OFFSET_ZEROP (thunk_binfo)))
2045             {
2046               tree offset = convert (ssizetype, BINFO_OFFSET (thunk_binfo));
2047
2048               if (virtual_offset)
2049                 {
2050                   /* We convert via virtual base.  Adjust the fixed
2051                      offset to be from there.  */
2052                   offset = size_diffop
2053                     (offset, convert
2054                      (ssizetype, BINFO_OFFSET (virtual_offset)));
2055                 }
2056               if (fixed_offset)
2057                 /* There was an existing fixed offset, this must be
2058                    from the base just converted to, and the base the
2059                    FN was thunking to.  */
2060                 fixed_offset = size_binop (PLUS_EXPR, fixed_offset, offset);
2061               else
2062                 fixed_offset = offset;
2063             }
2064         }
2065
2066       if (fixed_offset || virtual_offset)
2067         /* Replace the overriding function with a covariant thunk.  We
2068            will emit the overriding function in its own slot as
2069            well.  */
2070         overrider_fn = make_thunk (overrider_target, /*this_adjusting=*/0,
2071                                    fixed_offset, virtual_offset);
2072     }
2073   else
2074     gcc_assert (!DECL_THUNK_P (fn));
2075
2076   /* Assume that we will produce a thunk that convert all the way to
2077      the final overrider, and not to an intermediate virtual base.  */
2078   virtual_base = NULL_TREE;
2079
2080   /* See if we can convert to an intermediate virtual base first, and then
2081      use the vcall offset located there to finish the conversion.  */
2082   for (; b; b = BINFO_INHERITANCE_CHAIN (b))
2083     {
2084       /* If we find the final overrider, then we can stop
2085          walking.  */
2086       if (SAME_BINFO_TYPE_P (BINFO_TYPE (b),
2087                              BINFO_TYPE (TREE_VALUE (overrider))))
2088         break;
2089
2090       /* If we find a virtual base, and we haven't yet found the
2091          overrider, then there is a virtual base between the
2092          declaring base (first_defn) and the final overrider.  */
2093       if (BINFO_VIRTUAL_P (b))
2094         {
2095           virtual_base = b;
2096           break;
2097         }
2098     }
2099
2100   if (overrider_fn != overrider_target && !virtual_base)
2101     {
2102       /* The ABI specifies that a covariant thunk includes a mangling
2103          for a this pointer adjustment.  This-adjusting thunks that
2104          override a function from a virtual base have a vcall
2105          adjustment.  When the virtual base in question is a primary
2106          virtual base, we know the adjustments are zero, (and in the
2107          non-covariant case, we would not use the thunk).
2108          Unfortunately we didn't notice this could happen, when
2109          designing the ABI and so never mandated that such a covariant
2110          thunk should be emitted.  Because we must use the ABI mandated
2111          name, we must continue searching from the binfo where we
2112          found the most recent definition of the function, towards the
2113          primary binfo which first introduced the function into the
2114          vtable.  If that enters a virtual base, we must use a vcall
2115          this-adjusting thunk.  Bleah! */
2116       tree probe = first_defn;
2117
2118       while ((probe = get_primary_binfo (probe))
2119              && (unsigned) list_length (BINFO_VIRTUALS (probe)) > ix)
2120         if (BINFO_VIRTUAL_P (probe))
2121           virtual_base = probe;
2122
2123       if (virtual_base)
2124         /* Even if we find a virtual base, the correct delta is
2125            between the overrider and the binfo we're building a vtable
2126            for.  */
2127         goto virtual_covariant;
2128     }
2129
2130   /* Compute the constant adjustment to the `this' pointer.  The
2131      `this' pointer, when this function is called, will point at BINFO
2132      (or one of its primary bases, which are at the same offset).  */
2133   if (virtual_base)
2134     /* The `this' pointer needs to be adjusted from the declaration to
2135        the nearest virtual base.  */
2136     delta = size_diffop (convert (ssizetype, BINFO_OFFSET (virtual_base)),
2137                          convert (ssizetype, BINFO_OFFSET (first_defn)));
2138   else if (lost)
2139     /* If the nearest definition is in a lost primary, we don't need an
2140        entry in our vtable.  Except possibly in a constructor vtable,
2141        if we happen to get our primary back.  In that case, the offset
2142        will be zero, as it will be a primary base.  */
2143     delta = size_zero_node;
2144   else
2145     /* The `this' pointer needs to be adjusted from pointing to
2146        BINFO to pointing at the base where the final overrider
2147        appears.  */
2148     virtual_covariant:
2149     delta = size_diffop (convert (ssizetype,
2150                                   BINFO_OFFSET (TREE_VALUE (overrider))),
2151                          convert (ssizetype, BINFO_OFFSET (binfo)));
2152
2153   modify_vtable_entry (t, binfo, overrider_fn, delta, virtuals);
2154
2155   if (virtual_base)
2156     BV_VCALL_INDEX (*virtuals)
2157       = get_vcall_index (overrider_target, BINFO_TYPE (virtual_base));
2158   else
2159     BV_VCALL_INDEX (*virtuals) = NULL_TREE;
2160 }
2161
2162 /* Called from modify_all_vtables via dfs_walk.  */
2163
2164 static tree
2165 dfs_modify_vtables (tree binfo, void* data)
2166 {
2167   tree t = (tree) data;
2168   tree virtuals;
2169   tree old_virtuals;
2170   unsigned ix;
2171
2172   if (!TYPE_CONTAINS_VPTR_P (BINFO_TYPE (binfo)))
2173     /* A base without a vtable needs no modification, and its bases
2174        are uninteresting.  */
2175     return dfs_skip_bases;
2176
2177   if (SAME_BINFO_TYPE_P (BINFO_TYPE (binfo), t)
2178       && !CLASSTYPE_HAS_PRIMARY_BASE_P (t))
2179     /* Don't do the primary vtable, if it's new.  */
2180     return NULL_TREE;
2181
2182   if (BINFO_PRIMARY_P (binfo) && !BINFO_VIRTUAL_P (binfo))
2183     /* There's no need to modify the vtable for a non-virtual primary
2184        base; we're not going to use that vtable anyhow.  We do still
2185        need to do this for virtual primary bases, as they could become
2186        non-primary in a construction vtable.  */
2187     return NULL_TREE;
2188
2189   make_new_vtable (t, binfo);
2190
2191   /* Now, go through each of the virtual functions in the virtual
2192      function table for BINFO.  Find the final overrider, and update
2193      the BINFO_VIRTUALS list appropriately.  */
2194   for (ix = 0, virtuals = BINFO_VIRTUALS (binfo),
2195          old_virtuals = BINFO_VIRTUALS (TYPE_BINFO (BINFO_TYPE (binfo)));
2196        virtuals;
2197        ix++, virtuals = TREE_CHAIN (virtuals),
2198          old_virtuals = TREE_CHAIN (old_virtuals))
2199     update_vtable_entry_for_fn (t,
2200                                 binfo,
2201                                 BV_FN (old_virtuals),
2202                                 &virtuals, ix);
2203
2204   return NULL_TREE;
2205 }
2206
2207 /* Update all of the primary and secondary vtables for T.  Create new
2208    vtables as required, and initialize their RTTI information.  Each
2209    of the functions in VIRTUALS is declared in T and may override a
2210    virtual function from a base class; find and modify the appropriate
2211    entries to point to the overriding functions.  Returns a list, in
2212    declaration order, of the virtual functions that are declared in T,
2213    but do not appear in the primary base class vtable, and which
2214    should therefore be appended to the end of the vtable for T.  */
2215
2216 static tree
2217 modify_all_vtables (tree t, tree virtuals)
2218 {
2219   tree binfo = TYPE_BINFO (t);
2220   tree *fnsp;
2221
2222   /* Update all of the vtables.  */
2223   dfs_walk_once (binfo, dfs_modify_vtables, NULL, t);
2224
2225   /* Add virtual functions not already in our primary vtable. These
2226      will be both those introduced by this class, and those overridden
2227      from secondary bases.  It does not include virtuals merely
2228      inherited from secondary bases.  */
2229   for (fnsp = &virtuals; *fnsp; )
2230     {
2231       tree fn = TREE_VALUE (*fnsp);
2232
2233       if (!value_member (fn, BINFO_VIRTUALS (binfo))
2234           || DECL_VINDEX (fn) == error_mark_node)
2235         {
2236           /* We don't need to adjust the `this' pointer when
2237              calling this function.  */
2238           BV_DELTA (*fnsp) = integer_zero_node;
2239           BV_VCALL_INDEX (*fnsp) = NULL_TREE;
2240
2241           /* This is a function not already in our vtable.  Keep it.  */
2242           fnsp = &TREE_CHAIN (*fnsp);
2243         }
2244       else
2245         /* We've already got an entry for this function.  Skip it.  */
2246         *fnsp = TREE_CHAIN (*fnsp);
2247     }
2248
2249   return virtuals;
2250 }
2251
2252 /* Get the base virtual function declarations in T that have the
2253    indicated NAME.  */
2254
2255 static tree
2256 get_basefndecls (tree name, tree t)
2257 {
2258   tree methods;
2259   tree base_fndecls = NULL_TREE;
2260   int n_baseclasses = BINFO_N_BASE_BINFOS (TYPE_BINFO (t));
2261   int i;
2262
2263   /* Find virtual functions in T with the indicated NAME.  */
2264   i = lookup_fnfields_1 (t, name);
2265   if (i != -1)
2266     for (methods = VEC_index (tree, CLASSTYPE_METHOD_VEC (t), i);
2267          methods;
2268          methods = OVL_NEXT (methods))
2269       {
2270         tree method = OVL_CURRENT (methods);
2271
2272         if (TREE_CODE (method) == FUNCTION_DECL
2273             && DECL_VINDEX (method))
2274           base_fndecls = tree_cons (NULL_TREE, method, base_fndecls);
2275       }
2276
2277   if (base_fndecls)
2278     return base_fndecls;
2279
2280   for (i = 0; i < n_baseclasses; i++)
2281     {
2282       tree basetype = BINFO_TYPE (BINFO_BASE_BINFO (TYPE_BINFO (t), i));
2283       base_fndecls = chainon (get_basefndecls (name, basetype),
2284                               base_fndecls);
2285     }
2286
2287   return base_fndecls;
2288 }
2289
2290 /* If this declaration supersedes the declaration of
2291    a method declared virtual in the base class, then
2292    mark this field as being virtual as well.  */
2293
2294 void
2295 check_for_override (tree decl, tree ctype)
2296 {
2297   if (TREE_CODE (decl) == TEMPLATE_DECL)
2298     /* In [temp.mem] we have:
2299
2300          A specialization of a member function template does not
2301          override a virtual function from a base class.  */
2302     return;
2303   if ((DECL_DESTRUCTOR_P (decl)
2304        || IDENTIFIER_VIRTUAL_P (DECL_NAME (decl))
2305        || DECL_CONV_FN_P (decl))
2306       && look_for_overrides (ctype, decl)
2307       && !DECL_STATIC_FUNCTION_P (decl))
2308     /* Set DECL_VINDEX to a value that is neither an INTEGER_CST nor
2309        the error_mark_node so that we know it is an overriding
2310        function.  */
2311     DECL_VINDEX (decl) = decl;
2312
2313   if (DECL_VIRTUAL_P (decl))
2314     {
2315       if (!DECL_VINDEX (decl))
2316         DECL_VINDEX (decl) = error_mark_node;
2317       IDENTIFIER_VIRTUAL_P (DECL_NAME (decl)) = 1;
2318     }
2319 }
2320
2321 /* Warn about hidden virtual functions that are not overridden in t.
2322    We know that constructors and destructors don't apply.  */
2323
2324 void
2325 warn_hidden (tree t)
2326 {
2327   VEC(tree,gc) *method_vec = CLASSTYPE_METHOD_VEC (t);
2328   tree fns;
2329   size_t i;
2330
2331   /* We go through each separately named virtual function.  */
2332   for (i = CLASSTYPE_FIRST_CONVERSION_SLOT;
2333        VEC_iterate (tree, method_vec, i, fns);
2334        ++i)
2335     {
2336       tree fn;
2337       tree name;
2338       tree fndecl;
2339       tree base_fndecls;
2340       tree base_binfo;
2341       tree binfo;
2342       int j;
2343
2344       /* All functions in this slot in the CLASSTYPE_METHOD_VEC will
2345          have the same name.  Figure out what name that is.  */
2346       name = DECL_NAME (OVL_CURRENT (fns));
2347       /* There are no possibly hidden functions yet.  */
2348       base_fndecls = NULL_TREE;
2349       /* Iterate through all of the base classes looking for possibly
2350          hidden functions.  */
2351       for (binfo = TYPE_BINFO (t), j = 0;
2352            BINFO_BASE_ITERATE (binfo, j, base_binfo); j++)
2353         {
2354           tree basetype = BINFO_TYPE (base_binfo);
2355           base_fndecls = chainon (get_basefndecls (name, basetype),
2356                                   base_fndecls);
2357         }
2358
2359       /* If there are no functions to hide, continue.  */
2360       if (!base_fndecls)
2361         continue;
2362
2363       /* Remove any overridden functions.  */
2364       for (fn = fns; fn; fn = OVL_NEXT (fn))
2365         {
2366           fndecl = OVL_CURRENT (fn);
2367           if (DECL_VINDEX (fndecl))
2368             {
2369               tree *prev = &base_fndecls;
2370
2371               while (*prev)
2372                 /* If the method from the base class has the same
2373                    signature as the method from the derived class, it
2374                    has been overridden.  */
2375                 if (same_signature_p (fndecl, TREE_VALUE (*prev)))
2376                   *prev = TREE_CHAIN (*prev);
2377                 else
2378                   prev = &TREE_CHAIN (*prev);
2379             }
2380         }
2381
2382       /* Now give a warning for all base functions without overriders,
2383          as they are hidden.  */
2384       while (base_fndecls)
2385         {
2386           /* Here we know it is a hider, and no overrider exists.  */
2387           warning (0, "%q+D was hidden", TREE_VALUE (base_fndecls));
2388           warning (0, "  by %q+D", fns);
2389           base_fndecls = TREE_CHAIN (base_fndecls);
2390         }
2391     }
2392 }
2393
2394 /* Check for things that are invalid.  There are probably plenty of other
2395    things we should check for also.  */
2396
2397 static void
2398 finish_struct_anon (tree t)
2399 {
2400   tree field;
2401
2402   for (field = TYPE_FIELDS (t); field; field = TREE_CHAIN (field))
2403     {
2404       if (TREE_STATIC (field))
2405         continue;
2406       if (TREE_CODE (field) != FIELD_DECL)
2407         continue;
2408
2409       if (DECL_NAME (field) == NULL_TREE
2410           && ANON_AGGR_TYPE_P (TREE_TYPE (field)))
2411         {
2412           tree elt = TYPE_FIELDS (TREE_TYPE (field));
2413           for (; elt; elt = TREE_CHAIN (elt))
2414             {
2415               /* We're generally only interested in entities the user
2416                  declared, but we also find nested classes by noticing
2417                  the TYPE_DECL that we create implicitly.  You're
2418                  allowed to put one anonymous union inside another,
2419                  though, so we explicitly tolerate that.  We use
2420                  TYPE_ANONYMOUS_P rather than ANON_AGGR_TYPE_P so that
2421                  we also allow unnamed types used for defining fields.  */
2422               if (DECL_ARTIFICIAL (elt)
2423                   && (!DECL_IMPLICIT_TYPEDEF_P (elt)
2424                       || TYPE_ANONYMOUS_P (TREE_TYPE (elt))))
2425                 continue;
2426
2427               if (TREE_CODE (elt) != FIELD_DECL)
2428                 {
2429                   pedwarn ("%q+#D invalid; an anonymous union can "
2430                            "only have non-static data members", elt);
2431                   continue;
2432                 }
2433
2434               if (TREE_PRIVATE (elt))
2435                 pedwarn ("private member %q+#D in anonymous union", elt);
2436               else if (TREE_PROTECTED (elt))
2437                 pedwarn ("protected member %q+#D in anonymous union", elt);
2438
2439               TREE_PRIVATE (elt) = TREE_PRIVATE (field);
2440               TREE_PROTECTED (elt) = TREE_PROTECTED (field);
2441             }
2442         }
2443     }
2444 }
2445
2446 /* Add T to CLASSTYPE_DECL_LIST of current_class_type which
2447    will be used later during class template instantiation.
2448    When FRIEND_P is zero, T can be a static member data (VAR_DECL),
2449    a non-static member data (FIELD_DECL), a member function
2450    (FUNCTION_DECL), a nested type (RECORD_TYPE, ENUM_TYPE),
2451    a typedef (TYPE_DECL) or a member class template (TEMPLATE_DECL)
2452    When FRIEND_P is nonzero, T is either a friend class
2453    (RECORD_TYPE, TEMPLATE_DECL) or a friend function
2454    (FUNCTION_DECL, TEMPLATE_DECL).  */
2455
2456 void
2457 maybe_add_class_template_decl_list (tree type, tree t, int friend_p)
2458 {
2459   /* Save some memory by not creating TREE_LIST if TYPE is not template.  */
2460   if (CLASSTYPE_TEMPLATE_INFO (type))
2461     CLASSTYPE_DECL_LIST (type)
2462       = tree_cons (friend_p ? NULL_TREE : type,
2463                    t, CLASSTYPE_DECL_LIST (type));
2464 }
2465
2466 /* Create default constructors, assignment operators, and so forth for
2467    the type indicated by T, if they are needed.  CANT_HAVE_CONST_CTOR,
2468    and CANT_HAVE_CONST_ASSIGNMENT are nonzero if, for whatever reason,
2469    the class cannot have a default constructor, copy constructor
2470    taking a const reference argument, or an assignment operator taking
2471    a const reference, respectively.  */
2472
2473 static void
2474 add_implicitly_declared_members (tree t,
2475                                  int cant_have_const_cctor,
2476                                  int cant_have_const_assignment)
2477 {
2478   /* Destructor.  */
2479   if (!CLASSTYPE_DESTRUCTORS (t))
2480     {
2481       /* In general, we create destructors lazily.  */
2482       CLASSTYPE_LAZY_DESTRUCTOR (t) = 1;
2483       /* However, if the implicit destructor is non-trivial
2484          destructor, we sometimes have to create it at this point.  */
2485       if (TYPE_HAS_NONTRIVIAL_DESTRUCTOR (t))
2486         {
2487           bool lazy_p = true;
2488
2489           if (TYPE_FOR_JAVA (t))
2490             /* If this a Java class, any non-trivial destructor is
2491                invalid, even if compiler-generated.  Therefore, if the
2492                destructor is non-trivial we create it now.  */
2493             lazy_p = false;
2494           else
2495             {
2496               tree binfo;
2497               tree base_binfo;
2498               int ix;
2499
2500               /* If the implicit destructor will be virtual, then we must
2501                  generate it now because (unfortunately) we do not
2502                  generate virtual tables lazily.  */
2503               binfo = TYPE_BINFO (t);
2504               for (ix = 0; BINFO_BASE_ITERATE (binfo, ix, base_binfo); ix++)
2505                 {
2506                   tree base_type;
2507                   tree dtor;
2508
2509                   base_type = BINFO_TYPE (base_binfo);
2510                   dtor = CLASSTYPE_DESTRUCTORS (base_type);
2511                   if (dtor && DECL_VIRTUAL_P (dtor))
2512                     {
2513                       lazy_p = false;
2514                       break;
2515                     }
2516                 }
2517             }
2518
2519           /* If we can't get away with being lazy, generate the destructor
2520              now.  */
2521           if (!lazy_p)
2522             lazily_declare_fn (sfk_destructor, t);
2523         }
2524     }
2525
2526   /* Default constructor.  */
2527   if (! TYPE_HAS_CONSTRUCTOR (t))
2528     {
2529       TYPE_HAS_DEFAULT_CONSTRUCTOR (t) = 1;
2530       CLASSTYPE_LAZY_DEFAULT_CTOR (t) = 1;
2531     }
2532
2533   /* Copy constructor.  */
2534   if (! TYPE_HAS_INIT_REF (t) && ! TYPE_FOR_JAVA (t))
2535     {
2536       TYPE_HAS_INIT_REF (t) = 1;
2537       TYPE_HAS_CONST_INIT_REF (t) = !cant_have_const_cctor;
2538       CLASSTYPE_LAZY_COPY_CTOR (t) = 1;
2539       TYPE_HAS_CONSTRUCTOR (t) = 1;
2540     }
2541
2542   /* If there is no assignment operator, one will be created if and
2543      when it is needed.  For now, just record whether or not the type
2544      of the parameter to the assignment operator will be a const or
2545      non-const reference.  */
2546   if (!TYPE_HAS_ASSIGN_REF (t) && !TYPE_FOR_JAVA (t))
2547     {
2548       TYPE_HAS_ASSIGN_REF (t) = 1;
2549       TYPE_HAS_CONST_ASSIGN_REF (t) = !cant_have_const_assignment;
2550       CLASSTYPE_LAZY_ASSIGNMENT_OP (t) = 1;
2551     }
2552 }
2553
2554 /* Subroutine of finish_struct_1.  Recursively count the number of fields
2555    in TYPE, including anonymous union members.  */
2556
2557 static int
2558 count_fields (tree fields)
2559 {
2560   tree x;
2561   int n_fields = 0;
2562   for (x = fields; x; x = TREE_CHAIN (x))
2563     {
2564       if (TREE_CODE (x) == FIELD_DECL && ANON_AGGR_TYPE_P (TREE_TYPE (x)))
2565         n_fields += count_fields (TYPE_FIELDS (TREE_TYPE (x)));
2566       else
2567         n_fields += 1;
2568     }
2569   return n_fields;
2570 }
2571
2572 /* Subroutine of finish_struct_1.  Recursively add all the fields in the
2573    TREE_LIST FIELDS to the SORTED_FIELDS_TYPE elts, starting at offset IDX.  */
2574
2575 static int
2576 add_fields_to_record_type (tree fields, struct sorted_fields_type *field_vec, int idx)
2577 {
2578   tree x;
2579   for (x = fields; x; x = TREE_CHAIN (x))
2580     {
2581       if (TREE_CODE (x) == FIELD_DECL && ANON_AGGR_TYPE_P (TREE_TYPE (x)))
2582         idx = add_fields_to_record_type (TYPE_FIELDS (TREE_TYPE (x)), field_vec, idx);
2583       else
2584         field_vec->elts[idx++] = x;
2585     }
2586   return idx;
2587 }
2588
2589 /* FIELD is a bit-field.  We are finishing the processing for its
2590    enclosing type.  Issue any appropriate messages and set appropriate
2591    flags.  */
2592
2593 static void
2594 check_bitfield_decl (tree field)
2595 {
2596   tree type = TREE_TYPE (field);
2597   tree w = NULL_TREE;
2598
2599   /* Detect invalid bit-field type.  */
2600   if (DECL_INITIAL (field)
2601       && ! INTEGRAL_TYPE_P (TREE_TYPE (field)))
2602     {
2603       error ("bit-field %q+#D with non-integral type", field);
2604       w = error_mark_node;
2605     }
2606
2607   /* Detect and ignore out of range field width.  */
2608   if (DECL_INITIAL (field))
2609     {
2610       w = DECL_INITIAL (field);
2611
2612       /* Avoid the non_lvalue wrapper added by fold for PLUS_EXPRs.  */
2613       STRIP_NOPS (w);
2614
2615       /* detect invalid field size.  */
2616       w = integral_constant_value (w);
2617
2618       if (TREE_CODE (w) != INTEGER_CST)
2619         {
2620           error ("bit-field %q+D width not an integer constant", field);
2621           w = error_mark_node;
2622         }
2623       else if (tree_int_cst_sgn (w) < 0)
2624         {
2625           error ("negative width in bit-field %q+D", field);
2626           w = error_mark_node;
2627         }
2628       else if (integer_zerop (w) && DECL_NAME (field) != 0)
2629         {
2630           error ("zero width for bit-field %q+D", field);
2631           w = error_mark_node;
2632         }
2633       else if (compare_tree_int (w, TYPE_PRECISION (type)) > 0
2634                && TREE_CODE (type) != ENUMERAL_TYPE
2635                && TREE_CODE (type) != BOOLEAN_TYPE)
2636         warning (0, "width of %q+D exceeds its type", field);
2637       else if (TREE_CODE (type) == ENUMERAL_TYPE
2638                && (0 > compare_tree_int (w,
2639                                          min_precision (TYPE_MIN_VALUE (type),
2640                                                         TYPE_UNSIGNED (type)))
2641                    ||  0 > compare_tree_int (w,
2642                                              min_precision
2643                                              (TYPE_MAX_VALUE (type),
2644                                               TYPE_UNSIGNED (type)))))
2645         warning (0, "%q+D is too small to hold all values of %q#T", field, type);
2646     }
2647
2648   /* Remove the bit-field width indicator so that the rest of the
2649      compiler does not treat that value as an initializer.  */
2650   DECL_INITIAL (field) = NULL_TREE;
2651
2652   if (w != error_mark_node)
2653     {
2654       DECL_SIZE (field) = convert (bitsizetype, w);
2655       DECL_BIT_FIELD (field) = 1;
2656     }
2657   else
2658     {
2659       /* Non-bit-fields are aligned for their type.  */
2660       DECL_BIT_FIELD (field) = 0;
2661       CLEAR_DECL_C_BIT_FIELD (field);
2662     }
2663 }
2664
2665 /* FIELD is a non bit-field.  We are finishing the processing for its
2666    enclosing type T.  Issue any appropriate messages and set appropriate
2667    flags.  */
2668
2669 static void
2670 check_field_decl (tree field,
2671                   tree t,
2672                   int* cant_have_const_ctor,
2673                   int* no_const_asn_ref,
2674                   int* any_default_members)
2675 {
2676   tree type = strip_array_types (TREE_TYPE (field));
2677
2678   /* An anonymous union cannot contain any fields which would change
2679      the settings of CANT_HAVE_CONST_CTOR and friends.  */
2680   if (ANON_UNION_TYPE_P (type))
2681     ;
2682   /* And, we don't set TYPE_HAS_CONST_INIT_REF, etc., for anonymous
2683      structs.  So, we recurse through their fields here.  */
2684   else if (ANON_AGGR_TYPE_P (type))
2685     {
2686       tree fields;
2687
2688       for (fields = TYPE_FIELDS (type); fields; fields = TREE_CHAIN (fields))
2689         if (TREE_CODE (fields) == FIELD_DECL && !DECL_C_BIT_FIELD (field))
2690           check_field_decl (fields, t, cant_have_const_ctor,
2691                             no_const_asn_ref, any_default_members);
2692     }
2693   /* Check members with class type for constructors, destructors,
2694      etc.  */
2695   else if (CLASS_TYPE_P (type))
2696     {
2697       /* Never let anything with uninheritable virtuals
2698          make it through without complaint.  */
2699       abstract_virtuals_error (field, type);
2700
2701       if (TREE_CODE (t) == UNION_TYPE)
2702         {
2703           if (TYPE_NEEDS_CONSTRUCTING (type))
2704             error ("member %q+#D with constructor not allowed in union",
2705                    field);
2706           if (TYPE_HAS_NONTRIVIAL_DESTRUCTOR (type))
2707             error ("member %q+#D with destructor not allowed in union", field);
2708           if (TYPE_HAS_COMPLEX_ASSIGN_REF (type))
2709             error ("member %q+#D with copy assignment operator not allowed in union",
2710                    field);
2711         }
2712       else
2713         {
2714           TYPE_NEEDS_CONSTRUCTING (t) |= TYPE_NEEDS_CONSTRUCTING (type);
2715           TYPE_HAS_NONTRIVIAL_DESTRUCTOR (t)
2716             |= TYPE_HAS_NONTRIVIAL_DESTRUCTOR (type);
2717           TYPE_HAS_COMPLEX_ASSIGN_REF (t) |= TYPE_HAS_COMPLEX_ASSIGN_REF (type);
2718           TYPE_HAS_COMPLEX_INIT_REF (t) |= TYPE_HAS_COMPLEX_INIT_REF (type);
2719         }
2720
2721       if (!TYPE_HAS_CONST_INIT_REF (type))
2722         *cant_have_const_ctor = 1;
2723
2724       if (!TYPE_HAS_CONST_ASSIGN_REF (type))
2725         *no_const_asn_ref = 1;
2726     }
2727   if (DECL_INITIAL (field) != NULL_TREE)
2728     {
2729       /* `build_class_init_list' does not recognize
2730          non-FIELD_DECLs.  */
2731       if (TREE_CODE (t) == UNION_TYPE && any_default_members != 0)
2732         error ("multiple fields in union %qT initialized", t);
2733       *any_default_members = 1;
2734     }
2735 }
2736
2737 /* Check the data members (both static and non-static), class-scoped
2738    typedefs, etc., appearing in the declaration of T.  Issue
2739    appropriate diagnostics.  Sets ACCESS_DECLS to a list (in
2740    declaration order) of access declarations; each TREE_VALUE in this
2741    list is a USING_DECL.
2742
2743    In addition, set the following flags:
2744
2745      EMPTY_P
2746        The class is empty, i.e., contains no non-static data members.
2747
2748      CANT_HAVE_CONST_CTOR_P
2749        This class cannot have an implicitly generated copy constructor
2750        taking a const reference.
2751
2752      CANT_HAVE_CONST_ASN_REF
2753        This class cannot have an implicitly generated assignment
2754        operator taking a const reference.
2755
2756    All of these flags should be initialized before calling this
2757    function.
2758
2759    Returns a pointer to the end of the TYPE_FIELDs chain; additional
2760    fields can be added by adding to this chain.  */
2761
2762 static void
2763 check_field_decls (tree t, tree *access_decls,
2764                    int *cant_have_const_ctor_p,
2765                    int *no_const_asn_ref_p)
2766 {
2767   tree *field;
2768   tree *next;
2769   bool has_pointers;
2770   int any_default_members;
2771
2772   /* Assume there are no access declarations.  */
2773   *access_decls = NULL_TREE;
2774   /* Assume this class has no pointer members.  */
2775   has_pointers = false;
2776   /* Assume none of the members of this class have default
2777      initializations.  */
2778   any_default_members = 0;
2779
2780   for (field = &TYPE_FIELDS (t); *field; field = next)
2781     {
2782       tree x = *field;
2783       tree type = TREE_TYPE (x);
2784
2785       next = &TREE_CHAIN (x);
2786
2787       if (TREE_CODE (x) == FIELD_DECL)
2788         {
2789           if (TYPE_PACKED (t))
2790             {
2791               if (!pod_type_p (TREE_TYPE (x)) && !TYPE_PACKED (TREE_TYPE (x)))
2792                 warning
2793                   (0,
2794                    "ignoring packed attribute on unpacked non-POD field %q+#D",
2795                    x);
2796               else
2797                 DECL_PACKED (x) = 1;
2798             }
2799
2800           if (DECL_C_BIT_FIELD (x) && integer_zerop (DECL_INITIAL (x)))
2801             /* We don't treat zero-width bitfields as making a class
2802                non-empty.  */
2803             ;
2804           else
2805             {
2806               tree element_type;
2807
2808               /* The class is non-empty.  */
2809               CLASSTYPE_EMPTY_P (t) = 0;
2810               /* The class is not even nearly empty.  */
2811               CLASSTYPE_NEARLY_EMPTY_P (t) = 0;
2812               /* If one of the data members contains an empty class,
2813                  so does T.  */
2814               element_type = strip_array_types (type);
2815               if (CLASS_TYPE_P (element_type)
2816                   && CLASSTYPE_CONTAINS_EMPTY_CLASS_P (element_type))
2817                 CLASSTYPE_CONTAINS_EMPTY_CLASS_P (t) = 1;
2818             }
2819         }
2820
2821       if (TREE_CODE (x) == USING_DECL)
2822         {
2823           /* Prune the access declaration from the list of fields.  */
2824           *field = TREE_CHAIN (x);
2825
2826           /* Save the access declarations for our caller.  */
2827           *access_decls = tree_cons (NULL_TREE, x, *access_decls);
2828
2829           /* Since we've reset *FIELD there's no reason to skip to the
2830              next field.  */
2831           next = field;
2832           continue;
2833         }
2834
2835       if (TREE_CODE (x) == TYPE_DECL
2836           || TREE_CODE (x) == TEMPLATE_DECL)
2837         continue;
2838
2839       /* If we've gotten this far, it's a data member, possibly static,
2840          or an enumerator.  */
2841       DECL_CONTEXT (x) = t;
2842
2843       /* When this goes into scope, it will be a non-local reference.  */
2844       DECL_NONLOCAL (x) = 1;
2845
2846       if (TREE_CODE (t) == UNION_TYPE)
2847         {
2848           /* [class.union]
2849
2850              If a union contains a static data member, or a member of
2851              reference type, the program is ill-formed.  */
2852           if (TREE_CODE (x) == VAR_DECL)
2853             {
2854               error ("%q+D may not be static because it is a member of a union", x);
2855               continue;
2856             }
2857           if (TREE_CODE (type) == REFERENCE_TYPE)
2858             {
2859               error ("%q+D may not have reference type %qT because"
2860                      " it is a member of a union",
2861                      x, type);
2862               continue;
2863             }
2864         }
2865
2866       /* ``A local class cannot have static data members.'' ARM 9.4 */
2867       if (current_function_decl && TREE_STATIC (x))
2868         error ("field %q+D in local class cannot be static", x);
2869
2870       /* Perform error checking that did not get done in
2871          grokdeclarator.  */
2872       if (TREE_CODE (type) == FUNCTION_TYPE)
2873         {
2874           error ("field %q+D invalidly declared function type", x);
2875           type = build_pointer_type (type);
2876           TREE_TYPE (x) = type;
2877         }
2878       else if (TREE_CODE (type) == METHOD_TYPE)
2879         {
2880           error ("field %q+D invalidly declared method type", x);
2881           type = build_pointer_type (type);
2882           TREE_TYPE (x) = type;
2883         }
2884
2885       if (type == error_mark_node)
2886         continue;
2887
2888       if (TREE_CODE (x) == CONST_DECL || TREE_CODE (x) == VAR_DECL)
2889         continue;
2890
2891       /* Now it can only be a FIELD_DECL.  */
2892
2893       if (TREE_PRIVATE (x) || TREE_PROTECTED (x))
2894         CLASSTYPE_NON_AGGREGATE (t) = 1;
2895
2896       /* If this is of reference type, check if it needs an init.
2897          Also do a little ANSI jig if necessary.  */
2898       if (TREE_CODE (type) == REFERENCE_TYPE)
2899         {
2900           CLASSTYPE_NON_POD_P (t) = 1;
2901           if (DECL_INITIAL (x) == NULL_TREE)
2902             SET_CLASSTYPE_REF_FIELDS_NEED_INIT (t, 1);
2903
2904           /* ARM $12.6.2: [A member initializer list] (or, for an
2905              aggregate, initialization by a brace-enclosed list) is the
2906              only way to initialize nonstatic const and reference
2907              members.  */
2908           TYPE_HAS_COMPLEX_ASSIGN_REF (t) = 1;
2909
2910           if (! TYPE_HAS_CONSTRUCTOR (t) && CLASSTYPE_NON_AGGREGATE (t)
2911               && extra_warnings)
2912             warning (0, "non-static reference %q+#D in class without a constructor", x);
2913         }
2914
2915       type = strip_array_types (type);
2916
2917       /* This is used by -Weffc++ (see below). Warn only for pointers
2918          to members which might hold dynamic memory. So do not warn
2919          for pointers to functions or pointers to members.  */
2920       if (TYPE_PTR_P (type)
2921           && !TYPE_PTRFN_P (type)
2922           && !TYPE_PTR_TO_MEMBER_P (type))
2923         has_pointers = true;
2924
2925       if (CLASS_TYPE_P (type))
2926         {
2927           if (CLASSTYPE_REF_FIELDS_NEED_INIT (type))
2928             SET_CLASSTYPE_REF_FIELDS_NEED_INIT (t, 1);
2929           if (CLASSTYPE_READONLY_FIELDS_NEED_INIT (type))
2930             SET_CLASSTYPE_READONLY_FIELDS_NEED_INIT (t, 1);
2931         }
2932
2933       if (DECL_MUTABLE_P (x) || TYPE_HAS_MUTABLE_P (type))
2934         CLASSTYPE_HAS_MUTABLE (t) = 1;
2935
2936       if (! pod_type_p (type))
2937         /* DR 148 now allows pointers to members (which are POD themselves),
2938            to be allowed in POD structs.  */
2939         CLASSTYPE_NON_POD_P (t) = 1;
2940
2941       if (! zero_init_p (type))
2942         CLASSTYPE_NON_ZERO_INIT_P (t) = 1;
2943
2944       /* If any field is const, the structure type is pseudo-const.  */
2945       if (CP_TYPE_CONST_P (type))
2946         {
2947           C_TYPE_FIELDS_READONLY (t) = 1;
2948           if (DECL_INITIAL (x) == NULL_TREE)
2949             SET_CLASSTYPE_READONLY_FIELDS_NEED_INIT (t, 1);
2950
2951           /* ARM $12.6.2: [A member initializer list] (or, for an
2952              aggregate, initialization by a brace-enclosed list) is the
2953              only way to initialize nonstatic const and reference
2954              members.  */
2955           TYPE_HAS_COMPLEX_ASSIGN_REF (t) = 1;
2956
2957           if (! TYPE_HAS_CONSTRUCTOR (t) && CLASSTYPE_NON_AGGREGATE (t)
2958               && extra_warnings)
2959             warning (0, "non-static const member %q+#D in class without a constructor", x);
2960         }
2961       /* A field that is pseudo-const makes the structure likewise.  */
2962       else if (CLASS_TYPE_P (type))
2963         {
2964           C_TYPE_FIELDS_READONLY (t) |= C_TYPE_FIELDS_READONLY (type);
2965           SET_CLASSTYPE_READONLY_FIELDS_NEED_INIT (t,
2966             CLASSTYPE_READONLY_FIELDS_NEED_INIT (t)
2967             | CLASSTYPE_READONLY_FIELDS_NEED_INIT (type));
2968         }
2969
2970       /* Core issue 80: A nonstatic data member is required to have a
2971          different name from the class iff the class has a
2972          user-defined constructor.  */
2973       if (constructor_name_p (DECL_NAME (x), t) && TYPE_HAS_CONSTRUCTOR (t))
2974         pedwarn ("field %q+#D with same name as class", x);
2975
2976       /* We set DECL_C_BIT_FIELD in grokbitfield.
2977          If the type and width are valid, we'll also set DECL_BIT_FIELD.  */
2978       if (DECL_C_BIT_FIELD (x))
2979         check_bitfield_decl (x);
2980       else
2981         check_field_decl (x, t,
2982                           cant_have_const_ctor_p,
2983                           no_const_asn_ref_p,
2984                           &any_default_members);
2985     }
2986
2987   /* Effective C++ rule 11: if a class has dynamic memory held by pointers,
2988      it should also define a copy constructor and an assignment operator to
2989      implement the correct copy semantic (deep vs shallow, etc.). As it is
2990      not feasible to check whether the constructors do allocate dynamic memory
2991      and store it within members, we approximate the warning like this:
2992
2993      -- Warn only if there are members which are pointers
2994      -- Warn only if there is a non-trivial constructor (otherwise,
2995         there cannot be memory allocated).
2996      -- Warn only if there is a non-trivial destructor. We assume that the
2997         user at least implemented the cleanup correctly, and a destructor
2998         is needed to free dynamic memory.
2999
3000      This seems enough for practical purposes.  */
3001     if (warn_ecpp
3002         && has_pointers
3003         && TYPE_HAS_CONSTRUCTOR (t)
3004         && TYPE_HAS_NONTRIVIAL_DESTRUCTOR (t)
3005         && !(TYPE_HAS_INIT_REF (t) && TYPE_HAS_ASSIGN_REF (t)))
3006     {
3007       warning (0, "%q#T has pointer data members", t);
3008
3009       if (! TYPE_HAS_INIT_REF (t))
3010         {
3011           warning (0, "  but does not override %<%T(const %T&)%>", t, t);
3012           if (! TYPE_HAS_ASSIGN_REF (t))
3013             warning (0, "  or %<operator=(const %T&)%>", t);
3014         }
3015       else if (! TYPE_HAS_ASSIGN_REF (t))
3016         warning (0, "  but does not override %<operator=(const %T&)%>", t);
3017     }
3018
3019
3020   /* Check anonymous struct/anonymous union fields.  */
3021   finish_struct_anon (t);
3022
3023   /* We've built up the list of access declarations in reverse order.
3024      Fix that now.  */
3025   *access_decls = nreverse (*access_decls);
3026 }
3027
3028 /* If TYPE is an empty class type, records its OFFSET in the table of
3029    OFFSETS.  */
3030
3031 static int
3032 record_subobject_offset (tree type, tree offset, splay_tree offsets)
3033 {
3034   splay_tree_node n;
3035
3036   if (!is_empty_class (type))
3037     return 0;
3038
3039   /* Record the location of this empty object in OFFSETS.  */
3040   n = splay_tree_lookup (offsets, (splay_tree_key) offset);
3041   if (!n)
3042     n = splay_tree_insert (offsets,
3043                            (splay_tree_key) offset,
3044                            (splay_tree_value) NULL_TREE);
3045   n->value = ((splay_tree_value)
3046               tree_cons (NULL_TREE,
3047                          type,
3048                          (tree) n->value));
3049
3050   return 0;
3051 }
3052
3053 /* Returns nonzero if TYPE is an empty class type and there is
3054    already an entry in OFFSETS for the same TYPE as the same OFFSET.  */
3055
3056 static int
3057 check_subobject_offset (tree type, tree offset, splay_tree offsets)
3058 {
3059   splay_tree_node n;
3060   tree t;
3061
3062   if (!is_empty_class (type))
3063     return 0;
3064
3065   /* Record the location of this empty object in OFFSETS.  */
3066   n = splay_tree_lookup (offsets, (splay_tree_key) offset);
3067   if (!n)
3068     return 0;
3069
3070   for (t = (tree) n->value; t; t = TREE_CHAIN (t))
3071     if (same_type_p (TREE_VALUE (t), type))
3072       return 1;
3073
3074   return 0;
3075 }
3076
3077 /* Walk through all the subobjects of TYPE (located at OFFSET).  Call
3078    F for every subobject, passing it the type, offset, and table of
3079    OFFSETS.  If VBASES_P is one, then virtual non-primary bases should
3080    be traversed.
3081
3082    If MAX_OFFSET is non-NULL, then subobjects with an offset greater
3083    than MAX_OFFSET will not be walked.
3084
3085    If F returns a nonzero value, the traversal ceases, and that value
3086    is returned.  Otherwise, returns zero.  */
3087
3088 static int
3089 walk_subobject_offsets (tree type,
3090                         subobject_offset_fn f,
3091                         tree offset,
3092                         splay_tree offsets,
3093                         tree max_offset,
3094                         int vbases_p)
3095 {
3096   int r = 0;
3097   tree type_binfo = NULL_TREE;
3098
3099   /* If this OFFSET is bigger than the MAX_OFFSET, then we should
3100      stop.  */
3101   if (max_offset && INT_CST_LT (max_offset, offset))
3102     return 0;
3103
3104   if (!TYPE_P (type))
3105     {
3106       if (abi_version_at_least (2))
3107         type_binfo = type;
3108       type = BINFO_TYPE (type);
3109     }
3110
3111   if (CLASS_TYPE_P (type))
3112     {
3113       tree field;
3114       tree binfo;
3115       int i;
3116
3117       /* Avoid recursing into objects that are not interesting.  */
3118       if (!CLASSTYPE_CONTAINS_EMPTY_CLASS_P (type))
3119         return 0;
3120
3121       /* Record the location of TYPE.  */
3122       r = (*f) (type, offset, offsets);
3123       if (r)
3124         return r;
3125
3126       /* Iterate through the direct base classes of TYPE.  */
3127       if (!type_binfo)
3128         type_binfo = TYPE_BINFO (type);
3129       for (i = 0; BINFO_BASE_ITERATE (type_binfo, i, binfo); i++)
3130         {
3131           tree binfo_offset;
3132
3133           if (abi_version_at_least (2)
3134               && BINFO_VIRTUAL_P (binfo))
3135             continue;
3136
3137           if (!vbases_p
3138               && BINFO_VIRTUAL_P (binfo)
3139               && !BINFO_PRIMARY_P (binfo))
3140             continue;
3141
3142           if (!abi_version_at_least (2))
3143             binfo_offset = size_binop (PLUS_EXPR,
3144                                        offset,
3145                                        BINFO_OFFSET (binfo));
3146           else
3147             {
3148               tree orig_binfo;
3149               /* We cannot rely on BINFO_OFFSET being set for the base
3150                  class yet, but the offsets for direct non-virtual
3151                  bases can be calculated by going back to the TYPE.  */
3152               orig_binfo = BINFO_BASE_BINFO (TYPE_BINFO (type), i);
3153               binfo_offset = size_binop (PLUS_EXPR,
3154                                          offset,
3155                                          BINFO_OFFSET (orig_binfo));
3156             }
3157
3158           r = walk_subobject_offsets (binfo,
3159                                       f,
3160                                       binfo_offset,
3161                                       offsets,
3162                                       max_offset,
3163                                       (abi_version_at_least (2)
3164                                        ? /*vbases_p=*/0 : vbases_p));
3165           if (r)
3166             return r;
3167         }
3168
3169       if (abi_version_at_least (2) && CLASSTYPE_VBASECLASSES (type))
3170         {
3171           unsigned ix;
3172           VEC(tree,gc) *vbases;
3173
3174           /* Iterate through the virtual base classes of TYPE.  In G++
3175              3.2, we included virtual bases in the direct base class
3176              loop above, which results in incorrect results; the
3177              correct offsets for virtual bases are only known when
3178              working with the most derived type.  */
3179           if (vbases_p)
3180             for (vbases = CLASSTYPE_VBASECLASSES (type), ix = 0;
3181                  VEC_iterate (tree, vbases, ix, binfo); ix++)
3182               {
3183                 r = walk_subobject_offsets (binfo,
3184                                             f,
3185                                             size_binop (PLUS_EXPR,
3186                                                         offset,
3187                                                         BINFO_OFFSET (binfo)),
3188                                             offsets,
3189                                             max_offset,
3190                                             /*vbases_p=*/0);
3191                 if (r)
3192                   return r;
3193               }
3194           else
3195             {
3196               /* We still have to walk the primary base, if it is
3197                  virtual.  (If it is non-virtual, then it was walked
3198                  above.)  */
3199               tree vbase = get_primary_binfo (type_binfo);
3200
3201               if (vbase && BINFO_VIRTUAL_P (vbase)
3202                   && BINFO_PRIMARY_P (vbase)
3203                   && BINFO_INHERITANCE_CHAIN (vbase) == type_binfo)
3204                 {
3205                   r = (walk_subobject_offsets
3206                        (vbase, f, offset,
3207                         offsets, max_offset, /*vbases_p=*/0));
3208                   if (r)
3209                     return r;
3210                 }
3211             }
3212         }
3213
3214       /* Iterate through the fields of TYPE.  */
3215       for (field = TYPE_FIELDS (type); field; field = TREE_CHAIN (field))
3216         if (TREE_CODE (field) == FIELD_DECL && !DECL_ARTIFICIAL (field))
3217           {
3218             tree field_offset;
3219
3220             if (abi_version_at_least (2))
3221               field_offset = byte_position (field);
3222             else
3223               /* In G++ 3.2, DECL_FIELD_OFFSET was used.  */
3224               field_offset = DECL_FIELD_OFFSET (field);
3225
3226             r = walk_subobject_offsets (TREE_TYPE (field),
3227                                         f,
3228                                         size_binop (PLUS_EXPR,
3229                                                     offset,
3230                                                     field_offset),
3231                                         offsets,
3232                                         max_offset,
3233                                         /*vbases_p=*/1);
3234             if (r)
3235               return r;
3236           }
3237     }
3238   else if (TREE_CODE (type) == ARRAY_TYPE)
3239     {
3240       tree element_type = strip_array_types (type);
3241       tree domain = TYPE_DOMAIN (type);
3242       tree index;
3243
3244       /* Avoid recursing into objects that are not interesting.  */
3245       if (!CLASS_TYPE_P (element_type)
3246           || !CLASSTYPE_CONTAINS_EMPTY_CLASS_P (element_type))
3247         return 0;
3248
3249       /* Step through each of the elements in the array.  */
3250       for (index = size_zero_node;
3251            /* G++ 3.2 had an off-by-one error here.  */
3252            (abi_version_at_least (2)
3253             ? !INT_CST_LT (TYPE_MAX_VALUE (domain), index)
3254             : INT_CST_LT (index, TYPE_MAX_VALUE (domain)));
3255            index = size_binop (PLUS_EXPR, index, size_one_node))
3256         {
3257           r = walk_subobject_offsets (TREE_TYPE (type),
3258                                       f,
3259                                       offset,
3260                                       offsets,
3261                                       max_offset,
3262                                       /*vbases_p=*/1);
3263           if (r)
3264             return r;
3265           offset = size_binop (PLUS_EXPR, offset,
3266                                TYPE_SIZE_UNIT (TREE_TYPE (type)));
3267           /* If this new OFFSET is bigger than the MAX_OFFSET, then
3268              there's no point in iterating through the remaining
3269              elements of the array.  */
3270           if (max_offset && INT_CST_LT (max_offset, offset))
3271             break;
3272         }
3273     }
3274
3275   return 0;
3276 }
3277
3278 /* Record all of the empty subobjects of TYPE (located at OFFSET) in
3279    OFFSETS.  If VBASES_P is nonzero, virtual bases of TYPE are
3280    examined.  */
3281
3282 static void
3283 record_subobject_offsets (tree type,
3284                           tree offset,
3285                           splay_tree offsets,
3286                           int vbases_p)
3287 {
3288   walk_subobject_offsets (type, record_subobject_offset, offset,
3289                           offsets, /*max_offset=*/NULL_TREE, vbases_p);
3290 }
3291
3292 /* Returns nonzero if any of the empty subobjects of TYPE (located at
3293    OFFSET) conflict with entries in OFFSETS.  If VBASES_P is nonzero,
3294    virtual bases of TYPE are examined.  */
3295
3296 static int
3297 layout_conflict_p (tree type,
3298                    tree offset,
3299                    splay_tree offsets,
3300                    int vbases_p)
3301 {
3302   splay_tree_node max_node;
3303
3304   /* Get the node in OFFSETS that indicates the maximum offset where
3305      an empty subobject is located.  */
3306   max_node = splay_tree_max (offsets);
3307   /* If there aren't any empty subobjects, then there's no point in
3308      performing this check.  */
3309   if (!max_node)
3310     return 0;
3311
3312   return walk_subobject_offsets (type, check_subobject_offset, offset,
3313                                  offsets, (tree) (max_node->key),
3314                                  vbases_p);
3315 }
3316
3317 /* DECL is a FIELD_DECL corresponding either to a base subobject of a
3318    non-static data member of the type indicated by RLI.  BINFO is the
3319    binfo corresponding to the base subobject, OFFSETS maps offsets to
3320    types already located at those offsets.  This function determines
3321    the position of the DECL.  */
3322
3323 static void
3324 layout_nonempty_base_or_field (record_layout_info rli,
3325                                tree decl,
3326                                tree binfo,
3327                                splay_tree offsets)
3328 {
3329   tree offset = NULL_TREE;
3330   bool field_p;
3331   tree type;
3332
3333   if (binfo)
3334     {
3335       /* For the purposes of determining layout conflicts, we want to
3336          use the class type of BINFO; TREE_TYPE (DECL) will be the
3337          CLASSTYPE_AS_BASE version, which does not contain entries for
3338          zero-sized bases.  */
3339       type = TREE_TYPE (binfo);
3340       field_p = false;
3341     }
3342   else
3343     {
3344       type = TREE_TYPE (decl);
3345       field_p = true;
3346     }
3347
3348   /* Try to place the field.  It may take more than one try if we have
3349      a hard time placing the field without putting two objects of the
3350      same type at the same address.  */
3351   while (1)
3352     {
3353       struct record_layout_info_s old_rli = *rli;
3354
3355       /* Place this field.  */
3356       place_field (rli, decl);
3357       offset = byte_position (decl);
3358
3359       /* We have to check to see whether or not there is already
3360          something of the same type at the offset we're about to use.
3361          For example, consider:
3362
3363            struct S {};
3364            struct T : public S { int i; };
3365            struct U : public S, public T {};
3366
3367          Here, we put S at offset zero in U.  Then, we can't put T at
3368          offset zero -- its S component would be at the same address
3369          as the S we already allocated.  So, we have to skip ahead.
3370          Since all data members, including those whose type is an
3371          empty class, have nonzero size, any overlap can happen only
3372          with a direct or indirect base-class -- it can't happen with
3373          a data member.  */
3374       /* In a union, overlap is permitted; all members are placed at
3375          offset zero.  */
3376       if (TREE_CODE (rli->t) == UNION_TYPE)
3377         break;
3378       /* G++ 3.2 did not check for overlaps when placing a non-empty
3379          virtual base.  */
3380       if (!abi_version_at_least (2) && binfo && BINFO_VIRTUAL_P (binfo))
3381         break;
3382       if (layout_conflict_p (field_p ? type : binfo, offset,
3383                              offsets, field_p))
3384         {
3385           /* Strip off the size allocated to this field.  That puts us
3386              at the first place we could have put the field with
3387              proper alignment.  */
3388           *rli = old_rli;
3389
3390           /* Bump up by the alignment required for the type.  */
3391           rli->bitpos
3392             = size_binop (PLUS_EXPR, rli->bitpos,
3393                           bitsize_int (binfo
3394                                        ? CLASSTYPE_ALIGN (type)
3395                                        : TYPE_ALIGN (type)));
3396           normalize_rli (rli);
3397         }
3398       else
3399         /* There was no conflict.  We're done laying out this field.  */
3400         break;
3401     }
3402
3403   /* Now that we know where it will be placed, update its
3404      BINFO_OFFSET.  */
3405   if (binfo && CLASS_TYPE_P (BINFO_TYPE (binfo)))
3406     /* Indirect virtual bases may have a nonzero BINFO_OFFSET at
3407        this point because their BINFO_OFFSET is copied from another
3408        hierarchy.  Therefore, we may not need to add the entire
3409        OFFSET.  */
3410     propagate_binfo_offsets (binfo,
3411                              size_diffop (convert (ssizetype, offset),
3412                                           convert (ssizetype,
3413                                                    BINFO_OFFSET (binfo))));
3414 }
3415
3416 /* Returns true if TYPE is empty and OFFSET is nonzero.  */
3417
3418 static int
3419 empty_base_at_nonzero_offset_p (tree type,
3420                                 tree offset,
3421                                 splay_tree offsets ATTRIBUTE_UNUSED)
3422 {
3423   return is_empty_class (type) && !integer_zerop (offset);
3424 }
3425
3426 /* Layout the empty base BINFO.  EOC indicates the byte currently just
3427    past the end of the class, and should be correctly aligned for a
3428    class of the type indicated by BINFO; OFFSETS gives the offsets of
3429    the empty bases allocated so far. T is the most derived
3430    type.  Return nonzero iff we added it at the end.  */
3431
3432 static bool
3433 layout_empty_base (tree binfo, tree eoc, splay_tree offsets)
3434 {
3435   tree alignment;
3436   tree basetype = BINFO_TYPE (binfo);
3437   bool atend = false;
3438
3439   /* This routine should only be used for empty classes.  */
3440   gcc_assert (is_empty_class (basetype));
3441   alignment = ssize_int (CLASSTYPE_ALIGN_UNIT (basetype));
3442
3443   if (!integer_zerop (BINFO_OFFSET (binfo)))
3444     {
3445       if (abi_version_at_least (2))
3446         propagate_binfo_offsets
3447           (binfo, size_diffop (size_zero_node, BINFO_OFFSET (binfo)));
3448       else if (warn_abi)
3449         warning (0, "offset of empty base %qT may not be ABI-compliant and may"
3450                  "change in a future version of GCC",
3451                  BINFO_TYPE (binfo));
3452     }
3453
3454   /* This is an empty base class.  We first try to put it at offset
3455      zero.  */
3456   if (layout_conflict_p (binfo,
3457                          BINFO_OFFSET (binfo),
3458                          offsets,
3459                          /*vbases_p=*/0))
3460     {
3461       /* That didn't work.  Now, we move forward from the next
3462          available spot in the class.  */
3463       atend = true;
3464       propagate_binfo_offsets (binfo, convert (ssizetype, eoc));
3465       while (1)
3466         {
3467           if (!layout_conflict_p (binfo,
3468                                   BINFO_OFFSET (binfo),
3469                                   offsets,
3470                                   /*vbases_p=*/0))
3471             /* We finally found a spot where