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 CONSTRAINT_INFO:
2914       return cp_tree_equal (CI_ASSOCIATED_CONSTRAINTS (t1),
2915                             CI_ASSOCIATED_CONSTRAINTS (t2));
2916
2917     case TREE_VEC:
2918       {
2919         unsigned ix;
2920         if (TREE_VEC_LENGTH (t1) != TREE_VEC_LENGTH (t2))
2921           return false;
2922         for (ix = TREE_VEC_LENGTH (t1); ix--;)
2923           if (!cp_tree_equal (TREE_VEC_ELT (t1, ix),
2924                               TREE_VEC_ELT (t2, ix)))
2925             return false;
2926         return true;
2927       }
2928
2929     case SIZEOF_EXPR:
2930     case ALIGNOF_EXPR:
2931       {
2932         tree o1 = TREE_OPERAND (t1, 0);
2933         tree o2 = TREE_OPERAND (t2, 0);
2934
2935         if (code1 == SIZEOF_EXPR)
2936           {
2937             if (SIZEOF_EXPR_TYPE_P (t1))
2938               o1 = TREE_TYPE (o1);
2939             if (SIZEOF_EXPR_TYPE_P (t2))
2940               o2 = TREE_TYPE (o2);
2941           }
2942         if (TREE_CODE (o1) != TREE_CODE (o2))
2943           return false;
2944         if (TYPE_P (o1))
2945           return same_type_p (o1, o2);
2946         else
2947           return cp_tree_equal (o1, o2);
2948       }
2949
2950     case MODOP_EXPR:
2951       {
2952         tree t1_op1, t2_op1;
2953
2954         if (!cp_tree_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0)))
2955           return false;
2956
2957         t1_op1 = TREE_OPERAND (t1, 1);
2958         t2_op1 = TREE_OPERAND (t2, 1);
2959         if (TREE_CODE (t1_op1) != TREE_CODE (t2_op1))
2960           return false;
2961
2962         return cp_tree_equal (TREE_OPERAND (t1, 2), TREE_OPERAND (t2, 2));
2963       }
2964
2965     case PTRMEM_CST:
2966       /* Two pointer-to-members are the same if they point to the same
2967          field or function in the same class.  */
2968       if (PTRMEM_CST_MEMBER (t1) != PTRMEM_CST_MEMBER (t2))
2969         return false;
2970
2971       return same_type_p (PTRMEM_CST_CLASS (t1), PTRMEM_CST_CLASS (t2));
2972
2973     case OVERLOAD:
2974       if (OVL_FUNCTION (t1) != OVL_FUNCTION (t2))
2975         return false;
2976       return cp_tree_equal (OVL_CHAIN (t1), OVL_CHAIN (t2));
2977
2978     case TRAIT_EXPR:
2979       if (TRAIT_EXPR_KIND (t1) != TRAIT_EXPR_KIND (t2))
2980         return false;
2981       return same_type_p (TRAIT_EXPR_TYPE1 (t1), TRAIT_EXPR_TYPE1 (t2))
2982         && cp_tree_equal (TRAIT_EXPR_TYPE2 (t1), TRAIT_EXPR_TYPE2 (t2));
2983
2984     case CAST_EXPR:
2985     case STATIC_CAST_EXPR:
2986     case REINTERPRET_CAST_EXPR:
2987     case CONST_CAST_EXPR:
2988     case DYNAMIC_CAST_EXPR:
2989     case IMPLICIT_CONV_EXPR:
2990     case NEW_EXPR:
2991     CASE_CONVERT:
2992     case NON_LVALUE_EXPR:
2993     case VIEW_CONVERT_EXPR:
2994       if (!same_type_p (TREE_TYPE (t1), TREE_TYPE (t2)))
2995         return false;
2996       /* Now compare operands as usual.  */
2997       break;
2998
2999     case DEFERRED_NOEXCEPT:
3000       return (cp_tree_equal (DEFERRED_NOEXCEPT_PATTERN (t1),
3001                              DEFERRED_NOEXCEPT_PATTERN (t2))
3002               && comp_template_args (DEFERRED_NOEXCEPT_ARGS (t1),
3003                                      DEFERRED_NOEXCEPT_ARGS (t2)));
3004       break;
3005
3006     default:
3007       break;
3008     }
3009
3010   switch (TREE_CODE_CLASS (code1))
3011     {
3012     case tcc_unary:
3013     case tcc_binary:
3014     case tcc_comparison:
3015     case tcc_expression:
3016     case tcc_vl_exp:
3017     case tcc_reference:
3018     case tcc_statement:
3019       {
3020         int i, n;
3021
3022         n = cp_tree_operand_length (t1);
3023         if (TREE_CODE_CLASS (code1) == tcc_vl_exp
3024             && n != TREE_OPERAND_LENGTH (t2))
3025           return false;
3026
3027         for (i = 0; i < n; ++i)
3028           if (!cp_tree_equal (TREE_OPERAND (t1, i), TREE_OPERAND (t2, i)))
3029             return false;
3030
3031         return true;
3032       }
3033
3034     case tcc_type:
3035       return same_type_p (t1, t2);
3036     default:
3037       gcc_unreachable ();
3038     }
3039   /* We can get here with --disable-checking.  */
3040   return false;
3041 }
3042
3043 /* The type of ARG when used as an lvalue.  */
3044
3045 tree
3046 lvalue_type (tree arg)
3047 {
3048   tree type = TREE_TYPE (arg);
3049   return type;
3050 }
3051
3052 /* The type of ARG for printing error messages; denote lvalues with
3053    reference types.  */
3054
3055 tree
3056 error_type (tree arg)
3057 {
3058   tree type = TREE_TYPE (arg);
3059
3060   if (TREE_CODE (type) == ARRAY_TYPE)
3061     ;
3062   else if (TREE_CODE (type) == ERROR_MARK)
3063     ;
3064   else if (real_lvalue_p (arg))
3065     type = build_reference_type (lvalue_type (arg));
3066   else if (MAYBE_CLASS_TYPE_P (type))
3067     type = lvalue_type (arg);
3068
3069   return type;
3070 }
3071
3072 /* Does FUNCTION use a variable-length argument list?  */
3073
3074 int
3075 varargs_function_p (const_tree function)
3076 {
3077   return stdarg_p (TREE_TYPE (function));
3078 }
3079
3080 /* Returns 1 if decl is a member of a class.  */
3081
3082 int
3083 member_p (const_tree decl)
3084 {
3085   const_tree const ctx = DECL_CONTEXT (decl);
3086   return (ctx && TYPE_P (ctx));
3087 }
3088
3089 /* Create a placeholder for member access where we don't actually have an
3090    object that the access is against.  */
3091
3092 tree
3093 build_dummy_object (tree type)
3094 {
3095   tree decl = build1 (CONVERT_EXPR, build_pointer_type (type), void_node);
3096   return cp_build_indirect_ref (decl, RO_NULL, tf_warning_or_error);
3097 }
3098
3099 /* We've gotten a reference to a member of TYPE.  Return *this if appropriate,
3100    or a dummy object otherwise.  If BINFOP is non-0, it is filled with the
3101    binfo path from current_class_type to TYPE, or 0.  */
3102
3103 tree
3104 maybe_dummy_object (tree type, tree* binfop)
3105 {
3106   tree decl, context;
3107   tree binfo;
3108   tree current = current_nonlambda_class_type ();
3109
3110   if (current
3111       && (binfo = lookup_base (current, type, ba_any, NULL,
3112                                tf_warning_or_error)))
3113     context = current;
3114   else
3115     {
3116       /* Reference from a nested class member function.  */
3117       context = type;
3118       binfo = TYPE_BINFO (type);
3119     }
3120
3121   if (binfop)
3122     *binfop = binfo;
3123
3124   if (current_class_ref
3125       /* current_class_ref might not correspond to current_class_type if
3126          we're in tsubst_default_argument or a lambda-declarator; in either
3127          case, we want to use current_class_ref if it matches CONTEXT.  */
3128       && (same_type_ignoring_top_level_qualifiers_p
3129           (TREE_TYPE (current_class_ref), context)))
3130     decl = current_class_ref;
3131   else
3132     decl = build_dummy_object (context);
3133
3134   return decl;
3135 }
3136
3137 /* Returns 1 if OB is a placeholder object, or a pointer to one.  */
3138
3139 int
3140 is_dummy_object (const_tree ob)
3141 {
3142   if (INDIRECT_REF_P (ob))
3143     ob = TREE_OPERAND (ob, 0);
3144   return (TREE_CODE (ob) == CONVERT_EXPR
3145           && TREE_OPERAND (ob, 0) == void_node);
3146 }
3147
3148 /* Returns 1 iff type T is something we want to treat as a scalar type for
3149    the purpose of deciding whether it is trivial/POD/standard-layout.  */
3150
3151 bool
3152 scalarish_type_p (const_tree t)
3153 {
3154   if (t == error_mark_node)
3155     return 1;
3156
3157   return (SCALAR_TYPE_P (t)
3158           || TREE_CODE (t) == VECTOR_TYPE);
3159 }
3160
3161 /* Returns true iff T requires non-trivial default initialization.  */
3162
3163 bool
3164 type_has_nontrivial_default_init (const_tree t)
3165 {
3166   t = strip_array_types (CONST_CAST_TREE (t));
3167
3168   if (CLASS_TYPE_P (t))
3169     return TYPE_HAS_COMPLEX_DFLT (t);
3170   else
3171     return 0;
3172 }
3173
3174 /* Returns true iff copying an object of type T (including via move
3175    constructor) is non-trivial.  That is, T has no non-trivial copy
3176    constructors and no non-trivial move constructors.  */
3177
3178 bool
3179 type_has_nontrivial_copy_init (const_tree t)
3180 {
3181   t = strip_array_types (CONST_CAST_TREE (t));
3182
3183   if (CLASS_TYPE_P (t))
3184     {
3185       gcc_assert (COMPLETE_TYPE_P (t));
3186       return ((TYPE_HAS_COPY_CTOR (t)
3187                && TYPE_HAS_COMPLEX_COPY_CTOR (t))
3188               || TYPE_HAS_COMPLEX_MOVE_CTOR (t));
3189     }
3190   else
3191     return 0;
3192 }
3193
3194 /* Returns 1 iff type T is a trivially copyable type, as defined in
3195    [basic.types] and [class].  */
3196
3197 bool
3198 trivially_copyable_p (const_tree t)
3199 {
3200   t = strip_array_types (CONST_CAST_TREE (t));
3201
3202   if (CLASS_TYPE_P (t))
3203     return ((!TYPE_HAS_COPY_CTOR (t)
3204              || !TYPE_HAS_COMPLEX_COPY_CTOR (t))
3205             && !TYPE_HAS_COMPLEX_MOVE_CTOR (t)
3206             && (!TYPE_HAS_COPY_ASSIGN (t)
3207                 || !TYPE_HAS_COMPLEX_COPY_ASSIGN (t))
3208             && !TYPE_HAS_COMPLEX_MOVE_ASSIGN (t)
3209             && TYPE_HAS_TRIVIAL_DESTRUCTOR (t));
3210   else
3211     return !CP_TYPE_VOLATILE_P (t) && scalarish_type_p (t);
3212 }
3213
3214 /* Returns 1 iff type T is a trivial type, as defined in [basic.types] and
3215    [class].  */
3216
3217 bool
3218 trivial_type_p (const_tree t)
3219 {
3220   t = strip_array_types (CONST_CAST_TREE (t));
3221
3222   if (CLASS_TYPE_P (t))
3223     return (TYPE_HAS_TRIVIAL_DFLT (t)
3224             && trivially_copyable_p (t));
3225   else
3226     return scalarish_type_p (t);
3227 }
3228
3229 /* Returns 1 iff type T is a POD type, as defined in [basic.types].  */
3230
3231 bool
3232 pod_type_p (const_tree t)
3233 {
3234   /* This CONST_CAST is okay because strip_array_types returns its
3235      argument unmodified and we assign it to a const_tree.  */
3236   t = strip_array_types (CONST_CAST_TREE(t));
3237
3238   if (!CLASS_TYPE_P (t))
3239     return scalarish_type_p (t);
3240   else if (cxx_dialect > cxx98)
3241     /* [class]/10: A POD struct is a class that is both a trivial class and a
3242        standard-layout class, and has no non-static data members of type
3243        non-POD struct, non-POD union (or array of such types).
3244
3245        We don't need to check individual members because if a member is
3246        non-std-layout or non-trivial, the class will be too.  */
3247     return (std_layout_type_p (t) && trivial_type_p (t));
3248   else
3249     /* The C++98 definition of POD is different.  */
3250     return !CLASSTYPE_NON_LAYOUT_POD_P (t);
3251 }
3252
3253 /* Returns true iff T is POD for the purpose of layout, as defined in the
3254    C++ ABI.  */
3255
3256 bool
3257 layout_pod_type_p (const_tree t)
3258 {
3259   t = strip_array_types (CONST_CAST_TREE (t));
3260
3261   if (CLASS_TYPE_P (t))
3262     return !CLASSTYPE_NON_LAYOUT_POD_P (t);
3263   else
3264     return scalarish_type_p (t);
3265 }
3266
3267 /* Returns true iff T is a standard-layout type, as defined in
3268    [basic.types].  */
3269
3270 bool
3271 std_layout_type_p (const_tree t)
3272 {
3273   t = strip_array_types (CONST_CAST_TREE (t));
3274
3275   if (CLASS_TYPE_P (t))
3276     return !CLASSTYPE_NON_STD_LAYOUT (t);
3277   else
3278     return scalarish_type_p (t);
3279 }
3280
3281 /* Nonzero iff type T is a class template implicit specialization.  */
3282
3283 bool
3284 class_tmpl_impl_spec_p (const_tree t)
3285 {
3286   return CLASS_TYPE_P (t) && CLASSTYPE_TEMPLATE_INSTANTIATION (t);
3287 }
3288
3289 /* Returns 1 iff zero initialization of type T means actually storing
3290    zeros in it.  */
3291
3292 int
3293 zero_init_p (const_tree t)
3294 {
3295   /* This CONST_CAST is okay because strip_array_types returns its
3296      argument unmodified and we assign it to a const_tree.  */
3297   t = strip_array_types (CONST_CAST_TREE(t));
3298
3299   if (t == error_mark_node)
3300     return 1;
3301
3302   /* NULL pointers to data members are initialized with -1.  */
3303   if (TYPE_PTRDATAMEM_P (t))
3304     return 0;
3305
3306   /* Classes that contain types that can't be zero-initialized, cannot
3307      be zero-initialized themselves.  */
3308   if (CLASS_TYPE_P (t) && CLASSTYPE_NON_ZERO_INIT_P (t))
3309     return 0;
3310
3311   return 1;
3312 }
3313
3314 /* Table of valid C++ attributes.  */
3315 const struct attribute_spec cxx_attribute_table[] =
3316 {
3317   /* { name, min_len, max_len, decl_req, type_req, fn_type_req, handler,
3318        affects_type_identity } */
3319   { "java_interface", 0, 0, false, false, false,
3320     handle_java_interface_attribute, false },
3321   { "com_interface",  0, 0, false, false, false,
3322     handle_com_interface_attribute, false },
3323   { "init_priority",  1, 1, true,  false, false,
3324     handle_init_priority_attribute, false },
3325   { "abi_tag", 1, -1, false, false, false,
3326     handle_abi_tag_attribute, true },
3327   { NULL,             0, 0, false, false, false, NULL, false }
3328 };
3329
3330 /* Handle a "java_interface" attribute; arguments as in
3331    struct attribute_spec.handler.  */
3332 static tree
3333 handle_java_interface_attribute (tree* node,
3334                                  tree name,
3335                                  tree /*args*/,
3336                                  int flags,
3337                                  bool* no_add_attrs)
3338 {
3339   if (DECL_P (*node)
3340       || !CLASS_TYPE_P (*node)
3341       || !TYPE_FOR_JAVA (*node))
3342     {
3343       error ("%qE attribute can only be applied to Java class definitions",
3344              name);
3345       *no_add_attrs = true;
3346       return NULL_TREE;
3347     }
3348   if (!(flags & (int) ATTR_FLAG_TYPE_IN_PLACE))
3349     *node = build_variant_type_copy (*node);
3350   TYPE_JAVA_INTERFACE (*node) = 1;
3351
3352   return NULL_TREE;
3353 }
3354
3355 /* Handle a "com_interface" attribute; arguments as in
3356    struct attribute_spec.handler.  */
3357 static tree
3358 handle_com_interface_attribute (tree* node,
3359                                 tree name,
3360                                 tree /*args*/,
3361                                 int /*flags*/,
3362                                 bool* no_add_attrs)
3363 {
3364   static int warned;
3365
3366   *no_add_attrs = true;
3367
3368   if (DECL_P (*node)
3369       || !CLASS_TYPE_P (*node)
3370       || *node != TYPE_MAIN_VARIANT (*node))
3371     {
3372       warning (OPT_Wattributes, "%qE attribute can only be applied "
3373                "to class definitions", name);
3374       return NULL_TREE;
3375     }
3376
3377   if (!warned++)
3378     warning (0, "%qE is obsolete; g++ vtables are now COM-compatible by default",
3379              name);
3380
3381   return NULL_TREE;
3382 }
3383
3384 /* Handle an "init_priority" attribute; arguments as in
3385    struct attribute_spec.handler.  */
3386 static tree
3387 handle_init_priority_attribute (tree* node,
3388                                 tree name,
3389                                 tree args,
3390                                 int /*flags*/,
3391                                 bool* no_add_attrs)
3392 {
3393   tree initp_expr = TREE_VALUE (args);
3394   tree decl = *node;
3395   tree type = TREE_TYPE (decl);
3396   int pri;
3397
3398   STRIP_NOPS (initp_expr);
3399   initp_expr = default_conversion (initp_expr);
3400
3401   if (!initp_expr || TREE_CODE (initp_expr) != INTEGER_CST)
3402     {
3403       error ("requested init_priority is not an integer constant");
3404       *no_add_attrs = true;
3405       return NULL_TREE;
3406     }
3407
3408   pri = TREE_INT_CST_LOW (initp_expr);
3409
3410   type = strip_array_types (type);
3411
3412   if (decl == NULL_TREE
3413       || !VAR_P (decl)
3414       || !TREE_STATIC (decl)
3415       || DECL_EXTERNAL (decl)
3416       || (TREE_CODE (type) != RECORD_TYPE
3417           && TREE_CODE (type) != UNION_TYPE)
3418       /* Static objects in functions are initialized the
3419          first time control passes through that
3420          function. This is not precise enough to pin down an
3421          init_priority value, so don't allow it.  */
3422       || current_function_decl)
3423     {
3424       error ("can only use %qE attribute on file-scope definitions "
3425              "of objects of class type", name);
3426       *no_add_attrs = true;
3427       return NULL_TREE;
3428     }
3429
3430   if (pri > MAX_INIT_PRIORITY || pri <= 0)
3431     {
3432       error ("requested init_priority is out of range");
3433       *no_add_attrs = true;
3434       return NULL_TREE;
3435     }
3436
3437   /* Check for init_priorities that are reserved for
3438      language and runtime support implementations.*/
3439   if (pri <= MAX_RESERVED_INIT_PRIORITY)
3440     {
3441       warning
3442         (0, "requested init_priority is reserved for internal use");
3443     }
3444
3445   if (SUPPORTS_INIT_PRIORITY)
3446     {
3447       SET_DECL_INIT_PRIORITY (decl, pri);
3448       DECL_HAS_INIT_PRIORITY_P (decl) = 1;
3449       return NULL_TREE;
3450     }
3451   else
3452     {
3453       error ("%qE attribute is not supported on this platform", name);
3454       *no_add_attrs = true;
3455       return NULL_TREE;
3456     }
3457 }
3458
3459 /* DECL is being redeclared; the old declaration had the abi tags in OLD,
3460    and the new one has the tags in NEW_.  Give an error if there are tags
3461    in NEW_ that weren't in OLD.  */
3462
3463 bool
3464 check_abi_tag_redeclaration (const_tree decl, const_tree old, const_tree new_)
3465 {
3466   if (old && TREE_CODE (TREE_VALUE (old)) == TREE_LIST)
3467     old = TREE_VALUE (old);
3468   if (new_ && TREE_CODE (TREE_VALUE (new_)) == TREE_LIST)
3469     new_ = TREE_VALUE (new_);
3470   bool err = false;
3471   for (const_tree t = new_; t; t = TREE_CHAIN (t))
3472     {
3473       tree str = TREE_VALUE (t);
3474       for (const_tree in = old; in; in = TREE_CHAIN (in))
3475         {
3476           tree ostr = TREE_VALUE (in);
3477           if (cp_tree_equal (str, ostr))
3478             goto found;
3479         }
3480       error ("redeclaration of %qD adds abi tag %E", decl, str);
3481       err = true;
3482     found:;
3483     }
3484   if (err)
3485     {
3486       inform (DECL_SOURCE_LOCATION (decl), "previous declaration here");
3487       return false;
3488     }
3489   return true;
3490 }
3491
3492 /* Handle an "abi_tag" attribute; arguments as in
3493    struct attribute_spec.handler.  */
3494
3495 static tree
3496 handle_abi_tag_attribute (tree* node, tree name, tree args,
3497                           int flags, bool* no_add_attrs)
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           goto fail;
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                   goto fail;
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                   goto fail;
3538                 }
3539             }
3540         }
3541     }
3542
3543   if (TYPE_P (*node))
3544     {
3545       if (!OVERLOAD_TYPE_P (*node))
3546         {
3547           error ("%qE attribute applied to non-class, non-enum type %qT",
3548                  name, *node);
3549           goto fail;
3550         }
3551       else if (!(flags & (int)ATTR_FLAG_TYPE_IN_PLACE))
3552         {
3553           error ("%qE attribute applied to %qT after its definition",
3554                  name, *node);
3555           goto fail;
3556         }
3557       else if (CLASSTYPE_TEMPLATE_INSTANTIATION (*node))
3558         {
3559           warning (OPT_Wattributes, "ignoring %qE attribute applied to "
3560                    "template instantiation %qT", name, *node);
3561           goto fail;
3562         }
3563       else if (CLASSTYPE_TEMPLATE_SPECIALIZATION (*node))
3564         {
3565           warning (OPT_Wattributes, "ignoring %qE attribute applied to "
3566                    "template specialization %qT", name, *node);
3567           goto fail;
3568         }
3569
3570       tree attributes = TYPE_ATTRIBUTES (*node);
3571       tree decl = TYPE_NAME (*node);
3572
3573       /* Make sure all declarations have the same abi tags.  */
3574       if (DECL_SOURCE_LOCATION (decl) != input_location)
3575         {
3576           if (!check_abi_tag_redeclaration (decl,
3577                                             lookup_attribute ("abi_tag",
3578                                                               attributes),
3579                                             args))
3580             goto fail;
3581         }
3582     }
3583   else
3584     {
3585       if (TREE_CODE (*node) != FUNCTION_DECL)
3586         {
3587           error ("%qE attribute applied to non-function %qD", name, *node);
3588           goto fail;
3589         }
3590       else if (DECL_LANGUAGE (*node) == lang_c)
3591         {
3592           error ("%qE attribute applied to extern \"C\" function %qD",
3593                  name, *node);
3594           goto fail;
3595         }
3596     }
3597
3598   return NULL_TREE;
3599
3600  fail:
3601   *no_add_attrs = true;
3602   return NULL_TREE;
3603 }
3604
3605 /* Return a new PTRMEM_CST of the indicated TYPE.  The MEMBER is the
3606    thing pointed to by the constant.  */
3607
3608 tree
3609 make_ptrmem_cst (tree type, tree member)
3610 {
3611   tree ptrmem_cst = make_node (PTRMEM_CST);
3612   TREE_TYPE (ptrmem_cst) = type;
3613   PTRMEM_CST_MEMBER (ptrmem_cst) = member;
3614   return ptrmem_cst;
3615 }
3616
3617 /* Build a variant of TYPE that has the indicated ATTRIBUTES.  May
3618    return an existing type if an appropriate type already exists.  */
3619
3620 tree
3621 cp_build_type_attribute_variant (tree type, tree attributes)
3622 {
3623   tree new_type;
3624
3625   new_type = build_type_attribute_variant (type, attributes);
3626   if (TREE_CODE (new_type) == FUNCTION_TYPE
3627       || TREE_CODE (new_type) == METHOD_TYPE)
3628     {
3629       new_type = build_exception_variant (new_type,
3630                                           TYPE_RAISES_EXCEPTIONS (type));
3631       new_type = build_ref_qualified_type (new_type,
3632                                            type_memfn_rqual (type));
3633     }
3634
3635   /* Making a new main variant of a class type is broken.  */
3636   gcc_assert (!CLASS_TYPE_P (type) || new_type == type);
3637
3638   return new_type;
3639 }
3640
3641 /* Return TRUE if TYPE1 and TYPE2 are identical for type hashing purposes.
3642    Called only after doing all language independent checks.  Only
3643    to check TYPE_RAISES_EXCEPTIONS for FUNCTION_TYPE, the rest is already
3644    compared in type_hash_eq.  */
3645
3646 bool
3647 cxx_type_hash_eq (const_tree typea, const_tree typeb)
3648 {
3649   gcc_assert (TREE_CODE (typea) == FUNCTION_TYPE
3650               || TREE_CODE (typea) == METHOD_TYPE);
3651
3652   return comp_except_specs (TYPE_RAISES_EXCEPTIONS (typea),
3653                             TYPE_RAISES_EXCEPTIONS (typeb), ce_exact);
3654 }
3655
3656 /* Apply FUNC to all language-specific sub-trees of TP in a pre-order
3657    traversal.  Called from walk_tree.  */
3658
3659 tree
3660 cp_walk_subtrees (tree *tp, int *walk_subtrees_p, walk_tree_fn func,
3661                   void *data, hash_set<tree> *pset)
3662 {
3663   enum tree_code code = TREE_CODE (*tp);
3664   tree result;
3665
3666 #define WALK_SUBTREE(NODE)                              \
3667   do                                                    \
3668     {                                                   \
3669       result = cp_walk_tree (&(NODE), func, data, pset);        \
3670       if (result) goto out;                             \
3671     }                                                   \
3672   while (0)
3673
3674   /* Not one of the easy cases.  We must explicitly go through the
3675      children.  */
3676   result = NULL_TREE;
3677   switch (code)
3678     {
3679     case DEFAULT_ARG:
3680     case TEMPLATE_TEMPLATE_PARM:
3681     case BOUND_TEMPLATE_TEMPLATE_PARM:
3682     case UNBOUND_CLASS_TEMPLATE:
3683     case TEMPLATE_PARM_INDEX:
3684     case TEMPLATE_TYPE_PARM:
3685     case TYPENAME_TYPE:
3686     case TYPEOF_TYPE:
3687     case UNDERLYING_TYPE:
3688       /* None of these have subtrees other than those already walked
3689          above.  */
3690       *walk_subtrees_p = 0;
3691       break;
3692
3693     case BASELINK:
3694       WALK_SUBTREE (BASELINK_FUNCTIONS (*tp));
3695       *walk_subtrees_p = 0;
3696       break;
3697
3698     case PTRMEM_CST:
3699       WALK_SUBTREE (TREE_TYPE (*tp));
3700       *walk_subtrees_p = 0;
3701       break;
3702
3703     case TREE_LIST:
3704       WALK_SUBTREE (TREE_PURPOSE (*tp));
3705       break;
3706
3707     case OVERLOAD:
3708       WALK_SUBTREE (OVL_FUNCTION (*tp));
3709       WALK_SUBTREE (OVL_CHAIN (*tp));
3710       *walk_subtrees_p = 0;
3711       break;
3712
3713     case USING_DECL:
3714       WALK_SUBTREE (DECL_NAME (*tp));
3715       WALK_SUBTREE (USING_DECL_SCOPE (*tp));
3716       WALK_SUBTREE (USING_DECL_DECLS (*tp));
3717       *walk_subtrees_p = 0;
3718       break;
3719
3720     case RECORD_TYPE:
3721       if (TYPE_PTRMEMFUNC_P (*tp))
3722         WALK_SUBTREE (TYPE_PTRMEMFUNC_FN_TYPE_RAW (*tp));
3723       break;
3724
3725     case TYPE_ARGUMENT_PACK:
3726     case NONTYPE_ARGUMENT_PACK:
3727       {
3728         tree args = ARGUMENT_PACK_ARGS (*tp);
3729         int i, len = TREE_VEC_LENGTH (args);
3730         for (i = 0; i < len; i++)
3731           WALK_SUBTREE (TREE_VEC_ELT (args, i));
3732       }
3733       break;
3734
3735     case TYPE_PACK_EXPANSION:
3736       WALK_SUBTREE (TREE_TYPE (*tp));
3737       WALK_SUBTREE (PACK_EXPANSION_EXTRA_ARGS (*tp));
3738       *walk_subtrees_p = 0;
3739       break;
3740
3741     case EXPR_PACK_EXPANSION:
3742       WALK_SUBTREE (TREE_OPERAND (*tp, 0));
3743       WALK_SUBTREE (PACK_EXPANSION_EXTRA_ARGS (*tp));
3744       *walk_subtrees_p = 0;
3745       break;
3746
3747     case CAST_EXPR:
3748     case REINTERPRET_CAST_EXPR:
3749     case STATIC_CAST_EXPR:
3750     case CONST_CAST_EXPR:
3751     case DYNAMIC_CAST_EXPR:
3752     case IMPLICIT_CONV_EXPR:
3753       if (TREE_TYPE (*tp))
3754         WALK_SUBTREE (TREE_TYPE (*tp));
3755
3756       {
3757         int i;
3758         for (i = 0; i < TREE_CODE_LENGTH (TREE_CODE (*tp)); ++i)
3759           WALK_SUBTREE (TREE_OPERAND (*tp, i));
3760       }
3761       *walk_subtrees_p = 0;
3762       break;
3763
3764     case TRAIT_EXPR:
3765       WALK_SUBTREE (TRAIT_EXPR_TYPE1 (*tp));
3766       WALK_SUBTREE (TRAIT_EXPR_TYPE2 (*tp));
3767       *walk_subtrees_p = 0;
3768       break;
3769
3770     case DECLTYPE_TYPE:
3771       WALK_SUBTREE (DECLTYPE_TYPE_EXPR (*tp));
3772       *walk_subtrees_p = 0;
3773       break;
3774
3775     case REQUIRES_EXPR:
3776       // Only recurse through the nested expression. Do not
3777       // walk the parameter list. Doing so causes false
3778       // positives in the pack expansion checker since the
3779       // requires parameters are introduced as pack expansions.
3780       WALK_SUBTREE (TREE_OPERAND (*tp, 1));
3781       *walk_subtrees_p = 0;
3782       break;
3783
3784     default:
3785       return NULL_TREE;
3786     }
3787
3788   /* We didn't find what we were looking for.  */
3789  out:
3790   return result;
3791
3792 #undef WALK_SUBTREE
3793 }
3794
3795 /* Like save_expr, but for C++.  */
3796
3797 tree
3798 cp_save_expr (tree expr)
3799 {
3800   /* There is no reason to create a SAVE_EXPR within a template; if
3801      needed, we can create the SAVE_EXPR when instantiating the
3802      template.  Furthermore, the middle-end cannot handle C++-specific
3803      tree codes.  */
3804   if (processing_template_decl)
3805     return expr;
3806   return save_expr (expr);
3807 }
3808
3809 /* Initialize tree.c.  */
3810
3811 void
3812 init_tree (void)
3813 {
3814   list_hash_table = hash_table<list_hasher>::create_ggc (61);
3815 }
3816
3817 /* Returns the kind of special function that DECL (a FUNCTION_DECL)
3818    is.  Note that sfk_none is zero, so this function can be used as a
3819    predicate to test whether or not DECL is a special function.  */
3820
3821 special_function_kind
3822 special_function_p (const_tree decl)
3823 {
3824   /* Rather than doing all this stuff with magic names, we should
3825      probably have a field of type `special_function_kind' in
3826      DECL_LANG_SPECIFIC.  */
3827   if (DECL_INHERITED_CTOR_BASE (decl))
3828     return sfk_inheriting_constructor;
3829   if (DECL_COPY_CONSTRUCTOR_P (decl))
3830     return sfk_copy_constructor;
3831   if (DECL_MOVE_CONSTRUCTOR_P (decl))
3832     return sfk_move_constructor;
3833   if (DECL_CONSTRUCTOR_P (decl))
3834     return sfk_constructor;
3835   if (DECL_OVERLOADED_OPERATOR_P (decl) == NOP_EXPR)
3836     {
3837       if (copy_fn_p (decl))
3838         return sfk_copy_assignment;
3839       if (move_fn_p (decl))
3840         return sfk_move_assignment;
3841     }
3842   if (DECL_MAYBE_IN_CHARGE_DESTRUCTOR_P (decl))
3843     return sfk_destructor;
3844   if (DECL_COMPLETE_DESTRUCTOR_P (decl))
3845     return sfk_complete_destructor;
3846   if (DECL_BASE_DESTRUCTOR_P (decl))
3847     return sfk_base_destructor;
3848   if (DECL_DELETING_DESTRUCTOR_P (decl))
3849     return sfk_deleting_destructor;
3850   if (DECL_CONV_FN_P (decl))
3851     return sfk_conversion;
3852
3853   return sfk_none;
3854 }
3855
3856 /* Returns nonzero if TYPE is a character type, including wchar_t.  */
3857
3858 int
3859 char_type_p (tree type)
3860 {
3861   return (same_type_p (type, char_type_node)
3862           || same_type_p (type, unsigned_char_type_node)
3863           || same_type_p (type, signed_char_type_node)
3864           || same_type_p (type, char16_type_node)
3865           || same_type_p (type, char32_type_node)
3866           || same_type_p (type, wchar_type_node));
3867 }
3868
3869 /* Returns the kind of linkage associated with the indicated DECL.  Th
3870    value returned is as specified by the language standard; it is
3871    independent of implementation details regarding template
3872    instantiation, etc.  For example, it is possible that a declaration
3873    to which this function assigns external linkage would not show up
3874    as a global symbol when you run `nm' on the resulting object file.  */
3875
3876 linkage_kind
3877 decl_linkage (tree decl)
3878 {
3879   /* This function doesn't attempt to calculate the linkage from first
3880      principles as given in [basic.link].  Instead, it makes use of
3881      the fact that we have already set TREE_PUBLIC appropriately, and
3882      then handles a few special cases.  Ideally, we would calculate
3883      linkage first, and then transform that into a concrete
3884      implementation.  */
3885
3886   /* Things that don't have names have no linkage.  */
3887   if (!DECL_NAME (decl))
3888     return lk_none;
3889
3890   /* Fields have no linkage.  */
3891   if (TREE_CODE (decl) == FIELD_DECL)
3892     return lk_none;
3893
3894   /* Things that are TREE_PUBLIC have external linkage.  */
3895   if (TREE_PUBLIC (decl))
3896     return lk_external;
3897
3898   if (TREE_CODE (decl) == NAMESPACE_DECL)
3899     return lk_external;
3900
3901   /* Linkage of a CONST_DECL depends on the linkage of the enumeration
3902      type.  */
3903   if (TREE_CODE (decl) == CONST_DECL)
3904     return decl_linkage (TYPE_NAME (DECL_CONTEXT (decl)));
3905
3906   /* Things in local scope do not have linkage, if they don't have
3907      TREE_PUBLIC set.  */
3908   if (decl_function_context (decl))
3909     return lk_none;
3910
3911   /* Members of the anonymous namespace also have TREE_PUBLIC unset, but
3912      are considered to have external linkage for language purposes, as do
3913      template instantiations on targets without weak symbols.  DECLs really
3914      meant to have internal linkage have DECL_THIS_STATIC set.  */
3915   if (TREE_CODE (decl) == TYPE_DECL)
3916     return lk_external;
3917   if (VAR_OR_FUNCTION_DECL_P (decl))
3918     {
3919       if (!DECL_THIS_STATIC (decl))
3920         return lk_external;
3921
3922       /* Static data members and static member functions from classes
3923          in anonymous namespace also don't have TREE_PUBLIC set.  */
3924       if (DECL_CLASS_CONTEXT (decl))
3925         return lk_external;
3926     }
3927
3928   /* Everything else has internal linkage.  */
3929   return lk_internal;
3930 }
3931
3932 /* Returns the storage duration of the object or reference associated with
3933    the indicated DECL, which should be a VAR_DECL or PARM_DECL.  */
3934
3935 duration_kind
3936 decl_storage_duration (tree decl)
3937 {
3938   if (TREE_CODE (decl) == PARM_DECL)
3939     return dk_auto;
3940   if (TREE_CODE (decl) == FUNCTION_DECL)
3941     return dk_static;
3942   gcc_assert (VAR_P (decl));
3943   if (!TREE_STATIC (decl)
3944       && !DECL_EXTERNAL (decl))
3945     return dk_auto;
3946   if (DECL_THREAD_LOCAL_P (decl))
3947     return dk_thread;
3948   return dk_static;
3949 }
3950 \f
3951 /* EXP is an expression that we want to pre-evaluate.  Returns (in
3952    *INITP) an expression that will perform the pre-evaluation.  The
3953    value returned by this function is a side-effect free expression
3954    equivalent to the pre-evaluated expression.  Callers must ensure
3955    that *INITP is evaluated before EXP.  */
3956
3957 tree
3958 stabilize_expr (tree exp, tree* initp)
3959 {
3960   tree init_expr;
3961
3962   if (!TREE_SIDE_EFFECTS (exp))
3963     init_expr = NULL_TREE;
3964   else if (VOID_TYPE_P (TREE_TYPE (exp)))
3965     {
3966       init_expr = exp;
3967       exp = void_node;
3968     }
3969   /* There are no expressions with REFERENCE_TYPE, but there can be call
3970      arguments with such a type; just treat it as a pointer.  */
3971   else if (TREE_CODE (TREE_TYPE (exp)) == REFERENCE_TYPE
3972            || SCALAR_TYPE_P (TREE_TYPE (exp))
3973            || !lvalue_or_rvalue_with_address_p (exp))
3974     {
3975       init_expr = get_target_expr (exp);
3976       exp = TARGET_EXPR_SLOT (init_expr);
3977       if (CLASS_TYPE_P (TREE_TYPE (exp)))
3978         exp = move (exp);
3979       else
3980         exp = rvalue (exp);
3981     }
3982   else
3983     {
3984       bool xval = !real_lvalue_p (exp);
3985       exp = cp_build_addr_expr (exp, tf_warning_or_error);
3986       init_expr = get_target_expr (exp);
3987       exp = TARGET_EXPR_SLOT (init_expr);
3988       exp = cp_build_indirect_ref (exp, RO_NULL, tf_warning_or_error);
3989       if (xval)
3990         exp = move (exp);
3991     }
3992   *initp = init_expr;
3993
3994   gcc_assert (!TREE_SIDE_EFFECTS (exp));
3995   return exp;
3996 }
3997
3998 /* Add NEW_EXPR, an expression whose value we don't care about, after the
3999    similar expression ORIG.  */
4000
4001 tree
4002 add_stmt_to_compound (tree orig, tree new_expr)
4003 {
4004   if (!new_expr || !TREE_SIDE_EFFECTS (new_expr))
4005     return orig;
4006   if (!orig || !TREE_SIDE_EFFECTS (orig))
4007     return new_expr;
4008   return build2 (COMPOUND_EXPR, void_type_node, orig, new_expr);
4009 }
4010
4011 /* Like stabilize_expr, but for a call whose arguments we want to
4012    pre-evaluate.  CALL is modified in place to use the pre-evaluated
4013    arguments, while, upon return, *INITP contains an expression to
4014    compute the arguments.  */
4015
4016 void
4017 stabilize_call (tree call, tree *initp)
4018 {
4019   tree inits = NULL_TREE;
4020   int i;
4021   int nargs = call_expr_nargs (call);
4022
4023   if (call == error_mark_node || processing_template_decl)
4024     {
4025       *initp = NULL_TREE;
4026       return;
4027     }
4028
4029   gcc_assert (TREE_CODE (call) == CALL_EXPR);
4030
4031   for (i = 0; i < nargs; i++)
4032     {
4033       tree init;
4034       CALL_EXPR_ARG (call, i) =
4035         stabilize_expr (CALL_EXPR_ARG (call, i), &init);
4036       inits = add_stmt_to_compound (inits, init);
4037     }
4038
4039   *initp = inits;
4040 }
4041
4042 /* Like stabilize_expr, but for an AGGR_INIT_EXPR whose arguments we want
4043    to pre-evaluate.  CALL is modified in place to use the pre-evaluated
4044    arguments, while, upon return, *INITP contains an expression to
4045    compute the arguments.  */
4046
4047 static void
4048 stabilize_aggr_init (tree call, tree *initp)
4049 {
4050   tree inits = NULL_TREE;
4051   int i;
4052   int nargs = aggr_init_expr_nargs (call);
4053
4054   if (call == error_mark_node)
4055     return;
4056
4057   gcc_assert (TREE_CODE (call) == AGGR_INIT_EXPR);
4058
4059   for (i = 0; i < nargs; i++)
4060     {
4061       tree init;
4062       AGGR_INIT_EXPR_ARG (call, i) =
4063         stabilize_expr (AGGR_INIT_EXPR_ARG (call, i), &init);
4064       inits = add_stmt_to_compound (inits, init);
4065     }
4066
4067   *initp = inits;
4068 }
4069
4070 /* Like stabilize_expr, but for an initialization.
4071
4072    If the initialization is for an object of class type, this function
4073    takes care not to introduce additional temporaries.
4074
4075    Returns TRUE iff the expression was successfully pre-evaluated,
4076    i.e., if INIT is now side-effect free, except for, possibly, a
4077    single call to a constructor.  */
4078
4079 bool
4080 stabilize_init (tree init, tree *initp)
4081 {
4082   tree t = init;
4083
4084   *initp = NULL_TREE;
4085
4086   if (t == error_mark_node || processing_template_decl)
4087     return true;
4088
4089   if (TREE_CODE (t) == INIT_EXPR)
4090     t = TREE_OPERAND (t, 1);
4091   if (TREE_CODE (t) == TARGET_EXPR)
4092     t = TARGET_EXPR_INITIAL (t);
4093
4094   /* If the RHS can be stabilized without breaking copy elision, stabilize
4095      it.  We specifically don't stabilize class prvalues here because that
4096      would mean an extra copy, but they might be stabilized below.  */
4097   if (TREE_CODE (init) == INIT_EXPR
4098       && TREE_CODE (t) != CONSTRUCTOR
4099       && TREE_CODE (t) != AGGR_INIT_EXPR
4100       && (SCALAR_TYPE_P (TREE_TYPE (t))
4101           || lvalue_or_rvalue_with_address_p (t)))
4102     {
4103       TREE_OPERAND (init, 1) = stabilize_expr (t, initp);
4104       return true;
4105     }
4106
4107   if (TREE_CODE (t) == COMPOUND_EXPR
4108       && TREE_CODE (init) == INIT_EXPR)
4109     {
4110       tree last = expr_last (t);
4111       /* Handle stabilizing the EMPTY_CLASS_EXPR pattern.  */
4112       if (!TREE_SIDE_EFFECTS (last))
4113         {
4114           *initp = t;
4115           TREE_OPERAND (init, 1) = last;
4116           return true;
4117         }
4118     }
4119
4120   if (TREE_CODE (t) == CONSTRUCTOR)
4121     {
4122       /* Aggregate initialization: stabilize each of the field
4123          initializers.  */
4124       unsigned i;
4125       constructor_elt *ce;
4126       bool good = true;
4127       vec<constructor_elt, va_gc> *v = CONSTRUCTOR_ELTS (t);
4128       for (i = 0; vec_safe_iterate (v, i, &ce); ++i)
4129         {
4130           tree type = TREE_TYPE (ce->value);
4131           tree subinit;
4132           if (TREE_CODE (type) == REFERENCE_TYPE
4133               || SCALAR_TYPE_P (type))
4134             ce->value = stabilize_expr (ce->value, &subinit);
4135           else if (!stabilize_init (ce->value, &subinit))
4136             good = false;
4137           *initp = add_stmt_to_compound (*initp, subinit);
4138         }
4139       return good;
4140     }
4141
4142   if (TREE_CODE (t) == CALL_EXPR)
4143     {
4144       stabilize_call (t, initp);
4145       return true;
4146     }
4147
4148   if (TREE_CODE (t) == AGGR_INIT_EXPR)
4149     {
4150       stabilize_aggr_init (t, initp);
4151       return true;
4152     }
4153
4154   /* The initialization is being performed via a bitwise copy -- and
4155      the item copied may have side effects.  */
4156   return !TREE_SIDE_EFFECTS (init);
4157 }
4158
4159 /* Like "fold", but should be used whenever we might be processing the
4160    body of a template.  */
4161
4162 tree
4163 fold_if_not_in_template (tree expr)
4164 {
4165   /* In the body of a template, there is never any need to call
4166      "fold".  We will call fold later when actually instantiating the
4167      template.  Integral constant expressions in templates will be
4168      evaluated via instantiate_non_dependent_expr, as necessary.  */
4169   if (processing_template_decl)
4170     return expr;
4171
4172   /* Fold C++ front-end specific tree codes.  */
4173   if (TREE_CODE (expr) == UNARY_PLUS_EXPR)
4174     return fold_convert (TREE_TYPE (expr), TREE_OPERAND (expr, 0));
4175
4176   return fold (expr);
4177 }
4178
4179 /* Returns true if a cast to TYPE may appear in an integral constant
4180    expression.  */
4181
4182 bool
4183 cast_valid_in_integral_constant_expression_p (tree type)
4184 {
4185   return (INTEGRAL_OR_ENUMERATION_TYPE_P (type)
4186           || cxx_dialect >= cxx11
4187           || dependent_type_p (type)
4188           || type == error_mark_node);
4189 }
4190
4191 /* Return true if we need to fix linkage information of DECL.  */
4192
4193 static bool
4194 cp_fix_function_decl_p (tree decl)
4195 {
4196   /* Skip if DECL is not externally visible.  */
4197   if (!TREE_PUBLIC (decl))
4198     return false;
4199
4200   /* We need to fix DECL if it a appears to be exported but with no
4201      function body.  Thunks do not have CFGs and we may need to
4202      handle them specially later.   */
4203   if (!gimple_has_body_p (decl)
4204       && !DECL_THUNK_P (decl)
4205       && !DECL_EXTERNAL (decl))
4206     {
4207       struct cgraph_node *node = cgraph_node::get (decl);
4208
4209       /* Don't fix same_body aliases.  Although they don't have their own
4210          CFG, they share it with what they alias to.  */
4211       if (!node || !node->alias
4212           || !vec_safe_length (node->ref_list.references))
4213         return true;
4214     }
4215
4216   return false;
4217 }
4218
4219 /* Clean the C++ specific parts of the tree T. */
4220
4221 void
4222 cp_free_lang_data (tree t)
4223 {
4224   if (TREE_CODE (t) == METHOD_TYPE
4225       || TREE_CODE (t) == FUNCTION_TYPE)
4226     {
4227       /* Default args are not interesting anymore.  */
4228       tree argtypes = TYPE_ARG_TYPES (t);
4229       while (argtypes)
4230         {
4231           TREE_PURPOSE (argtypes) = 0;
4232           argtypes = TREE_CHAIN (argtypes);
4233         }
4234     }
4235   else if (TREE_CODE (t) == FUNCTION_DECL
4236            && cp_fix_function_decl_p (t))
4237     {
4238       /* If T is used in this translation unit at all,  the definition
4239          must exist somewhere else since we have decided to not emit it
4240          in this TU.  So make it an external reference.  */
4241       DECL_EXTERNAL (t) = 1;
4242       TREE_STATIC (t) = 0;
4243     }
4244   if (TREE_CODE (t) == NAMESPACE_DECL)
4245     {
4246       /* The list of users of a namespace isn't useful for the middle-end
4247          or debug generators.  */
4248       DECL_NAMESPACE_USERS (t) = NULL_TREE;
4249       /* Neither do we need the leftover chaining of namespaces
4250          from the binding level.  */
4251       DECL_CHAIN (t) = NULL_TREE;
4252     }
4253 }
4254
4255 /* Stub for c-common.  Please keep in sync with c-decl.c.
4256    FIXME: If address space support is target specific, then this
4257    should be a C target hook.  But currently this is not possible,
4258    because this function is called via REGISTER_TARGET_PRAGMAS.  */
4259 void
4260 c_register_addr_space (const char * /*word*/, addr_space_t /*as*/)
4261 {
4262 }
4263
4264 /* Return the number of operands in T that we care about for things like
4265    mangling.  */
4266
4267 int
4268 cp_tree_operand_length (const_tree t)
4269 {
4270   enum tree_code code = TREE_CODE (t);
4271
4272   switch (code)
4273     {
4274     case PREINCREMENT_EXPR:
4275     case PREDECREMENT_EXPR:
4276     case POSTINCREMENT_EXPR:
4277     case POSTDECREMENT_EXPR:
4278       return 1;
4279
4280     case ARRAY_REF:
4281       return 2;
4282
4283     case EXPR_PACK_EXPANSION:
4284       return 1;
4285
4286     default:
4287       return TREE_OPERAND_LENGTH (t);
4288     }
4289 }
4290
4291 /* Implement -Wzero_as_null_pointer_constant.  Return true if the
4292    conditions for the warning hold, false otherwise.  */
4293 bool
4294 maybe_warn_zero_as_null_pointer_constant (tree expr, location_t loc)
4295 {
4296   if (c_inhibit_evaluation_warnings == 0
4297       && !NULLPTR_TYPE_P (TREE_TYPE (expr)))
4298     {
4299       warning_at (loc, OPT_Wzero_as_null_pointer_constant,
4300                   "zero as null pointer constant");
4301       return true;
4302     }
4303   return false;
4304 }
4305 \f
4306 #if defined ENABLE_TREE_CHECKING && (GCC_VERSION >= 2007)
4307 /* Complain that some language-specific thing hanging off a tree
4308    node has been accessed improperly.  */
4309
4310 void
4311 lang_check_failed (const char* file, int line, const char* function)
4312 {
4313   internal_error ("lang_* check: failed in %s, at %s:%d",
4314                   function, trim_filename (file), line);
4315 }
4316 #endif /* ENABLE_TREE_CHECKING */
4317
4318 #include "gt-cp-tree.h"