OSDN Git Service

PR c++/28588
[pf3gnuchains/gcc-fork.git] / gcc / cp / tree.c
1 /* Language-dependent node constructors for parse phase of GNU compiler.
2    Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
3    1999, 2000, 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
4    Hacked by Michael Tiemann (tiemann@cygnus.com)
5
6 This file is part of GCC.
7
8 GCC is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 2, or (at your option)
11 any later version.
12
13 GCC is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16 GNU General Public License for more details.
17
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING.  If not, write to
20 the Free Software Foundation, 51 Franklin Street, Fifth Floor,
21 Boston, MA 02110-1301, USA.  */
22
23 #include "config.h"
24 #include "system.h"
25 #include "coretypes.h"
26 #include "tm.h"
27 #include "tree.h"
28 #include "cp-tree.h"
29 #include "flags.h"
30 #include "real.h"
31 #include "rtl.h"
32 #include "toplev.h"
33 #include "insn-config.h"
34 #include "integrate.h"
35 #include "tree-inline.h"
36 #include "debug.h"
37 #include "target.h"
38 #include "convert.h"
39
40 static tree bot_manip (tree *, int *, void *);
41 static tree bot_replace (tree *, int *, void *);
42 static tree build_cplus_array_type_1 (tree, tree);
43 static int list_hash_eq (const void *, const void *);
44 static hashval_t list_hash_pieces (tree, tree, tree);
45 static hashval_t list_hash (const void *);
46 static cp_lvalue_kind lvalue_p_1 (tree, int);
47 static tree build_target_expr (tree, tree);
48 static tree count_trees_r (tree *, int *, void *);
49 static tree verify_stmt_tree_r (tree *, int *, void *);
50 static tree build_local_temp (tree);
51
52 static tree handle_java_interface_attribute (tree *, tree, tree, int, bool *);
53 static tree handle_com_interface_attribute (tree *, tree, tree, int, bool *);
54 static tree handle_init_priority_attribute (tree *, tree, tree, int, bool *);
55
56 /* If REF is an lvalue, returns the kind of lvalue that REF is.
57    Otherwise, returns clk_none.  If TREAT_CLASS_RVALUES_AS_LVALUES is
58    nonzero, rvalues of class type are considered lvalues.  */
59
60 static cp_lvalue_kind
61 lvalue_p_1 (tree ref,
62             int treat_class_rvalues_as_lvalues)
63 {
64   cp_lvalue_kind op1_lvalue_kind = clk_none;
65   cp_lvalue_kind op2_lvalue_kind = clk_none;
66
67   if (TREE_CODE (TREE_TYPE (ref)) == REFERENCE_TYPE)
68     return clk_ordinary;
69
70   if (ref == current_class_ptr)
71     return clk_none;
72
73   switch (TREE_CODE (ref))
74     {
75       /* preincrements and predecrements are valid lvals, provided
76          what they refer to are valid lvals.  */
77     case PREINCREMENT_EXPR:
78     case PREDECREMENT_EXPR:
79     case SAVE_EXPR:
80     case TRY_CATCH_EXPR:
81     case WITH_CLEANUP_EXPR:
82     case REALPART_EXPR:
83     case IMAGPART_EXPR:
84       return lvalue_p_1 (TREE_OPERAND (ref, 0),
85                          treat_class_rvalues_as_lvalues);
86
87     case COMPONENT_REF:
88       op1_lvalue_kind = lvalue_p_1 (TREE_OPERAND (ref, 0),
89                                     treat_class_rvalues_as_lvalues);
90       /* Look at the member designator.  */
91       if (!op1_lvalue_kind
92           /* The "field" can be a FUNCTION_DECL or an OVERLOAD in some
93              situations.  */
94           || TREE_CODE (TREE_OPERAND (ref, 1)) != FIELD_DECL)
95         ;
96       else if (DECL_C_BIT_FIELD (TREE_OPERAND (ref, 1)))
97         {
98           /* Clear the ordinary bit.  If this object was a class
99              rvalue we want to preserve that information.  */
100           op1_lvalue_kind &= ~clk_ordinary;
101           /* The lvalue is for a bitfield.  */
102           op1_lvalue_kind |= clk_bitfield;
103         }
104       else if (DECL_PACKED (TREE_OPERAND (ref, 1)))
105         op1_lvalue_kind |= clk_packed;
106
107       return op1_lvalue_kind;
108
109     case STRING_CST:
110       return clk_ordinary;
111
112     case CONST_DECL:
113     case VAR_DECL:
114       if (TREE_READONLY (ref) && ! TREE_STATIC (ref)
115           && DECL_LANG_SPECIFIC (ref)
116           && DECL_IN_AGGR_P (ref))
117         return clk_none;
118     case INDIRECT_REF:
119     case ARRAY_REF:
120     case PARM_DECL:
121     case RESULT_DECL:
122       if (TREE_CODE (TREE_TYPE (ref)) != METHOD_TYPE)
123         return clk_ordinary;
124       break;
125
126       /* A currently unresolved scope ref.  */
127     case SCOPE_REF:
128       gcc_unreachable ();
129     case MAX_EXPR:
130     case MIN_EXPR:
131       /* Disallow <? and >? as lvalues if either argument side-effects.  */
132       if (TREE_SIDE_EFFECTS (TREE_OPERAND (ref, 0))
133           || TREE_SIDE_EFFECTS (TREE_OPERAND (ref, 1)))
134         return clk_none;
135       op1_lvalue_kind = lvalue_p_1 (TREE_OPERAND (ref, 0),
136                                     treat_class_rvalues_as_lvalues);
137       op2_lvalue_kind = lvalue_p_1 (TREE_OPERAND (ref, 1),
138                                     treat_class_rvalues_as_lvalues);
139       break;
140
141     case COND_EXPR:
142       op1_lvalue_kind = lvalue_p_1 (TREE_OPERAND (ref, 1),
143                                     treat_class_rvalues_as_lvalues);
144       op2_lvalue_kind = lvalue_p_1 (TREE_OPERAND (ref, 2),
145                                     treat_class_rvalues_as_lvalues);
146       break;
147
148     case MODIFY_EXPR:
149       return clk_ordinary;
150
151     case COMPOUND_EXPR:
152       return lvalue_p_1 (TREE_OPERAND (ref, 1),
153                          treat_class_rvalues_as_lvalues);
154
155     case TARGET_EXPR:
156       return treat_class_rvalues_as_lvalues ? clk_class : clk_none;
157
158     case VA_ARG_EXPR:
159       return (treat_class_rvalues_as_lvalues
160               && CLASS_TYPE_P (TREE_TYPE (ref))
161               ? clk_class : clk_none);
162
163     case CALL_EXPR:
164       /* Any class-valued call would be wrapped in a TARGET_EXPR.  */
165       return clk_none;
166
167     case FUNCTION_DECL:
168       /* All functions (except non-static-member functions) are
169          lvalues.  */
170       return (DECL_NONSTATIC_MEMBER_FUNCTION_P (ref)
171               ? clk_none : clk_ordinary);
172
173     case NON_DEPENDENT_EXPR:
174       /* We must consider NON_DEPENDENT_EXPRs to be lvalues so that
175          things like "&E" where "E" is an expression with a
176          non-dependent type work. It is safe to be lenient because an
177          error will be issued when the template is instantiated if "E"
178          is not an lvalue.  */
179       return clk_ordinary;
180
181     default:
182       break;
183     }
184
185   /* If one operand is not an lvalue at all, then this expression is
186      not an lvalue.  */
187   if (!op1_lvalue_kind || !op2_lvalue_kind)
188     return clk_none;
189
190   /* Otherwise, it's an lvalue, and it has all the odd properties
191      contributed by either operand.  */
192   op1_lvalue_kind = op1_lvalue_kind | op2_lvalue_kind;
193   /* It's not an ordinary lvalue if it involves either a bit-field or
194      a class rvalue.  */
195   if ((op1_lvalue_kind & ~clk_ordinary) != clk_none)
196     op1_lvalue_kind &= ~clk_ordinary;
197   return op1_lvalue_kind;
198 }
199
200 /* Returns the kind of lvalue that REF is, in the sense of
201    [basic.lval].  This function should really be named lvalue_p; it
202    computes the C++ definition of lvalue.  */
203
204 cp_lvalue_kind
205 real_lvalue_p (tree ref)
206 {
207   return lvalue_p_1 (ref,
208                      /*treat_class_rvalues_as_lvalues=*/0);
209 }
210
211 /* This differs from real_lvalue_p in that class rvalues are
212    considered lvalues.  */
213
214 int
215 lvalue_p (tree ref)
216 {
217   return
218     (lvalue_p_1 (ref, /*class rvalue ok*/ 1) != clk_none);
219 }
220
221 /* Test whether DECL is a builtin that may appear in a
222    constant-expression. */
223
224 bool
225 builtin_valid_in_constant_expr_p (tree decl)
226 {
227   /* At present BUILT_IN_CONSTANT_P is the only builtin we're allowing
228      in constant-expressions.  We may want to add other builtins later. */
229   return DECL_IS_BUILTIN_CONSTANT_P (decl);
230 }
231
232 /* Build a TARGET_EXPR, initializing the DECL with the VALUE.  */
233
234 static tree
235 build_target_expr (tree decl, tree value)
236 {
237   tree t;
238
239   t = build4 (TARGET_EXPR, TREE_TYPE (decl), decl, value,
240               cxx_maybe_build_cleanup (decl), NULL_TREE);
241   /* We always set TREE_SIDE_EFFECTS so that expand_expr does not
242      ignore the TARGET_EXPR.  If there really turn out to be no
243      side-effects, then the optimizer should be able to get rid of
244      whatever code is generated anyhow.  */
245   TREE_SIDE_EFFECTS (t) = 1;
246
247   return t;
248 }
249
250 /* Return an undeclared local temporary of type TYPE for use in building a
251    TARGET_EXPR.  */
252
253 static tree
254 build_local_temp (tree type)
255 {
256   tree slot = build_decl (VAR_DECL, NULL_TREE, type);
257   DECL_ARTIFICIAL (slot) = 1;
258   DECL_IGNORED_P (slot) = 1;
259   DECL_CONTEXT (slot) = current_function_decl;
260   layout_decl (slot, 0);
261   return slot;
262 }
263
264 /* INIT is a CALL_EXPR which needs info about its target.
265    TYPE is the type that this initialization should appear to have.
266
267    Build an encapsulation of the initialization to perform
268    and return it so that it can be processed by language-independent
269    and language-specific expression expanders.  */
270
271 tree
272 build_cplus_new (tree type, tree init)
273 {
274   tree fn;
275   tree slot;
276   tree rval;
277   int is_ctor;
278
279   /* Make sure that we're not trying to create an instance of an
280      abstract class.  */
281   abstract_virtuals_error (NULL_TREE, type);
282
283   if (TREE_CODE (init) != CALL_EXPR && TREE_CODE (init) != AGGR_INIT_EXPR)
284     return convert (type, init);
285
286   fn = TREE_OPERAND (init, 0);
287   is_ctor = (TREE_CODE (fn) == ADDR_EXPR
288              && TREE_CODE (TREE_OPERAND (fn, 0)) == FUNCTION_DECL
289              && DECL_CONSTRUCTOR_P (TREE_OPERAND (fn, 0)));
290
291   slot = build_local_temp (type);
292
293   /* We split the CALL_EXPR into its function and its arguments here.
294      Then, in expand_expr, we put them back together.  The reason for
295      this is that this expression might be a default argument
296      expression.  In that case, we need a new temporary every time the
297      expression is used.  That's what break_out_target_exprs does; it
298      replaces every AGGR_INIT_EXPR with a copy that uses a fresh
299      temporary slot.  Then, expand_expr builds up a call-expression
300      using the new slot.  */
301
302   /* If we don't need to use a constructor to create an object of this
303      type, don't mess with AGGR_INIT_EXPR.  */
304   if (is_ctor || TREE_ADDRESSABLE (type))
305     {
306       rval = build3 (AGGR_INIT_EXPR, void_type_node, fn,
307                      TREE_OPERAND (init, 1), slot);
308       TREE_SIDE_EFFECTS (rval) = 1;
309       AGGR_INIT_VIA_CTOR_P (rval) = is_ctor;
310     }
311   else
312     rval = init;
313
314   rval = build_target_expr (slot, rval);
315
316   return rval;
317 }
318
319 /* Build a TARGET_EXPR using INIT to initialize a new temporary of the
320    indicated TYPE.  */
321
322 tree
323 build_target_expr_with_type (tree init, tree type)
324 {
325   gcc_assert (!VOID_TYPE_P (type));
326
327   if (TREE_CODE (init) == TARGET_EXPR)
328     return init;
329   else if (CLASS_TYPE_P (type) && !TYPE_HAS_TRIVIAL_INIT_REF (type)
330            && TREE_CODE (init) != COND_EXPR
331            && TREE_CODE (init) != CONSTRUCTOR
332            && TREE_CODE (init) != VA_ARG_EXPR)
333     /* We need to build up a copy constructor call.  COND_EXPR is a special
334        case because we already have copies on the arms and we don't want
335        another one here.  A CONSTRUCTOR is aggregate initialization, which
336        is handled separately.  A VA_ARG_EXPR is magic creation of an
337        aggregate; there's no additional work to be done.  */
338     return force_rvalue (init);
339
340   return force_target_expr (type, init);
341 }
342
343 /* Like the above function, but without the checking.  This function should
344    only be used by code which is deliberately trying to subvert the type
345    system, such as call_builtin_trap.  */
346
347 tree
348 force_target_expr (tree type, tree init)
349 {
350   tree slot;
351
352   gcc_assert (!VOID_TYPE_P (type));
353
354   slot = build_local_temp (type);
355   return build_target_expr (slot, init);
356 }
357
358 /* Like build_target_expr_with_type, but use the type of INIT.  */
359
360 tree
361 get_target_expr (tree init)
362 {
363   return build_target_expr_with_type (init, TREE_TYPE (init));
364 }
365
366 /* If EXPR is a bitfield reference, convert it to the declared type of
367    the bitfield, and return the resulting expression.  Otherwise,
368    return EXPR itself.  */
369
370 tree
371 convert_bitfield_to_declared_type (tree expr)
372 {
373   tree bitfield_type;
374
375   bitfield_type = is_bitfield_expr_with_lowered_type (expr);
376   if (bitfield_type)
377     expr = convert_to_integer (TYPE_MAIN_VARIANT (bitfield_type),
378                                expr);
379   return expr;
380 }
381
382 /* EXPR is being used in an rvalue context.  Return a version of EXPR
383    that is marked as an rvalue.  */
384
385 tree
386 rvalue (tree expr)
387 {
388   tree type;
389
390   if (error_operand_p (expr))
391     return expr;
392
393   /* [basic.lval]
394
395      Non-class rvalues always have cv-unqualified types.  */
396   type = TREE_TYPE (expr);
397   if (!CLASS_TYPE_P (type) && cp_type_quals (type))
398     type = TYPE_MAIN_VARIANT (type);
399
400   if (!processing_template_decl && real_lvalue_p (expr))
401     expr = build1 (NON_LVALUE_EXPR, type, expr);
402   else if (type != TREE_TYPE (expr))
403     expr = build_nop (type, expr);
404
405   return expr;
406 }
407
408 \f
409 static tree
410 build_cplus_array_type_1 (tree elt_type, tree index_type)
411 {
412   tree t;
413
414   if (elt_type == error_mark_node || index_type == error_mark_node)
415     return error_mark_node;
416
417   if (dependent_type_p (elt_type)
418       || (index_type
419           && value_dependent_expression_p (TYPE_MAX_VALUE (index_type))))
420     {
421       t = make_node (ARRAY_TYPE);
422       TREE_TYPE (t) = elt_type;
423       TYPE_DOMAIN (t) = index_type;
424     }
425   else
426     t = build_array_type (elt_type, index_type);
427
428   /* Push these needs up so that initialization takes place
429      more easily.  */
430   TYPE_NEEDS_CONSTRUCTING (t)
431     = TYPE_NEEDS_CONSTRUCTING (TYPE_MAIN_VARIANT (elt_type));
432   TYPE_HAS_NONTRIVIAL_DESTRUCTOR (t)
433     = TYPE_HAS_NONTRIVIAL_DESTRUCTOR (TYPE_MAIN_VARIANT (elt_type));
434   return t;
435 }
436
437 tree
438 build_cplus_array_type (tree elt_type, tree index_type)
439 {
440   tree t;
441   int type_quals = cp_type_quals (elt_type);
442
443   if (type_quals != TYPE_UNQUALIFIED)
444     elt_type = cp_build_qualified_type (elt_type, TYPE_UNQUALIFIED);
445
446   t = build_cplus_array_type_1 (elt_type, index_type);
447
448   if (type_quals != TYPE_UNQUALIFIED)
449     t = cp_build_qualified_type (t, type_quals);
450
451   return t;
452 }
453 \f
454 /* Make a variant of TYPE, qualified with the TYPE_QUALS.  Handles
455    arrays correctly.  In particular, if TYPE is an array of T's, and
456    TYPE_QUALS is non-empty, returns an array of qualified T's.
457
458    FLAGS determines how to deal with illformed qualifications. If
459    tf_ignore_bad_quals is set, then bad qualifications are dropped
460    (this is permitted if TYPE was introduced via a typedef or template
461    type parameter). If bad qualifications are dropped and tf_warning
462    is set, then a warning is issued for non-const qualifications.  If
463    tf_ignore_bad_quals is not set and tf_error is not set, we
464    return error_mark_node. Otherwise, we issue an error, and ignore
465    the qualifications.
466
467    Qualification of a reference type is valid when the reference came
468    via a typedef or template type argument. [dcl.ref] No such
469    dispensation is provided for qualifying a function type.  [dcl.fct]
470    DR 295 queries this and the proposed resolution brings it into line
471    with qualifying a reference.  We implement the DR.  We also behave
472    in a similar manner for restricting non-pointer types.  */
473
474 tree
475 cp_build_qualified_type_real (tree type,
476                               int type_quals,
477                               tsubst_flags_t complain)
478 {
479   tree result;
480   int bad_quals = TYPE_UNQUALIFIED;
481
482   if (type == error_mark_node)
483     return type;
484
485   if (type_quals == cp_type_quals (type))
486     return type;
487
488   if (TREE_CODE (type) == ARRAY_TYPE)
489     {
490       /* In C++, the qualification really applies to the array element
491          type.  Obtain the appropriately qualified element type.  */
492       tree t;
493       tree element_type
494         = cp_build_qualified_type_real (TREE_TYPE (type),
495                                         type_quals,
496                                         complain);
497
498       if (element_type == error_mark_node)
499         return error_mark_node;
500
501       /* See if we already have an identically qualified type.  */
502       for (t = TYPE_MAIN_VARIANT (type); t; t = TYPE_NEXT_VARIANT (t))
503         if (cp_type_quals (t) == type_quals
504             && TYPE_NAME (t) == TYPE_NAME (type)
505             && TYPE_CONTEXT (t) == TYPE_CONTEXT (type))
506           break;
507
508       if (!t)
509         {
510           /* Make a new array type, just like the old one, but with the
511              appropriately qualified element type.  */
512           t = build_variant_type_copy (type);
513           TREE_TYPE (t) = element_type;
514         }
515
516       /* Even if we already had this variant, we update
517          TYPE_NEEDS_CONSTRUCTING and TYPE_HAS_NONTRIVIAL_DESTRUCTOR in case
518          they changed since the variant was originally created.
519
520          This seems hokey; if there is some way to use a previous
521          variant *without* coming through here,
522          TYPE_NEEDS_CONSTRUCTING will never be updated.  */
523       TYPE_NEEDS_CONSTRUCTING (t)
524         = TYPE_NEEDS_CONSTRUCTING (TYPE_MAIN_VARIANT (element_type));
525       TYPE_HAS_NONTRIVIAL_DESTRUCTOR (t)
526         = TYPE_HAS_NONTRIVIAL_DESTRUCTOR (TYPE_MAIN_VARIANT (element_type));
527       return t;
528     }
529   else if (TYPE_PTRMEMFUNC_P (type))
530     {
531       /* For a pointer-to-member type, we can't just return a
532          cv-qualified version of the RECORD_TYPE.  If we do, we
533          haven't changed the field that contains the actual pointer to
534          a method, and so TYPE_PTRMEMFUNC_FN_TYPE will be wrong.  */
535       tree t;
536
537       t = TYPE_PTRMEMFUNC_FN_TYPE (type);
538       t = cp_build_qualified_type_real (t, type_quals, complain);
539       return build_ptrmemfunc_type (t);
540     }
541
542   /* A reference or method type shall not be cv qualified.
543      [dcl.ref], [dct.fct]  */
544   if (type_quals & (TYPE_QUAL_CONST | TYPE_QUAL_VOLATILE)
545       && (TREE_CODE (type) == REFERENCE_TYPE
546           || TREE_CODE (type) == METHOD_TYPE))
547     {
548       bad_quals |= type_quals & (TYPE_QUAL_CONST | TYPE_QUAL_VOLATILE);
549       type_quals &= ~(TYPE_QUAL_CONST | TYPE_QUAL_VOLATILE);
550     }
551
552   /* A restrict-qualified type must be a pointer (or reference)
553      to object or incomplete type, or a function type. */
554   if ((type_quals & TYPE_QUAL_RESTRICT)
555       && TREE_CODE (type) != TEMPLATE_TYPE_PARM
556       && TREE_CODE (type) != TYPENAME_TYPE
557       && TREE_CODE (type) != FUNCTION_TYPE
558       && !POINTER_TYPE_P (type))
559     {
560       bad_quals |= TYPE_QUAL_RESTRICT;
561       type_quals &= ~TYPE_QUAL_RESTRICT;
562     }
563
564   if (bad_quals == TYPE_UNQUALIFIED)
565     /*OK*/;
566   else if (!(complain & (tf_error | tf_ignore_bad_quals)))
567     return error_mark_node;
568   else
569     {
570       if (complain & tf_ignore_bad_quals)
571         /* We're not going to warn about constifying things that can't
572            be constified.  */
573         bad_quals &= ~TYPE_QUAL_CONST;
574       if (bad_quals)
575         {
576           tree bad_type = build_qualified_type (ptr_type_node, bad_quals);
577
578           if (!(complain & tf_ignore_bad_quals))
579             error ("%qV qualifiers cannot be applied to %qT",
580                    bad_type, type);
581         }
582     }
583
584   /* Retrieve (or create) the appropriately qualified variant.  */
585   result = build_qualified_type (type, type_quals);
586
587   /* If this was a pointer-to-method type, and we just made a copy,
588      then we need to unshare the record that holds the cached
589      pointer-to-member-function type, because these will be distinct
590      between the unqualified and qualified types.  */
591   if (result != type
592       && TREE_CODE (type) == POINTER_TYPE
593       && TREE_CODE (TREE_TYPE (type)) == METHOD_TYPE)
594     TYPE_LANG_SPECIFIC (result) = NULL;
595
596   return result;
597 }
598
599 /* Returns the canonical version of TYPE.  In other words, if TYPE is
600    a typedef, returns the underlying type.  The cv-qualification of
601    the type returned matches the type input; they will always be
602    compatible types.  */
603
604 tree
605 canonical_type_variant (tree t)
606 {
607   return cp_build_qualified_type (TYPE_MAIN_VARIANT (t), cp_type_quals (t));
608 }
609 \f
610 /* Makes a copy of BINFO and TYPE, which is to be inherited into a
611    graph dominated by T.  If BINFO is NULL, TYPE is a dependent base,
612    and we do a shallow copy.  If BINFO is non-NULL, we do a deep copy.
613    VIRT indicates whether TYPE is inherited virtually or not.
614    IGO_PREV points at the previous binfo of the inheritance graph
615    order chain.  The newly copied binfo's TREE_CHAIN forms this
616    ordering.
617
618    The CLASSTYPE_VBASECLASSES vector of T is constructed in the
619    correct order. That is in the order the bases themselves should be
620    constructed in.
621
622    The BINFO_INHERITANCE of a virtual base class points to the binfo
623    of the most derived type. ??? We could probably change this so that
624    BINFO_INHERITANCE becomes synonymous with BINFO_PRIMARY, and hence
625    remove a field.  They currently can only differ for primary virtual
626    virtual bases.  */
627
628 tree
629 copy_binfo (tree binfo, tree type, tree t, tree *igo_prev, int virt)
630 {
631   tree new_binfo;
632
633   if (virt)
634     {
635       /* See if we've already made this virtual base.  */
636       new_binfo = binfo_for_vbase (type, t);
637       if (new_binfo)
638         return new_binfo;
639     }
640
641   new_binfo = make_tree_binfo (binfo ? BINFO_N_BASE_BINFOS (binfo) : 0);
642   BINFO_TYPE (new_binfo) = type;
643
644   /* Chain it into the inheritance graph.  */
645   TREE_CHAIN (*igo_prev) = new_binfo;
646   *igo_prev = new_binfo;
647
648   if (binfo)
649     {
650       int ix;
651       tree base_binfo;
652
653       gcc_assert (!BINFO_DEPENDENT_BASE_P (binfo));
654       gcc_assert (SAME_BINFO_TYPE_P (BINFO_TYPE (binfo), type));
655
656       BINFO_OFFSET (new_binfo) = BINFO_OFFSET (binfo);
657       BINFO_VIRTUALS (new_binfo) = BINFO_VIRTUALS (binfo);
658
659       /* We do not need to copy the accesses, as they are read only.  */
660       BINFO_BASE_ACCESSES (new_binfo) = BINFO_BASE_ACCESSES (binfo);
661
662       /* Recursively copy base binfos of BINFO.  */
663       for (ix = 0; BINFO_BASE_ITERATE (binfo, ix, base_binfo); ix++)
664         {
665           tree new_base_binfo;
666
667           gcc_assert (!BINFO_DEPENDENT_BASE_P (base_binfo));
668           new_base_binfo = copy_binfo (base_binfo, BINFO_TYPE (base_binfo),
669                                        t, igo_prev,
670                                        BINFO_VIRTUAL_P (base_binfo));
671
672           if (!BINFO_INHERITANCE_CHAIN (new_base_binfo))
673             BINFO_INHERITANCE_CHAIN (new_base_binfo) = new_binfo;
674           BINFO_BASE_APPEND (new_binfo, new_base_binfo);
675         }
676     }
677   else
678     BINFO_DEPENDENT_BASE_P (new_binfo) = 1;
679
680   if (virt)
681     {
682       /* Push it onto the list after any virtual bases it contains
683          will have been pushed.  */
684       VEC_quick_push (tree, CLASSTYPE_VBASECLASSES (t), new_binfo);
685       BINFO_VIRTUAL_P (new_binfo) = 1;
686       BINFO_INHERITANCE_CHAIN (new_binfo) = TYPE_BINFO (t);
687     }
688
689   return new_binfo;
690 }
691 \f
692 /* Hashing of lists so that we don't make duplicates.
693    The entry point is `list_hash_canon'.  */
694
695 /* Now here is the hash table.  When recording a list, it is added
696    to the slot whose index is the hash code mod the table size.
697    Note that the hash table is used for several kinds of lists.
698    While all these live in the same table, they are completely independent,
699    and the hash code is computed differently for each of these.  */
700
701 static GTY ((param_is (union tree_node))) htab_t list_hash_table;
702
703 struct list_proxy
704 {
705   tree purpose;
706   tree value;
707   tree chain;
708 };
709
710 /* Compare ENTRY (an entry in the hash table) with DATA (a list_proxy
711    for a node we are thinking about adding).  */
712
713 static int
714 list_hash_eq (const void* entry, const void* data)
715 {
716   tree t = (tree) entry;
717   struct list_proxy *proxy = (struct list_proxy *) data;
718
719   return (TREE_VALUE (t) == proxy->value
720           && TREE_PURPOSE (t) == proxy->purpose
721           && TREE_CHAIN (t) == proxy->chain);
722 }
723
724 /* Compute a hash code for a list (chain of TREE_LIST nodes
725    with goodies in the TREE_PURPOSE, TREE_VALUE, and bits of the
726    TREE_COMMON slots), by adding the hash codes of the individual entries.  */
727
728 static hashval_t
729 list_hash_pieces (tree purpose, tree value, tree chain)
730 {
731   hashval_t hashcode = 0;
732
733   if (chain)
734     hashcode += TREE_HASH (chain);
735
736   if (value)
737     hashcode += TREE_HASH (value);
738   else
739     hashcode += 1007;
740   if (purpose)
741     hashcode += TREE_HASH (purpose);
742   else
743     hashcode += 1009;
744   return hashcode;
745 }
746
747 /* Hash an already existing TREE_LIST.  */
748
749 static hashval_t
750 list_hash (const void* p)
751 {
752   tree t = (tree) p;
753   return list_hash_pieces (TREE_PURPOSE (t),
754                            TREE_VALUE (t),
755                            TREE_CHAIN (t));
756 }
757
758 /* Given list components PURPOSE, VALUE, AND CHAIN, return the canonical
759    object for an identical list if one already exists.  Otherwise, build a
760    new one, and record it as the canonical object.  */
761
762 tree
763 hash_tree_cons (tree purpose, tree value, tree chain)
764 {
765   int hashcode = 0;
766   void **slot;
767   struct list_proxy proxy;
768
769   /* Hash the list node.  */
770   hashcode = list_hash_pieces (purpose, value, chain);
771   /* Create a proxy for the TREE_LIST we would like to create.  We
772      don't actually create it so as to avoid creating garbage.  */
773   proxy.purpose = purpose;
774   proxy.value = value;
775   proxy.chain = chain;
776   /* See if it is already in the table.  */
777   slot = htab_find_slot_with_hash (list_hash_table, &proxy, hashcode,
778                                    INSERT);
779   /* If not, create a new node.  */
780   if (!*slot)
781     *slot = tree_cons (purpose, value, chain);
782   return (tree) *slot;
783 }
784
785 /* Constructor for hashed lists.  */
786
787 tree
788 hash_tree_chain (tree value, tree chain)
789 {
790   return hash_tree_cons (NULL_TREE, value, chain);
791 }
792 \f
793 void
794 debug_binfo (tree elem)
795 {
796   HOST_WIDE_INT n;
797   tree virtuals;
798
799   fprintf (stderr, "type \"%s\", offset = " HOST_WIDE_INT_PRINT_DEC
800            "\nvtable type:\n",
801            TYPE_NAME_STRING (BINFO_TYPE (elem)),
802            TREE_INT_CST_LOW (BINFO_OFFSET (elem)));
803   debug_tree (BINFO_TYPE (elem));
804   if (BINFO_VTABLE (elem))
805     fprintf (stderr, "vtable decl \"%s\"\n",
806              IDENTIFIER_POINTER (DECL_NAME (get_vtbl_decl_for_binfo (elem))));
807   else
808     fprintf (stderr, "no vtable decl yet\n");
809   fprintf (stderr, "virtuals:\n");
810   virtuals = BINFO_VIRTUALS (elem);
811   n = 0;
812
813   while (virtuals)
814     {
815       tree fndecl = TREE_VALUE (virtuals);
816       fprintf (stderr, "%s [%ld =? %ld]\n",
817                IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (fndecl)),
818                (long) n, (long) TREE_INT_CST_LOW (DECL_VINDEX (fndecl)));
819       ++n;
820       virtuals = TREE_CHAIN (virtuals);
821     }
822 }
823
824 /* Build a representation for the qualified name SCOPE::NAME.  TYPE is
825    the type of the result expression, if known, or NULL_TREE if the
826    resulting expression is type-dependent.  If TEMPLATE_P is true,
827    NAME is known to be a template because the user explicitly used the
828    "template" keyword after the "::".
829
830    All SCOPE_REFs should be built by use of this function.  */
831
832 tree
833 build_qualified_name (tree type, tree scope, tree name, bool template_p)
834 {
835   tree t;
836   if (type == error_mark_node
837       || scope == error_mark_node
838       || name == error_mark_node)
839     return error_mark_node;
840   t = build2 (SCOPE_REF, type, scope, name);
841   QUALIFIED_NAME_IS_TEMPLATE (t) = template_p;
842   return t;
843 }
844
845 /* Returns non-zero if X is an expression for a (possibly overloaded)
846    function.  If "f" is a function or function template, "f", "c->f",
847    "c.f", "C::f", and "f<int>" will all be considered possibly
848    overloaded functions.  Returns 2 if the function is actually
849    overloaded, i.e., if it is impossible to know the the type of the
850    function without performing overload resolution.  */
851  
852 int
853 is_overloaded_fn (tree x)
854 {
855   /* A baselink is also considered an overloaded function.  */
856   if (TREE_CODE (x) == OFFSET_REF)
857     x = TREE_OPERAND (x, 1);
858   if (BASELINK_P (x))
859     x = BASELINK_FUNCTIONS (x);
860   if (TREE_CODE (x) == TEMPLATE_ID_EXPR
861       || DECL_FUNCTION_TEMPLATE_P (OVL_CURRENT (x))
862       || (TREE_CODE (x) == OVERLOAD && OVL_CHAIN (x)))
863     return 2;
864   return  (TREE_CODE (x) == FUNCTION_DECL
865            || TREE_CODE (x) == OVERLOAD);
866 }
867
868 /* Returns true iff X is an expression for an overloaded function
869    whose type cannot be known without performing overload
870    resolution.  */
871
872 bool
873 really_overloaded_fn (tree x)
874 {
875   return is_overloaded_fn (x) == 2;
876 }
877
878 tree
879 get_first_fn (tree from)
880 {
881   gcc_assert (is_overloaded_fn (from));
882   /* A baselink is also considered an overloaded function.  */
883   if (BASELINK_P (from))
884     from = BASELINK_FUNCTIONS (from);
885   return OVL_CURRENT (from);
886 }
887
888 /* Return a new OVL node, concatenating it with the old one.  */
889
890 tree
891 ovl_cons (tree decl, tree chain)
892 {
893   tree result = make_node (OVERLOAD);
894   TREE_TYPE (result) = unknown_type_node;
895   OVL_FUNCTION (result) = decl;
896   TREE_CHAIN (result) = chain;
897
898   return result;
899 }
900
901 /* Build a new overloaded function. If this is the first one,
902    just return it; otherwise, ovl_cons the _DECLs */
903
904 tree
905 build_overload (tree decl, tree chain)
906 {
907   if (! chain && TREE_CODE (decl) != TEMPLATE_DECL)
908     return decl;
909   if (chain && TREE_CODE (chain) != OVERLOAD)
910     chain = ovl_cons (chain, NULL_TREE);
911   return ovl_cons (decl, chain);
912 }
913
914 \f
915 #define PRINT_RING_SIZE 4
916
917 const char *
918 cxx_printable_name (tree decl, int v)
919 {
920   static tree decl_ring[PRINT_RING_SIZE];
921   static char *print_ring[PRINT_RING_SIZE];
922   static int ring_counter;
923   int i;
924
925   /* Only cache functions.  */
926   if (v < 2
927       || TREE_CODE (decl) != FUNCTION_DECL
928       || DECL_LANG_SPECIFIC (decl) == 0)
929     return lang_decl_name (decl, v);
930
931   /* See if this print name is lying around.  */
932   for (i = 0; i < PRINT_RING_SIZE; i++)
933     if (decl_ring[i] == decl)
934       /* yes, so return it.  */
935       return print_ring[i];
936
937   if (++ring_counter == PRINT_RING_SIZE)
938     ring_counter = 0;
939
940   if (current_function_decl != NULL_TREE)
941     {
942       if (decl_ring[ring_counter] == current_function_decl)
943         ring_counter += 1;
944       if (ring_counter == PRINT_RING_SIZE)
945         ring_counter = 0;
946       gcc_assert (decl_ring[ring_counter] != current_function_decl);
947     }
948
949   if (print_ring[ring_counter])
950     free (print_ring[ring_counter]);
951
952   print_ring[ring_counter] = xstrdup (lang_decl_name (decl, v));
953   decl_ring[ring_counter] = decl;
954   return print_ring[ring_counter];
955 }
956 \f
957 /* Build the FUNCTION_TYPE or METHOD_TYPE which may throw exceptions
958    listed in RAISES.  */
959
960 tree
961 build_exception_variant (tree type, tree raises)
962 {
963   tree v = TYPE_MAIN_VARIANT (type);
964   int type_quals = TYPE_QUALS (type);
965
966   for (; v; v = TYPE_NEXT_VARIANT (v))
967     if (check_qualified_type (v, type, type_quals)
968         && comp_except_specs (raises, TYPE_RAISES_EXCEPTIONS (v), 1))
969       return v;
970
971   /* Need to build a new variant.  */
972   v = build_variant_type_copy (type);
973   TYPE_RAISES_EXCEPTIONS (v) = raises;
974   return v;
975 }
976
977 /* Given a TEMPLATE_TEMPLATE_PARM node T, create a new
978    BOUND_TEMPLATE_TEMPLATE_PARM bound with NEWARGS as its template
979    arguments.  */
980
981 tree
982 bind_template_template_parm (tree t, tree newargs)
983 {
984   tree decl = TYPE_NAME (t);
985   tree t2;
986
987   t2 = make_aggr_type (BOUND_TEMPLATE_TEMPLATE_PARM);
988   decl = build_decl (TYPE_DECL, DECL_NAME (decl), NULL_TREE);
989
990   /* These nodes have to be created to reflect new TYPE_DECL and template
991      arguments.  */
992   TEMPLATE_TYPE_PARM_INDEX (t2) = copy_node (TEMPLATE_TYPE_PARM_INDEX (t));
993   TEMPLATE_PARM_DECL (TEMPLATE_TYPE_PARM_INDEX (t2)) = decl;
994   TEMPLATE_TEMPLATE_PARM_TEMPLATE_INFO (t2)
995     = tree_cons (TEMPLATE_TEMPLATE_PARM_TEMPLATE_DECL (t),
996                  newargs, NULL_TREE);
997
998   TREE_TYPE (decl) = t2;
999   TYPE_NAME (t2) = decl;
1000   TYPE_STUB_DECL (t2) = decl;
1001   TYPE_SIZE (t2) = 0;
1002
1003   return t2;
1004 }
1005
1006 /* Called from count_trees via walk_tree.  */
1007
1008 static tree
1009 count_trees_r (tree *tp, int *walk_subtrees, void *data)
1010 {
1011   ++*((int *) data);
1012
1013   if (TYPE_P (*tp))
1014     *walk_subtrees = 0;
1015
1016   return NULL_TREE;
1017 }
1018
1019 /* Debugging function for measuring the rough complexity of a tree
1020    representation.  */
1021
1022 int
1023 count_trees (tree t)
1024 {
1025   int n_trees = 0;
1026   walk_tree_without_duplicates (&t, count_trees_r, &n_trees);
1027   return n_trees;
1028 }
1029
1030 /* Called from verify_stmt_tree via walk_tree.  */
1031
1032 static tree
1033 verify_stmt_tree_r (tree* tp,
1034                     int* walk_subtrees ATTRIBUTE_UNUSED ,
1035                     void* data)
1036 {
1037   tree t = *tp;
1038   htab_t *statements = (htab_t *) data;
1039   void **slot;
1040
1041   if (!STATEMENT_CODE_P (TREE_CODE (t)))
1042     return NULL_TREE;
1043
1044   /* If this statement is already present in the hash table, then
1045      there is a circularity in the statement tree.  */
1046   gcc_assert (!htab_find (*statements, t));
1047
1048   slot = htab_find_slot (*statements, t, INSERT);
1049   *slot = t;
1050
1051   return NULL_TREE;
1052 }
1053
1054 /* Debugging function to check that the statement T has not been
1055    corrupted.  For now, this function simply checks that T contains no
1056    circularities.  */
1057
1058 void
1059 verify_stmt_tree (tree t)
1060 {
1061   htab_t statements;
1062   statements = htab_create (37, htab_hash_pointer, htab_eq_pointer, NULL);
1063   walk_tree (&t, verify_stmt_tree_r, &statements, NULL);
1064   htab_delete (statements);
1065 }
1066
1067 /* Check if the type T depends on a type with no linkage and if so, return
1068    it.  If RELAXED_P then do not consider a class type declared within
1069    a TREE_PUBLIC function to have no linkage.  */
1070
1071 tree
1072 no_linkage_check (tree t, bool relaxed_p)
1073 {
1074   tree r;
1075
1076   /* There's no point in checking linkage on template functions; we
1077      can't know their complete types.  */
1078   if (processing_template_decl)
1079     return NULL_TREE;
1080
1081   switch (TREE_CODE (t))
1082     {
1083       tree fn;
1084
1085     case RECORD_TYPE:
1086       if (TYPE_PTRMEMFUNC_P (t))
1087         goto ptrmem;
1088       /* Fall through.  */
1089     case UNION_TYPE:
1090       if (!CLASS_TYPE_P (t))
1091         return NULL_TREE;
1092       /* Fall through.  */
1093     case ENUMERAL_TYPE:
1094       if (TYPE_ANONYMOUS_P (t))
1095         return t;
1096       fn = decl_function_context (TYPE_MAIN_DECL (t));
1097       if (fn && (!relaxed_p || !TREE_PUBLIC (fn)))
1098         return t;
1099       return NULL_TREE;
1100
1101     case ARRAY_TYPE:
1102     case POINTER_TYPE:
1103     case REFERENCE_TYPE:
1104       return no_linkage_check (TREE_TYPE (t), relaxed_p);
1105
1106     case OFFSET_TYPE:
1107     ptrmem:
1108       r = no_linkage_check (TYPE_PTRMEM_POINTED_TO_TYPE (t),
1109                             relaxed_p);
1110       if (r)
1111         return r;
1112       return no_linkage_check (TYPE_PTRMEM_CLASS_TYPE (t), relaxed_p);
1113
1114     case METHOD_TYPE:
1115       r = no_linkage_check (TYPE_METHOD_BASETYPE (t), relaxed_p);
1116       if (r)
1117         return r;
1118       /* Fall through.  */
1119     case FUNCTION_TYPE:
1120       {
1121         tree parm;
1122         for (parm = TYPE_ARG_TYPES (t);
1123              parm && parm != void_list_node;
1124              parm = TREE_CHAIN (parm))
1125           {
1126             r = no_linkage_check (TREE_VALUE (parm), relaxed_p);
1127             if (r)
1128               return r;
1129           }
1130         return no_linkage_check (TREE_TYPE (t), relaxed_p);
1131       }
1132
1133     default:
1134       return NULL_TREE;
1135     }
1136 }
1137
1138 #ifdef GATHER_STATISTICS
1139 extern int depth_reached;
1140 #endif
1141
1142 void
1143 cxx_print_statistics (void)
1144 {
1145   print_search_statistics ();
1146   print_class_statistics ();
1147 #ifdef GATHER_STATISTICS
1148   fprintf (stderr, "maximum template instantiation depth reached: %d\n",
1149            depth_reached);
1150 #endif
1151 }
1152
1153 /* Return, as an INTEGER_CST node, the number of elements for TYPE
1154    (which is an ARRAY_TYPE).  This counts only elements of the top
1155    array.  */
1156
1157 tree
1158 array_type_nelts_top (tree type)
1159 {
1160   return fold_build2 (PLUS_EXPR, sizetype,
1161                       array_type_nelts (type),
1162                       integer_one_node);
1163 }
1164
1165 /* Return, as an INTEGER_CST node, the number of elements for TYPE
1166    (which is an ARRAY_TYPE).  This one is a recursive count of all
1167    ARRAY_TYPEs that are clumped together.  */
1168
1169 tree
1170 array_type_nelts_total (tree type)
1171 {
1172   tree sz = array_type_nelts_top (type);
1173   type = TREE_TYPE (type);
1174   while (TREE_CODE (type) == ARRAY_TYPE)
1175     {
1176       tree n = array_type_nelts_top (type);
1177       sz = fold_build2 (MULT_EXPR, sizetype, sz, n);
1178       type = TREE_TYPE (type);
1179     }
1180   return sz;
1181 }
1182
1183 /* Called from break_out_target_exprs via mapcar.  */
1184
1185 static tree
1186 bot_manip (tree* tp, int* walk_subtrees, void* data)
1187 {
1188   splay_tree target_remap = ((splay_tree) data);
1189   tree t = *tp;
1190
1191   if (!TYPE_P (t) && TREE_CONSTANT (t))
1192     {
1193       /* There can't be any TARGET_EXPRs or their slot variables below
1194          this point.  We used to check !TREE_SIDE_EFFECTS, but then we
1195          failed to copy an ADDR_EXPR of the slot VAR_DECL.  */
1196       *walk_subtrees = 0;
1197       return NULL_TREE;
1198     }
1199   if (TREE_CODE (t) == TARGET_EXPR)
1200     {
1201       tree u;
1202
1203       if (TREE_CODE (TREE_OPERAND (t, 1)) == AGGR_INIT_EXPR)
1204         u = build_cplus_new
1205           (TREE_TYPE (t), break_out_target_exprs (TREE_OPERAND (t, 1)));
1206       else
1207         u = build_target_expr_with_type
1208           (break_out_target_exprs (TREE_OPERAND (t, 1)), TREE_TYPE (t));
1209
1210       /* Map the old variable to the new one.  */
1211       splay_tree_insert (target_remap,
1212                          (splay_tree_key) TREE_OPERAND (t, 0),
1213                          (splay_tree_value) TREE_OPERAND (u, 0));
1214
1215       /* Replace the old expression with the new version.  */
1216       *tp = u;
1217       /* We don't have to go below this point; the recursive call to
1218          break_out_target_exprs will have handled anything below this
1219          point.  */
1220       *walk_subtrees = 0;
1221       return NULL_TREE;
1222     }
1223
1224   /* Make a copy of this node.  */
1225   return copy_tree_r (tp, walk_subtrees, NULL);
1226 }
1227
1228 /* Replace all remapped VAR_DECLs in T with their new equivalents.
1229    DATA is really a splay-tree mapping old variables to new
1230    variables.  */
1231
1232 static tree
1233 bot_replace (tree* t,
1234              int* walk_subtrees ATTRIBUTE_UNUSED ,
1235              void* data)
1236 {
1237   splay_tree target_remap = ((splay_tree) data);
1238
1239   if (TREE_CODE (*t) == VAR_DECL)
1240     {
1241       splay_tree_node n = splay_tree_lookup (target_remap,
1242                                              (splay_tree_key) *t);
1243       if (n)
1244         *t = (tree) n->value;
1245     }
1246
1247   return NULL_TREE;
1248 }
1249
1250 /* When we parse a default argument expression, we may create
1251    temporary variables via TARGET_EXPRs.  When we actually use the
1252    default-argument expression, we make a copy of the expression, but
1253    we must replace the temporaries with appropriate local versions.  */
1254
1255 tree
1256 break_out_target_exprs (tree t)
1257 {
1258   static int target_remap_count;
1259   static splay_tree target_remap;
1260
1261   if (!target_remap_count++)
1262     target_remap = splay_tree_new (splay_tree_compare_pointers,
1263                                    /*splay_tree_delete_key_fn=*/NULL,
1264                                    /*splay_tree_delete_value_fn=*/NULL);
1265   walk_tree (&t, bot_manip, target_remap, NULL);
1266   walk_tree (&t, bot_replace, target_remap, NULL);
1267
1268   if (!--target_remap_count)
1269     {
1270       splay_tree_delete (target_remap);
1271       target_remap = NULL;
1272     }
1273
1274   return t;
1275 }
1276
1277 /* Similar to `build_nt', but for template definitions of dependent
1278    expressions  */
1279
1280 tree
1281 build_min_nt (enum tree_code code, ...)
1282 {
1283   tree t;
1284   int length;
1285   int i;
1286   va_list p;
1287
1288   va_start (p, code);
1289
1290   t = make_node (code);
1291   length = TREE_CODE_LENGTH (code);
1292
1293   for (i = 0; i < length; i++)
1294     {
1295       tree x = va_arg (p, tree);
1296       TREE_OPERAND (t, i) = x;
1297     }
1298
1299   va_end (p);
1300   return t;
1301 }
1302
1303 /* Similar to `build', but for template definitions.  */
1304
1305 tree
1306 build_min (enum tree_code code, tree tt, ...)
1307 {
1308   tree t;
1309   int length;
1310   int i;
1311   va_list p;
1312
1313   va_start (p, tt);
1314
1315   t = make_node (code);
1316   length = TREE_CODE_LENGTH (code);
1317   TREE_TYPE (t) = tt;
1318
1319   for (i = 0; i < length; i++)
1320     {
1321       tree x = va_arg (p, tree);
1322       TREE_OPERAND (t, i) = x;
1323       if (x && !TYPE_P (x) && TREE_SIDE_EFFECTS (x))
1324         TREE_SIDE_EFFECTS (t) = 1;
1325     }
1326
1327   va_end (p);
1328   return t;
1329 }
1330
1331 /* Similar to `build', but for template definitions of non-dependent
1332    expressions. NON_DEP is the non-dependent expression that has been
1333    built.  */
1334
1335 tree
1336 build_min_non_dep (enum tree_code code, tree non_dep, ...)
1337 {
1338   tree t;
1339   int length;
1340   int i;
1341   va_list p;
1342
1343   va_start (p, non_dep);
1344
1345   t = make_node (code);
1346   length = TREE_CODE_LENGTH (code);
1347   TREE_TYPE (t) = TREE_TYPE (non_dep);
1348   TREE_SIDE_EFFECTS (t) = TREE_SIDE_EFFECTS (non_dep);
1349
1350   for (i = 0; i < length; i++)
1351     {
1352       tree x = va_arg (p, tree);
1353       TREE_OPERAND (t, i) = x;
1354     }
1355
1356   if (code == COMPOUND_EXPR && TREE_CODE (non_dep) != COMPOUND_EXPR)
1357     /* This should not be considered a COMPOUND_EXPR, because it
1358        resolves to an overload.  */
1359     COMPOUND_EXPR_OVERLOADED (t) = 1;
1360
1361   va_end (p);
1362   return t;
1363 }
1364
1365 tree
1366 get_type_decl (tree t)
1367 {
1368   if (TREE_CODE (t) == TYPE_DECL)
1369     return t;
1370   if (TYPE_P (t))
1371     return TYPE_STUB_DECL (t);
1372   gcc_assert (t == error_mark_node);
1373   return t;
1374 }
1375
1376 /* Returns the namespace that contains DECL, whether directly or
1377    indirectly.  */
1378
1379 tree
1380 decl_namespace_context (tree decl)
1381 {
1382   while (1)
1383     {
1384       if (TREE_CODE (decl) == NAMESPACE_DECL)
1385         return decl;
1386       else if (TYPE_P (decl))
1387         decl = CP_DECL_CONTEXT (TYPE_MAIN_DECL (decl));
1388       else
1389         decl = CP_DECL_CONTEXT (decl);
1390     }
1391 }
1392
1393 /* Returns true if decl is within an anonymous namespace, however deeply
1394    nested, or false otherwise.  */
1395
1396 bool
1397 decl_anon_ns_mem_p (tree decl)
1398 {
1399   while (1)
1400     {
1401       if (decl == NULL_TREE || decl == error_mark_node)
1402         return false;
1403       if (TREE_CODE (decl) == NAMESPACE_DECL
1404           && DECL_NAME (decl) == NULL_TREE)
1405         return true;
1406       /* Classes and namespaces inside anonymous namespaces have
1407          TREE_PUBLIC == 0, so we can shortcut the search.  */
1408       else if (TYPE_P (decl))
1409         return (TREE_PUBLIC (TYPE_NAME (decl)) == 0);
1410       else if (TREE_CODE (decl) == NAMESPACE_DECL)
1411         return (TREE_PUBLIC (decl) == 0);
1412       else
1413         decl = DECL_CONTEXT (decl);
1414     }
1415 }
1416
1417 /* Return truthvalue of whether T1 is the same tree structure as T2.
1418    Return 1 if they are the same. Return 0 if they are different.  */
1419
1420 bool
1421 cp_tree_equal (tree t1, tree t2)
1422 {
1423   enum tree_code code1, code2;
1424
1425   if (t1 == t2)
1426     return true;
1427   if (!t1 || !t2)
1428     return false;
1429
1430   for (code1 = TREE_CODE (t1);
1431        code1 == NOP_EXPR || code1 == CONVERT_EXPR
1432          || code1 == NON_LVALUE_EXPR;
1433        code1 = TREE_CODE (t1))
1434     t1 = TREE_OPERAND (t1, 0);
1435   for (code2 = TREE_CODE (t2);
1436        code2 == NOP_EXPR || code2 == CONVERT_EXPR
1437          || code1 == NON_LVALUE_EXPR;
1438        code2 = TREE_CODE (t2))
1439     t2 = TREE_OPERAND (t2, 0);
1440
1441   /* They might have become equal now.  */
1442   if (t1 == t2)
1443     return true;
1444
1445   if (code1 != code2)
1446     return false;
1447
1448   switch (code1)
1449     {
1450     case INTEGER_CST:
1451       return TREE_INT_CST_LOW (t1) == TREE_INT_CST_LOW (t2)
1452         && TREE_INT_CST_HIGH (t1) == TREE_INT_CST_HIGH (t2);
1453
1454     case REAL_CST:
1455       return REAL_VALUES_EQUAL (TREE_REAL_CST (t1), TREE_REAL_CST (t2));
1456
1457     case STRING_CST:
1458       return TREE_STRING_LENGTH (t1) == TREE_STRING_LENGTH (t2)
1459         && !memcmp (TREE_STRING_POINTER (t1), TREE_STRING_POINTER (t2),
1460                     TREE_STRING_LENGTH (t1));
1461
1462     case CONSTRUCTOR:
1463       /* We need to do this when determining whether or not two
1464          non-type pointer to member function template arguments
1465          are the same.  */
1466       if (!(same_type_p (TREE_TYPE (t1), TREE_TYPE (t2))
1467             /* The first operand is RTL.  */
1468             && TREE_OPERAND (t1, 0) == TREE_OPERAND (t2, 0)))
1469         return false;
1470       return cp_tree_equal (TREE_OPERAND (t1, 1), TREE_OPERAND (t2, 1));
1471
1472     case TREE_LIST:
1473       if (!cp_tree_equal (TREE_PURPOSE (t1), TREE_PURPOSE (t2)))
1474         return false;
1475       if (!cp_tree_equal (TREE_VALUE (t1), TREE_VALUE (t2)))
1476         return false;
1477       return cp_tree_equal (TREE_CHAIN (t1), TREE_CHAIN (t2));
1478
1479     case SAVE_EXPR:
1480       return cp_tree_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
1481
1482     case CALL_EXPR:
1483       if (!cp_tree_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0)))
1484         return false;
1485       return cp_tree_equal (TREE_OPERAND (t1, 1), TREE_OPERAND (t2, 1));
1486
1487     case TARGET_EXPR:
1488       {
1489         tree o1 = TREE_OPERAND (t1, 0);
1490         tree o2 = TREE_OPERAND (t2, 0);
1491
1492         /* Special case: if either target is an unallocated VAR_DECL,
1493            it means that it's going to be unified with whatever the
1494            TARGET_EXPR is really supposed to initialize, so treat it
1495            as being equivalent to anything.  */
1496         if (TREE_CODE (o1) == VAR_DECL && DECL_NAME (o1) == NULL_TREE
1497             && !DECL_RTL_SET_P (o1))
1498           /*Nop*/;
1499         else if (TREE_CODE (o2) == VAR_DECL && DECL_NAME (o2) == NULL_TREE
1500                  && !DECL_RTL_SET_P (o2))
1501           /*Nop*/;
1502         else if (!cp_tree_equal (o1, o2))
1503           return false;
1504
1505         return cp_tree_equal (TREE_OPERAND (t1, 1), TREE_OPERAND (t2, 1));
1506       }
1507
1508     case WITH_CLEANUP_EXPR:
1509       if (!cp_tree_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0)))
1510         return false;
1511       return cp_tree_equal (TREE_OPERAND (t1, 1), TREE_OPERAND (t1, 1));
1512
1513     case COMPONENT_REF:
1514       if (TREE_OPERAND (t1, 1) != TREE_OPERAND (t2, 1))
1515         return false;
1516       return cp_tree_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
1517
1518     case VAR_DECL:
1519     case PARM_DECL:
1520     case CONST_DECL:
1521     case FUNCTION_DECL:
1522     case TEMPLATE_DECL:
1523     case IDENTIFIER_NODE:
1524     case SSA_NAME:
1525       return false;
1526
1527     case BASELINK:
1528       return (BASELINK_BINFO (t1) == BASELINK_BINFO (t2)
1529               && BASELINK_ACCESS_BINFO (t1) == BASELINK_ACCESS_BINFO (t2)
1530               && cp_tree_equal (BASELINK_FUNCTIONS (t1),
1531                                 BASELINK_FUNCTIONS (t2)));
1532
1533     case TEMPLATE_PARM_INDEX:
1534       return (TEMPLATE_PARM_IDX (t1) == TEMPLATE_PARM_IDX (t2)
1535               && TEMPLATE_PARM_LEVEL (t1) == TEMPLATE_PARM_LEVEL (t2)
1536               && same_type_p (TREE_TYPE (TEMPLATE_PARM_DECL (t1)),
1537                               TREE_TYPE (TEMPLATE_PARM_DECL (t2))));
1538
1539     case TEMPLATE_ID_EXPR:
1540       {
1541         unsigned ix;
1542         tree vec1, vec2;
1543
1544         if (!cp_tree_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0)))
1545           return false;
1546         vec1 = TREE_OPERAND (t1, 1);
1547         vec2 = TREE_OPERAND (t2, 1);
1548
1549         if (!vec1 || !vec2)
1550           return !vec1 && !vec2;
1551
1552         if (TREE_VEC_LENGTH (vec1) != TREE_VEC_LENGTH (vec2))
1553           return false;
1554
1555         for (ix = TREE_VEC_LENGTH (vec1); ix--;)
1556           if (!cp_tree_equal (TREE_VEC_ELT (vec1, ix),
1557                               TREE_VEC_ELT (vec2, ix)))
1558             return false;
1559
1560         return true;
1561       }
1562
1563     case SIZEOF_EXPR:
1564     case ALIGNOF_EXPR:
1565       {
1566         tree o1 = TREE_OPERAND (t1, 0);
1567         tree o2 = TREE_OPERAND (t2, 0);
1568
1569         if (TREE_CODE (o1) != TREE_CODE (o2))
1570           return false;
1571         if (TYPE_P (o1))
1572           return same_type_p (o1, o2);
1573         else
1574           return cp_tree_equal (o1, o2);
1575       }
1576
1577     case PTRMEM_CST:
1578       /* Two pointer-to-members are the same if they point to the same
1579          field or function in the same class.  */
1580       if (PTRMEM_CST_MEMBER (t1) != PTRMEM_CST_MEMBER (t2))
1581         return false;
1582
1583       return same_type_p (PTRMEM_CST_CLASS (t1), PTRMEM_CST_CLASS (t2));
1584
1585     case OVERLOAD:
1586       if (OVL_FUNCTION (t1) != OVL_FUNCTION (t2))
1587         return false;
1588       return cp_tree_equal (OVL_CHAIN (t1), OVL_CHAIN (t2));
1589
1590     default:
1591       break;
1592     }
1593
1594   switch (TREE_CODE_CLASS (code1))
1595     {
1596     case tcc_unary:
1597     case tcc_binary:
1598     case tcc_comparison:
1599     case tcc_expression:
1600     case tcc_reference:
1601     case tcc_statement:
1602       {
1603         int i;
1604
1605         for (i = 0; i < TREE_CODE_LENGTH (code1); ++i)
1606           if (!cp_tree_equal (TREE_OPERAND (t1, i), TREE_OPERAND (t2, i)))
1607             return false;
1608
1609         return true;
1610       }
1611
1612     case tcc_type:
1613       return same_type_p (t1, t2);
1614     default:
1615       gcc_unreachable ();
1616     }
1617   /* We can get here with --disable-checking.  */
1618   return false;
1619 }
1620
1621 /* The type of ARG when used as an lvalue.  */
1622
1623 tree
1624 lvalue_type (tree arg)
1625 {
1626   tree type = TREE_TYPE (arg);
1627   return type;
1628 }
1629
1630 /* The type of ARG for printing error messages; denote lvalues with
1631    reference types.  */
1632
1633 tree
1634 error_type (tree arg)
1635 {
1636   tree type = TREE_TYPE (arg);
1637
1638   if (TREE_CODE (type) == ARRAY_TYPE)
1639     ;
1640   else if (TREE_CODE (type) == ERROR_MARK)
1641     ;
1642   else if (real_lvalue_p (arg))
1643     type = build_reference_type (lvalue_type (arg));
1644   else if (IS_AGGR_TYPE (type))
1645     type = lvalue_type (arg);
1646
1647   return type;
1648 }
1649
1650 /* Does FUNCTION use a variable-length argument list?  */
1651
1652 int
1653 varargs_function_p (tree function)
1654 {
1655   tree parm = TYPE_ARG_TYPES (TREE_TYPE (function));
1656   for (; parm; parm = TREE_CHAIN (parm))
1657     if (TREE_VALUE (parm) == void_type_node)
1658       return 0;
1659   return 1;
1660 }
1661
1662 /* Returns 1 if decl is a member of a class.  */
1663
1664 int
1665 member_p (tree decl)
1666 {
1667   const tree ctx = DECL_CONTEXT (decl);
1668   return (ctx && TYPE_P (ctx));
1669 }
1670
1671 /* Create a placeholder for member access where we don't actually have an
1672    object that the access is against.  */
1673
1674 tree
1675 build_dummy_object (tree type)
1676 {
1677   tree decl = build1 (NOP_EXPR, build_pointer_type (type), void_zero_node);
1678   return build_indirect_ref (decl, NULL);
1679 }
1680
1681 /* We've gotten a reference to a member of TYPE.  Return *this if appropriate,
1682    or a dummy object otherwise.  If BINFOP is non-0, it is filled with the
1683    binfo path from current_class_type to TYPE, or 0.  */
1684
1685 tree
1686 maybe_dummy_object (tree type, tree* binfop)
1687 {
1688   tree decl, context;
1689   tree binfo;
1690
1691   if (current_class_type
1692       && (binfo = lookup_base (current_class_type, type,
1693                                ba_unique | ba_quiet, NULL)))
1694     context = current_class_type;
1695   else
1696     {
1697       /* Reference from a nested class member function.  */
1698       context = type;
1699       binfo = TYPE_BINFO (type);
1700     }
1701
1702   if (binfop)
1703     *binfop = binfo;
1704
1705   if (current_class_ref && context == current_class_type
1706       /* Kludge: Make sure that current_class_type is actually
1707          correct.  It might not be if we're in the middle of
1708          tsubst_default_argument.  */
1709       && same_type_p (TYPE_MAIN_VARIANT (TREE_TYPE (current_class_ref)),
1710                       current_class_type))
1711     decl = current_class_ref;
1712   else
1713     decl = build_dummy_object (context);
1714
1715   return decl;
1716 }
1717
1718 /* Returns 1 if OB is a placeholder object, or a pointer to one.  */
1719
1720 int
1721 is_dummy_object (tree ob)
1722 {
1723   if (TREE_CODE (ob) == INDIRECT_REF)
1724     ob = TREE_OPERAND (ob, 0);
1725   return (TREE_CODE (ob) == NOP_EXPR
1726           && TREE_OPERAND (ob, 0) == void_zero_node);
1727 }
1728
1729 /* Returns 1 iff type T is a POD type, as defined in [basic.types].  */
1730
1731 int
1732 pod_type_p (tree t)
1733 {
1734   t = strip_array_types (t);
1735
1736   if (t == error_mark_node)
1737     return 1;
1738   if (INTEGRAL_TYPE_P (t))
1739     return 1;  /* integral, character or enumeral type */
1740   if (FLOAT_TYPE_P (t))
1741     return 1;
1742   if (TYPE_PTR_P (t))
1743     return 1; /* pointer to non-member */
1744   if (TYPE_PTR_TO_MEMBER_P (t))
1745     return 1; /* pointer to member */
1746
1747   if (TREE_CODE (t) == VECTOR_TYPE)
1748     return 1; /* vectors are (small) arrays of scalars */
1749
1750   if (! CLASS_TYPE_P (t))
1751     return 0; /* other non-class type (reference or function) */
1752   if (CLASSTYPE_NON_POD_P (t))
1753     return 0;
1754   return 1;
1755 }
1756
1757 /* Returns 1 iff zero initialization of type T means actually storing
1758    zeros in it.  */
1759
1760 int
1761 zero_init_p (tree t)
1762 {
1763   t = strip_array_types (t);
1764
1765   if (t == error_mark_node)
1766     return 1;
1767
1768   /* NULL pointers to data members are initialized with -1.  */
1769   if (TYPE_PTRMEM_P (t))
1770     return 0;
1771
1772   /* Classes that contain types that can't be zero-initialized, cannot
1773      be zero-initialized themselves.  */
1774   if (CLASS_TYPE_P (t) && CLASSTYPE_NON_ZERO_INIT_P (t))
1775     return 0;
1776
1777   return 1;
1778 }
1779
1780 /* Table of valid C++ attributes.  */
1781 const struct attribute_spec cxx_attribute_table[] =
1782 {
1783   /* { name, min_len, max_len, decl_req, type_req, fn_type_req, handler } */
1784   { "java_interface", 0, 0, false, false, false, handle_java_interface_attribute },
1785   { "com_interface",  0, 0, false, false, false, handle_com_interface_attribute },
1786   { "init_priority",  1, 1, true,  false, false, handle_init_priority_attribute },
1787   { NULL,             0, 0, false, false, false, NULL }
1788 };
1789
1790 /* Handle a "java_interface" attribute; arguments as in
1791    struct attribute_spec.handler.  */
1792 static tree
1793 handle_java_interface_attribute (tree* node,
1794                                  tree name,
1795                                  tree args ATTRIBUTE_UNUSED ,
1796                                  int flags,
1797                                  bool* no_add_attrs)
1798 {
1799   if (DECL_P (*node)
1800       || !CLASS_TYPE_P (*node)
1801       || !TYPE_FOR_JAVA (*node))
1802     {
1803       error ("%qE attribute can only be applied to Java class definitions",
1804              name);
1805       *no_add_attrs = true;
1806       return NULL_TREE;
1807     }
1808   if (!(flags & (int) ATTR_FLAG_TYPE_IN_PLACE))
1809     *node = build_variant_type_copy (*node);
1810   TYPE_JAVA_INTERFACE (*node) = 1;
1811
1812   return NULL_TREE;
1813 }
1814
1815 /* Handle a "com_interface" attribute; arguments as in
1816    struct attribute_spec.handler.  */
1817 static tree
1818 handle_com_interface_attribute (tree* node,
1819                                 tree name,
1820                                 tree args ATTRIBUTE_UNUSED ,
1821                                 int flags ATTRIBUTE_UNUSED ,
1822                                 bool* no_add_attrs)
1823 {
1824   static int warned;
1825
1826   *no_add_attrs = true;
1827
1828   if (DECL_P (*node)
1829       || !CLASS_TYPE_P (*node)
1830       || *node != TYPE_MAIN_VARIANT (*node))
1831     {
1832       warning (OPT_Wattributes, "%qE attribute can only be applied "
1833                "to class definitions", name);
1834       return NULL_TREE;
1835     }
1836
1837   if (!warned++)
1838     warning (0, "%qE is obsolete; g++ vtables are now COM-compatible by default",
1839              name);
1840
1841   return NULL_TREE;
1842 }
1843
1844 /* Handle an "init_priority" attribute; arguments as in
1845    struct attribute_spec.handler.  */
1846 static tree
1847 handle_init_priority_attribute (tree* node,
1848                                 tree name,
1849                                 tree args,
1850                                 int flags ATTRIBUTE_UNUSED ,
1851                                 bool* no_add_attrs)
1852 {
1853   tree initp_expr = TREE_VALUE (args);
1854   tree decl = *node;
1855   tree type = TREE_TYPE (decl);
1856   int pri;
1857
1858   STRIP_NOPS (initp_expr);
1859
1860   if (!initp_expr || TREE_CODE (initp_expr) != INTEGER_CST)
1861     {
1862       error ("requested init_priority is not an integer constant");
1863       *no_add_attrs = true;
1864       return NULL_TREE;
1865     }
1866
1867   pri = TREE_INT_CST_LOW (initp_expr);
1868
1869   type = strip_array_types (type);
1870
1871   if (decl == NULL_TREE
1872       || TREE_CODE (decl) != VAR_DECL
1873       || !TREE_STATIC (decl)
1874       || DECL_EXTERNAL (decl)
1875       || (TREE_CODE (type) != RECORD_TYPE
1876           && TREE_CODE (type) != UNION_TYPE)
1877       /* Static objects in functions are initialized the
1878          first time control passes through that
1879          function. This is not precise enough to pin down an
1880          init_priority value, so don't allow it.  */
1881       || current_function_decl)
1882     {
1883       error ("can only use %qE attribute on file-scope definitions "
1884              "of objects of class type", name);
1885       *no_add_attrs = true;
1886       return NULL_TREE;
1887     }
1888
1889   if (pri > MAX_INIT_PRIORITY || pri <= 0)
1890     {
1891       error ("requested init_priority is out of range");
1892       *no_add_attrs = true;
1893       return NULL_TREE;
1894     }
1895
1896   /* Check for init_priorities that are reserved for
1897      language and runtime support implementations.*/
1898   if (pri <= MAX_RESERVED_INIT_PRIORITY)
1899     {
1900       warning
1901         (0, "requested init_priority is reserved for internal use");
1902     }
1903
1904   if (SUPPORTS_INIT_PRIORITY)
1905     {
1906       SET_DECL_INIT_PRIORITY (decl, pri);
1907       DECL_HAS_INIT_PRIORITY_P (decl) = 1;
1908       return NULL_TREE;
1909     }
1910   else
1911     {
1912       error ("%qE attribute is not supported on this platform", name);
1913       *no_add_attrs = true;
1914       return NULL_TREE;
1915     }
1916 }
1917
1918 /* Return a new PTRMEM_CST of the indicated TYPE.  The MEMBER is the
1919    thing pointed to by the constant.  */
1920
1921 tree
1922 make_ptrmem_cst (tree type, tree member)
1923 {
1924   tree ptrmem_cst = make_node (PTRMEM_CST);
1925   TREE_TYPE (ptrmem_cst) = type;
1926   PTRMEM_CST_MEMBER (ptrmem_cst) = member;
1927   return ptrmem_cst;
1928 }
1929
1930 /* Build a variant of TYPE that has the indicated ATTRIBUTES.  May
1931    return an existing type of an appropriate type already exists.  */
1932
1933 tree
1934 cp_build_type_attribute_variant (tree type, tree attributes)
1935 {
1936   tree new_type;
1937
1938   new_type = build_type_attribute_variant (type, attributes);
1939   if (TREE_CODE (new_type) == FUNCTION_TYPE
1940       && (TYPE_RAISES_EXCEPTIONS (new_type)
1941           != TYPE_RAISES_EXCEPTIONS (type)))
1942     new_type = build_exception_variant (new_type,
1943                                         TYPE_RAISES_EXCEPTIONS (type));
1944
1945   /* Making a new main variant of a class type is broken.  */
1946   gcc_assert (!CLASS_TYPE_P (type) || new_type == type);
1947     
1948   return new_type;
1949 }
1950
1951 /* Apply FUNC to all language-specific sub-trees of TP in a pre-order
1952    traversal.  Called from walk_tree.  */
1953
1954 tree
1955 cp_walk_subtrees (tree *tp, int *walk_subtrees_p, walk_tree_fn func,
1956                   void *data, struct pointer_set_t *pset)
1957 {
1958   enum tree_code code = TREE_CODE (*tp);
1959   location_t save_locus;
1960   tree result;
1961
1962 #define WALK_SUBTREE(NODE)                              \
1963   do                                                    \
1964     {                                                   \
1965       result = walk_tree (&(NODE), func, data, pset);   \
1966       if (result) goto out;                             \
1967     }                                                   \
1968   while (0)
1969
1970   /* Set input_location here so we get the right instantiation context
1971      if we call instantiate_decl from inlinable_function_p.  */
1972   save_locus = input_location;
1973   if (EXPR_HAS_LOCATION (*tp))
1974     input_location = EXPR_LOCATION (*tp);
1975
1976   /* Not one of the easy cases.  We must explicitly go through the
1977      children.  */
1978   result = NULL_TREE;
1979   switch (code)
1980     {
1981     case DEFAULT_ARG:
1982     case TEMPLATE_TEMPLATE_PARM:
1983     case BOUND_TEMPLATE_TEMPLATE_PARM:
1984     case UNBOUND_CLASS_TEMPLATE:
1985     case TEMPLATE_PARM_INDEX:
1986     case TEMPLATE_TYPE_PARM:
1987     case TYPENAME_TYPE:
1988     case TYPEOF_TYPE:
1989     case BASELINK:
1990       /* None of these have subtrees other than those already walked
1991          above.  */
1992       *walk_subtrees_p = 0;
1993       break;
1994
1995     case TINST_LEVEL:
1996       WALK_SUBTREE (TINST_DECL (*tp));
1997       *walk_subtrees_p = 0;
1998       break;
1999
2000     case PTRMEM_CST:
2001       WALK_SUBTREE (TREE_TYPE (*tp));
2002       *walk_subtrees_p = 0;
2003       break;
2004
2005     case TREE_LIST:
2006       WALK_SUBTREE (TREE_PURPOSE (*tp));
2007       break;
2008
2009     case OVERLOAD:
2010       WALK_SUBTREE (OVL_FUNCTION (*tp));
2011       WALK_SUBTREE (OVL_CHAIN (*tp));
2012       *walk_subtrees_p = 0;
2013       break;
2014
2015     case RECORD_TYPE:
2016       if (TYPE_PTRMEMFUNC_P (*tp))
2017         WALK_SUBTREE (TYPE_PTRMEMFUNC_FN_TYPE (*tp));
2018       break;
2019
2020     default:
2021       input_location = save_locus;
2022       return NULL_TREE;
2023     }
2024
2025   /* We didn't find what we were looking for.  */
2026  out:
2027   input_location = save_locus;
2028   return result;
2029
2030 #undef WALK_SUBTREE
2031 }
2032
2033 /* Decide whether there are language-specific reasons to not inline a
2034    function as a tree.  */
2035
2036 int
2037 cp_cannot_inline_tree_fn (tree* fnp)
2038 {
2039   tree fn = *fnp;
2040
2041   /* We can inline a template instantiation only if it's fully
2042      instantiated.  */
2043   if (DECL_TEMPLATE_INFO (fn)
2044       && TI_PENDING_TEMPLATE_FLAG (DECL_TEMPLATE_INFO (fn)))
2045     {
2046       /* Don't instantiate functions that are not going to be
2047          inlined.  */
2048       if (!DECL_INLINE (DECL_TEMPLATE_RESULT
2049                         (template_for_substitution (fn))))
2050         return 1;
2051
2052       fn = *fnp = instantiate_decl (fn, /*defer_ok=*/0, /*undefined_ok=*/0);
2053
2054       if (TI_PENDING_TEMPLATE_FLAG (DECL_TEMPLATE_INFO (fn)))
2055         return 1;
2056     }
2057
2058   if (flag_really_no_inline
2059       && lookup_attribute ("always_inline", DECL_ATTRIBUTES (fn)) == NULL)
2060     return 1;
2061
2062   /* Don't auto-inline anything that might not be bound within
2063      this unit of translation.
2064      Exclude comdat functions from this rule.  While they can be bound
2065      to the other unit, they all must be the same.  This is especially
2066      important so templates can inline.  */
2067   if (!DECL_DECLARED_INLINE_P (fn) && !(*targetm.binds_local_p) (fn)
2068       && !DECL_COMDAT (fn))
2069     {
2070       DECL_UNINLINABLE (fn) = 1;
2071       return 1;
2072     }
2073
2074   if (varargs_function_p (fn))
2075     {
2076       DECL_UNINLINABLE (fn) = 1;
2077       return 1;
2078     }
2079
2080   if (! function_attribute_inlinable_p (fn))
2081     {
2082       DECL_UNINLINABLE (fn) = 1;
2083       return 1;
2084     }
2085
2086   return 0;
2087 }
2088
2089 /* Add any pending functions other than the current function (already
2090    handled by the caller), that thus cannot be inlined, to FNS_P, then
2091    return the latest function added to the array, PREV_FN.  */
2092
2093 tree
2094 cp_add_pending_fn_decls (void* fns_p, tree prev_fn)
2095 {
2096   varray_type *fnsp = (varray_type *)fns_p;
2097   struct saved_scope *s;
2098
2099   for (s = scope_chain; s; s = s->prev)
2100     if (s->function_decl && s->function_decl != prev_fn)
2101       {
2102         VARRAY_PUSH_TREE (*fnsp, s->function_decl);
2103         prev_fn = s->function_decl;
2104       }
2105
2106   return prev_fn;
2107 }
2108
2109 /* Determine whether VAR is a declaration of an automatic variable in
2110    function FN.  */
2111
2112 int
2113 cp_auto_var_in_fn_p (tree var, tree fn)
2114 {
2115   return (DECL_P (var) && DECL_CONTEXT (var) == fn
2116           && nonstatic_local_decl_p (var));
2117 }
2118
2119 /* Like save_expr, but for C++.  */
2120
2121 tree
2122 cp_save_expr (tree expr)
2123 {
2124   /* There is no reason to create a SAVE_EXPR within a template; if
2125      needed, we can create the SAVE_EXPR when instantiating the
2126      template.  Furthermore, the middle-end cannot handle C++-specific
2127      tree codes.  */
2128   if (processing_template_decl)
2129     return expr;
2130   return save_expr (expr);
2131 }
2132
2133 /* Initialize tree.c.  */
2134
2135 void
2136 init_tree (void)
2137 {
2138   list_hash_table = htab_create_ggc (31, list_hash, list_hash_eq, NULL);
2139 }
2140
2141 /* Returns the kind of special function that DECL (a FUNCTION_DECL)
2142    is.  Note that sfk_none is zero, so this function can be used as a
2143    predicate to test whether or not DECL is a special function.  */
2144
2145 special_function_kind
2146 special_function_p (tree decl)
2147 {
2148   /* Rather than doing all this stuff with magic names, we should
2149      probably have a field of type `special_function_kind' in
2150      DECL_LANG_SPECIFIC.  */
2151   if (DECL_COPY_CONSTRUCTOR_P (decl))
2152     return sfk_copy_constructor;
2153   if (DECL_CONSTRUCTOR_P (decl))
2154     return sfk_constructor;
2155   if (DECL_OVERLOADED_OPERATOR_P (decl) == NOP_EXPR)
2156     return sfk_assignment_operator;
2157   if (DECL_MAYBE_IN_CHARGE_DESTRUCTOR_P (decl))
2158     return sfk_destructor;
2159   if (DECL_COMPLETE_DESTRUCTOR_P (decl))
2160     return sfk_complete_destructor;
2161   if (DECL_BASE_DESTRUCTOR_P (decl))
2162     return sfk_base_destructor;
2163   if (DECL_DELETING_DESTRUCTOR_P (decl))
2164     return sfk_deleting_destructor;
2165   if (DECL_CONV_FN_P (decl))
2166     return sfk_conversion;
2167
2168   return sfk_none;
2169 }
2170
2171 /* Returns nonzero if TYPE is a character type, including wchar_t.  */
2172
2173 int
2174 char_type_p (tree type)
2175 {
2176   return (same_type_p (type, char_type_node)
2177           || same_type_p (type, unsigned_char_type_node)
2178           || same_type_p (type, signed_char_type_node)
2179           || same_type_p (type, wchar_type_node));
2180 }
2181
2182 /* Returns the kind of linkage associated with the indicated DECL.  Th
2183    value returned is as specified by the language standard; it is
2184    independent of implementation details regarding template
2185    instantiation, etc.  For example, it is possible that a declaration
2186    to which this function assigns external linkage would not show up
2187    as a global symbol when you run `nm' on the resulting object file.  */
2188
2189 linkage_kind
2190 decl_linkage (tree decl)
2191 {
2192   /* This function doesn't attempt to calculate the linkage from first
2193      principles as given in [basic.link].  Instead, it makes use of
2194      the fact that we have already set TREE_PUBLIC appropriately, and
2195      then handles a few special cases.  Ideally, we would calculate
2196      linkage first, and then transform that into a concrete
2197      implementation.  */
2198
2199   /* Things that don't have names have no linkage.  */
2200   if (!DECL_NAME (decl))
2201     return lk_none;
2202
2203   /* Things that are TREE_PUBLIC have external linkage.  */
2204   if (TREE_PUBLIC (decl))
2205     return lk_external;
2206
2207   if (TREE_CODE (decl) == NAMESPACE_DECL)
2208     return lk_external;
2209
2210   /* Linkage of a CONST_DECL depends on the linkage of the enumeration
2211      type.  */
2212   if (TREE_CODE (decl) == CONST_DECL)
2213     return decl_linkage (TYPE_NAME (TREE_TYPE (decl)));
2214
2215   /* Some things that are not TREE_PUBLIC have external linkage, too.
2216      For example, on targets that don't have weak symbols, we make all
2217      template instantiations have internal linkage (in the object
2218      file), but the symbols should still be treated as having external
2219      linkage from the point of view of the language.  */
2220   if (TREE_CODE (decl) != TYPE_DECL && DECL_LANG_SPECIFIC (decl)
2221       && DECL_COMDAT (decl))
2222     return lk_external;
2223
2224   /* Things in local scope do not have linkage, if they don't have
2225      TREE_PUBLIC set.  */
2226   if (decl_function_context (decl))
2227     return lk_none;
2228
2229   /* Members of the anonymous namespace also have TREE_PUBLIC unset, but
2230      are considered to have external linkage for language purposes.  DECLs
2231      really meant to have internal linkage have DECL_THIS_STATIC set.  */
2232   if (TREE_CODE (decl) == TYPE_DECL
2233       || ((TREE_CODE (decl) == VAR_DECL || TREE_CODE (decl) == FUNCTION_DECL)
2234           && !DECL_THIS_STATIC (decl)))
2235     return lk_external;
2236
2237   /* Everything else has internal linkage.  */
2238   return lk_internal;
2239 }
2240 \f
2241 /* EXP is an expression that we want to pre-evaluate.  Returns (in
2242    *INITP) an expression that will perform the pre-evaluation.  The
2243    value returned by this function is a side-effect free expression
2244    equivalent to the pre-evaluated expression.  Callers must ensure
2245    that *INITP is evaluated before EXP.  */
2246
2247 tree
2248 stabilize_expr (tree exp, tree* initp)
2249 {
2250   tree init_expr;
2251
2252   if (!TREE_SIDE_EFFECTS (exp))
2253     init_expr = NULL_TREE;
2254   else if (!real_lvalue_p (exp)
2255            || !TYPE_NEEDS_CONSTRUCTING (TREE_TYPE (exp)))
2256     {
2257       init_expr = get_target_expr (exp);
2258       exp = TARGET_EXPR_SLOT (init_expr);
2259     }
2260   else
2261     {
2262       exp = build_unary_op (ADDR_EXPR, exp, 1);
2263       init_expr = get_target_expr (exp);
2264       exp = TARGET_EXPR_SLOT (init_expr);
2265       exp = build_indirect_ref (exp, 0);
2266     }
2267   *initp = init_expr;
2268
2269   gcc_assert (!TREE_SIDE_EFFECTS (exp));
2270   return exp;
2271 }
2272
2273 /* Add NEW, an expression whose value we don't care about, after the
2274    similar expression ORIG.  */
2275
2276 tree
2277 add_stmt_to_compound (tree orig, tree new)
2278 {
2279   if (!new || !TREE_SIDE_EFFECTS (new))
2280     return orig;
2281   if (!orig || !TREE_SIDE_EFFECTS (orig))
2282     return new;
2283   return build2 (COMPOUND_EXPR, void_type_node, orig, new);
2284 }
2285
2286 /* Like stabilize_expr, but for a call whose arguments we want to
2287    pre-evaluate.  CALL is modified in place to use the pre-evaluated
2288    arguments, while, upon return, *INITP contains an expression to
2289    compute the arguments.  */
2290
2291 void
2292 stabilize_call (tree call, tree *initp)
2293 {
2294   tree inits = NULL_TREE;
2295   tree t;
2296
2297   if (call == error_mark_node)
2298     return;
2299
2300   gcc_assert (TREE_CODE (call) == CALL_EXPR
2301               || TREE_CODE (call) == AGGR_INIT_EXPR);
2302
2303   for (t = TREE_OPERAND (call, 1); t; t = TREE_CHAIN (t))
2304     if (TREE_SIDE_EFFECTS (TREE_VALUE (t)))
2305       {
2306         tree init;
2307         TREE_VALUE (t) = stabilize_expr (TREE_VALUE (t), &init);
2308         inits = add_stmt_to_compound (inits, init);
2309       }
2310
2311   *initp = inits;
2312 }
2313
2314 /* Like stabilize_expr, but for an initialization.  
2315
2316    If the initialization is for an object of class type, this function
2317    takes care not to introduce additional temporaries.
2318
2319    Returns TRUE iff the expression was successfully pre-evaluated,
2320    i.e., if INIT is now side-effect free, except for, possible, a
2321    single call to a constructor.  */
2322
2323 bool
2324 stabilize_init (tree init, tree *initp)
2325 {
2326   tree t = init;
2327
2328   *initp = NULL_TREE;
2329
2330   if (t == error_mark_node)
2331     return true;
2332
2333   if (TREE_CODE (t) == INIT_EXPR
2334       && TREE_CODE (TREE_OPERAND (t, 1)) != TARGET_EXPR)
2335     {
2336       TREE_OPERAND (t, 1) = stabilize_expr (TREE_OPERAND (t, 1), initp);
2337       return true;
2338     }
2339
2340   if (TREE_CODE (t) == INIT_EXPR)
2341     t = TREE_OPERAND (t, 1);
2342   if (TREE_CODE (t) == TARGET_EXPR)
2343     t = TARGET_EXPR_INITIAL (t);
2344   if (TREE_CODE (t) == COMPOUND_EXPR)
2345     t = expr_last (t);
2346   if (TREE_CODE (t) == CONSTRUCTOR
2347       && EMPTY_CONSTRUCTOR_P (t))
2348     /* Default-initialization.  */
2349     return true;
2350
2351   /* If the initializer is a COND_EXPR, we can't preevaluate
2352      anything.  */
2353   if (TREE_CODE (t) == COND_EXPR)
2354     return false;
2355
2356   if (TREE_CODE (t) == CALL_EXPR
2357       || TREE_CODE (t) == AGGR_INIT_EXPR)
2358     {
2359       stabilize_call (t, initp);
2360       return true;
2361     }
2362
2363   /* The initialization is being performed via a bitwise copy -- and
2364      the item copied may have side effects.  */
2365   return TREE_SIDE_EFFECTS (init);
2366 }
2367
2368 /* Like "fold", but should be used whenever we might be processing the
2369    body of a template.  */
2370
2371 tree
2372 fold_if_not_in_template (tree expr)
2373 {
2374   /* In the body of a template, there is never any need to call
2375      "fold".  We will call fold later when actually instantiating the
2376      template.  Integral constant expressions in templates will be
2377      evaluated via fold_non_dependent_expr, as necessary.  */
2378   if (processing_template_decl)
2379     return expr;
2380
2381   /* Fold C++ front-end specific tree codes.  */
2382   if (TREE_CODE (expr) == UNARY_PLUS_EXPR)
2383     return fold_convert (TREE_TYPE (expr), TREE_OPERAND (expr, 0));
2384
2385   return fold (expr);
2386 }
2387
2388 /* Returns true if a cast to TYPE may appear in an integral constant
2389    expression.  */
2390
2391 bool
2392 cast_valid_in_integral_constant_expression_p (tree type)
2393 {
2394   return (INTEGRAL_OR_ENUMERATION_TYPE_P (type)
2395           || dependent_type_p (type)
2396           || type == error_mark_node);
2397 }
2398
2399 \f
2400 #if defined ENABLE_TREE_CHECKING && (GCC_VERSION >= 2007)
2401 /* Complain that some language-specific thing hanging off a tree
2402    node has been accessed improperly.  */
2403
2404 void
2405 lang_check_failed (const char* file, int line, const char* function)
2406 {
2407   internal_error ("lang_* check: failed in %s, at %s:%d",
2408                   function, trim_filename (file), line);
2409 }
2410 #endif /* ENABLE_TREE_CHECKING */
2411
2412 #include "gt-cp-tree.h"