OSDN Git Service

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