OSDN Git Service

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