OSDN Git Service

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