gcc/cp/tree.c

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