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