OSDN Git Service

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