OSDN Git Service

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