OSDN Git Service

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