OSDN Git Service

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