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