gcc/cp/tree.c

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