OSDN Git Service

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