OSDN Git Service

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