OSDN Git Service

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