OSDN Git Service

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