OSDN Git Service

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