gcc/cp/tree.c

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