OSDN Git Service

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