OSDN Git Service

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