OSDN Git Service

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