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   if (OVERLOAD_TYPE_P (result))
1191     {
1192       /* On classes and enums all attributes are ingrained.  */
1193       gcc_assert (attribs == TYPE_ATTRIBUTES (result));
1194       return result;
1195     }
1196
1197   for (tree a = attribs; a; a = TREE_CHAIN (a))
1198     {
1199       const attribute_spec *as
1200         = lookup_attribute_spec (get_attribute_name (a));
1201       if (as && as->affects_type_identity)
1202         {
1203           if (!first_ident)
1204             first_ident = a;
1205           else if (first_ident == error_mark_node)
1206             {
1207               *p = tree_cons (TREE_PURPOSE (a), TREE_VALUE (a), NULL_TREE);
1208               p = &TREE_CHAIN (*p);
1209             }
1210         }
1211       else if (first_ident)
1212         {
1213           for (tree a2 = first_ident; a2; a2 = TREE_CHAIN (a2))
1214             {
1215               *p = tree_cons (TREE_PURPOSE (a2), TREE_VALUE (a2), NULL_TREE);
1216               p = &TREE_CHAIN (*p);
1217             }
1218           first_ident = error_mark_node;
1219         }
1220     }
1221   if (first_ident != error_mark_node)
1222     new_attribs = first_ident;
1223
1224   if (first_ident == attribs)
1225     /* All attributes affected type identity.  */;
1226   else
1227     *remove_attributes = true;
1228
1229   return cp_build_type_attribute_variant (result, new_attribs);
1230 }
1231
1232 /* Builds a qualified variant of T that is not a typedef variant.
1233    E.g. consider the following declarations:
1234      typedef const int ConstInt;
1235      typedef ConstInt* PtrConstInt;
1236    If T is PtrConstInt, this function returns a type representing
1237      const int*.
1238    In other words, if T is a typedef, the function returns the underlying type.
1239    The cv-qualification and attributes of the type returned match the
1240    input type.
1241    They will always be compatible types.
1242    The returned type is built so that all of its subtypes
1243    recursively have their typedefs stripped as well.
1244
1245    This is different from just returning TYPE_CANONICAL (T)
1246    Because of several reasons:
1247     * If T is a type that needs structural equality
1248       its TYPE_CANONICAL (T) will be NULL.
1249     * TYPE_CANONICAL (T) desn't carry type attributes
1250       and loses template parameter names.
1251
1252    If REMOVE_ATTRIBUTES is non-null, also strip attributes that don't
1253    affect type identity, and set the referent to true if any were
1254    stripped.  */
1255
1256 tree
1257 strip_typedefs (tree t, bool *remove_attributes)
1258 {
1259   tree result = NULL, type = NULL, t0 = NULL;
1260
1261   if (!t || t == error_mark_node)
1262     return t;
1263
1264   if (TREE_CODE (t) == TREE_LIST)
1265     {
1266       bool changed = false;
1267       vec<tree,va_gc> *vec = make_tree_vector ();
1268       for (; t; t = TREE_CHAIN (t))
1269         {
1270           gcc_assert (!TREE_PURPOSE (t));
1271           tree elt = strip_typedefs (TREE_VALUE (t), remove_attributes);
1272           if (elt != TREE_VALUE (t))
1273             changed = true;
1274           vec_safe_push (vec, elt);
1275         }
1276       tree r = t;
1277       if (changed)
1278         r = build_tree_list_vec (vec);
1279       release_tree_vector (vec);
1280       return r;
1281     }
1282
1283   gcc_assert (TYPE_P (t));
1284
1285   if (t == TYPE_CANONICAL (t))
1286     return t;
1287
1288   if (dependent_alias_template_spec_p (t))
1289     /* DR 1558: However, if the template-id is dependent, subsequent
1290        template argument substitution still applies to the template-id.  */
1291     return t;
1292
1293   switch (TREE_CODE (t))
1294     {
1295     case POINTER_TYPE:
1296       type = strip_typedefs (TREE_TYPE (t), remove_attributes);
1297       result = build_pointer_type (type);
1298       break;
1299     case REFERENCE_TYPE:
1300       type = strip_typedefs (TREE_TYPE (t), remove_attributes);
1301       result = cp_build_reference_type (type, TYPE_REF_IS_RVALUE (t));
1302       break;
1303     case OFFSET_TYPE:
1304       t0 = strip_typedefs (TYPE_OFFSET_BASETYPE (t), remove_attributes);
1305       type = strip_typedefs (TREE_TYPE (t), remove_attributes);
1306       result = build_offset_type (t0, type);
1307       break;
1308     case RECORD_TYPE:
1309       if (TYPE_PTRMEMFUNC_P (t))
1310         {
1311           t0 = strip_typedefs (TYPE_PTRMEMFUNC_FN_TYPE (t), remove_attributes);
1312           result = build_ptrmemfunc_type (t0);
1313         }
1314       break;
1315     case ARRAY_TYPE:
1316       type = strip_typedefs (TREE_TYPE (t), remove_attributes);
1317       t0  = strip_typedefs (TYPE_DOMAIN (t), remove_attributes);
1318       result = build_cplus_array_type (type, t0);
1319       break;
1320     case FUNCTION_TYPE:
1321     case METHOD_TYPE:
1322       {
1323         tree arg_types = NULL, arg_node, arg_type;
1324         for (arg_node = TYPE_ARG_TYPES (t);
1325              arg_node;
1326              arg_node = TREE_CHAIN (arg_node))
1327           {
1328             if (arg_node == void_list_node)
1329               break;
1330             arg_type = strip_typedefs (TREE_VALUE (arg_node),
1331                                        remove_attributes);
1332             gcc_assert (arg_type);
1333
1334             arg_types =
1335               tree_cons (TREE_PURPOSE (arg_node), arg_type, arg_types);
1336           }
1337
1338         if (arg_types)
1339           arg_types = nreverse (arg_types);
1340
1341         /* A list of parameters not ending with an ellipsis
1342            must end with void_list_node.  */
1343         if (arg_node)
1344           arg_types = chainon (arg_types, void_list_node);
1345
1346         type = strip_typedefs (TREE_TYPE (t), remove_attributes);
1347         if (TREE_CODE (t) == METHOD_TYPE)
1348           {
1349             tree class_type = TREE_TYPE (TREE_VALUE (arg_types));
1350             gcc_assert (class_type);
1351             result =
1352               build_method_type_directly (class_type, type,
1353                                           TREE_CHAIN (arg_types));
1354             result
1355               = build_ref_qualified_type (result, type_memfn_rqual (t));
1356           }
1357         else
1358           {
1359             result = build_function_type (type,
1360                                           arg_types);
1361             result = apply_memfn_quals (result,
1362                                         type_memfn_quals (t),
1363                                         type_memfn_rqual (t));
1364           }
1365
1366         if (TYPE_RAISES_EXCEPTIONS (t))
1367           result = build_exception_variant (result,
1368                                             TYPE_RAISES_EXCEPTIONS (t));
1369         if (TYPE_HAS_LATE_RETURN_TYPE (t))
1370           TYPE_HAS_LATE_RETURN_TYPE (result) = 1;
1371       }
1372       break;
1373     case TYPENAME_TYPE:
1374       {
1375         tree fullname = TYPENAME_TYPE_FULLNAME (t);
1376         if (TREE_CODE (fullname) == TEMPLATE_ID_EXPR
1377             && TREE_OPERAND (fullname, 1))
1378           {
1379             tree args = TREE_OPERAND (fullname, 1);
1380             tree new_args = copy_node (args);
1381             bool changed = false;
1382             for (int i = 0; i < TREE_VEC_LENGTH (args); ++i)
1383               {
1384                 tree arg = TREE_VEC_ELT (args, i);
1385                 tree strip_arg;
1386                 if (TYPE_P (arg))
1387                   strip_arg = strip_typedefs (arg, remove_attributes);
1388                 else
1389                   strip_arg = strip_typedefs_expr (arg, remove_attributes);
1390                 TREE_VEC_ELT (new_args, i) = strip_arg;
1391                 if (strip_arg != arg)
1392                   changed = true;
1393               }
1394             if (changed)
1395               {
1396                 NON_DEFAULT_TEMPLATE_ARGS_COUNT (new_args)
1397                   = NON_DEFAULT_TEMPLATE_ARGS_COUNT (args);
1398                 fullname
1399                   = lookup_template_function (TREE_OPERAND (fullname, 0),
1400                                               new_args);
1401               }
1402             else
1403               ggc_free (new_args);
1404           }
1405         result = make_typename_type (strip_typedefs (TYPE_CONTEXT (t),
1406                                                      remove_attributes),
1407                                      fullname, typename_type, tf_none);
1408       }
1409       break;
1410     case DECLTYPE_TYPE:
1411       result = strip_typedefs_expr (DECLTYPE_TYPE_EXPR (t),
1412                                     remove_attributes);
1413       if (result == DECLTYPE_TYPE_EXPR (t))
1414         return t;
1415       else
1416         result = (finish_decltype_type
1417                   (result,
1418                    DECLTYPE_TYPE_ID_EXPR_OR_MEMBER_ACCESS_P (t),
1419                    tf_none));
1420       break;
1421     default:
1422       break;
1423     }
1424
1425   if (!result)
1426       result = TYPE_MAIN_VARIANT (t);
1427   if (TYPE_USER_ALIGN (t) != TYPE_USER_ALIGN (result)
1428       || TYPE_ALIGN (t) != TYPE_ALIGN (result))
1429     {
1430       gcc_assert (TYPE_USER_ALIGN (t));
1431       if (remove_attributes)
1432         *remove_attributes = true;
1433       else
1434         {
1435           if (TYPE_ALIGN (t) == TYPE_ALIGN (result))
1436             result = build_variant_type_copy (result);
1437           else
1438             result = build_aligned_type (result, TYPE_ALIGN (t));
1439           TYPE_USER_ALIGN (result) = true;
1440         }
1441     }
1442   if (TYPE_ATTRIBUTES (t))
1443     {
1444       if (remove_attributes)
1445         result = apply_identity_attributes (result, TYPE_ATTRIBUTES (t),
1446                                             remove_attributes);
1447       else
1448         result = cp_build_type_attribute_variant (result, TYPE_ATTRIBUTES (t));
1449     }
1450   return cp_build_qualified_type (result, cp_type_quals (t));
1451 }
1452
1453 /* Like strip_typedefs above, but works on expressions, so that in
1454
1455    template<class T> struct A
1456    {
1457      typedef T TT;
1458      B<sizeof(TT)> b;
1459    };
1460
1461    sizeof(TT) is replaced by sizeof(T).  */
1462
1463 tree
1464 strip_typedefs_expr (tree t, bool *remove_attributes)
1465 {
1466   unsigned i,n;
1467   tree r, type, *ops;
1468   enum tree_code code;
1469
1470   if (t == NULL_TREE || t == error_mark_node)
1471     return t;
1472
1473   if (DECL_P (t) || CONSTANT_CLASS_P (t))
1474     return t;
1475
1476   /* Some expressions have type operands, so let's handle types here rather
1477      than check TYPE_P in multiple places below.  */
1478   if (TYPE_P (t))
1479     return strip_typedefs (t, remove_attributes);
1480
1481   code = TREE_CODE (t);
1482   switch (code)
1483     {
1484     case IDENTIFIER_NODE:
1485     case TEMPLATE_PARM_INDEX:
1486     case OVERLOAD:
1487     case BASELINK:
1488     case ARGUMENT_PACK_SELECT:
1489       return t;
1490
1491     case TRAIT_EXPR:
1492       {
1493         tree type1 = strip_typedefs (TRAIT_EXPR_TYPE1 (t), remove_attributes);
1494         tree type2 = strip_typedefs (TRAIT_EXPR_TYPE2 (t), remove_attributes);
1495         if (type1 == TRAIT_EXPR_TYPE1 (t)
1496             && type2 == TRAIT_EXPR_TYPE2 (t))
1497           return t;
1498         r = copy_node (t);
1499         TRAIT_EXPR_TYPE1 (t) = type1;
1500         TRAIT_EXPR_TYPE2 (t) = type2;
1501         return r;
1502       }
1503
1504     case TREE_LIST:
1505       {
1506         vec<tree, va_gc> *vec = make_tree_vector ();
1507         bool changed = false;
1508         tree it;
1509         for (it = t; it; it = TREE_CHAIN (it))
1510           {
1511             tree val = strip_typedefs_expr (TREE_VALUE (t), remove_attributes);
1512             vec_safe_push (vec, val);
1513             if (val != TREE_VALUE (t))
1514               changed = true;
1515             gcc_assert (TREE_PURPOSE (it) == NULL_TREE);
1516           }
1517         if (changed)
1518           {
1519             r = NULL_TREE;
1520             FOR_EACH_VEC_ELT_REVERSE (*vec, i, it)
1521               r = tree_cons (NULL_TREE, it, r);
1522           }
1523         else
1524           r = t;
1525         release_tree_vector (vec);
1526         return r;
1527       }
1528
1529     case TREE_VEC:
1530       {
1531         bool changed = false;
1532         vec<tree, va_gc> *vec = make_tree_vector ();
1533         n = TREE_VEC_LENGTH (t);
1534         vec_safe_reserve (vec, n);
1535         for (i = 0; i < n; ++i)
1536           {
1537             tree op = strip_typedefs_expr (TREE_VEC_ELT (t, i),
1538                                            remove_attributes);
1539             vec->quick_push (op);
1540             if (op != TREE_VEC_ELT (t, i))
1541               changed = true;
1542           }
1543         if (changed)
1544           {
1545             r = copy_node (t);
1546             for (i = 0; i < n; ++i)
1547               TREE_VEC_ELT (r, i) = (*vec)[i];
1548             NON_DEFAULT_TEMPLATE_ARGS_COUNT (r)
1549               = NON_DEFAULT_TEMPLATE_ARGS_COUNT (t);
1550           }
1551         else
1552           r = t;
1553         release_tree_vector (vec);
1554         return r;
1555       }
1556
1557     case CONSTRUCTOR:
1558       {
1559         bool changed = false;
1560         vec<constructor_elt, va_gc> *vec
1561           = vec_safe_copy (CONSTRUCTOR_ELTS (t));
1562         n = CONSTRUCTOR_NELTS (t);
1563         type = strip_typedefs (TREE_TYPE (t), remove_attributes);
1564         for (i = 0; i < n; ++i)
1565           {
1566             constructor_elt *e = &(*vec)[i];
1567             tree op = strip_typedefs_expr (e->value, remove_attributes);
1568             if (op != e->value)
1569               {
1570                 changed = true;
1571                 e->value = op;
1572               }
1573             gcc_checking_assert
1574               (e->index == strip_typedefs_expr (e->index, remove_attributes));
1575           }
1576
1577         if (!changed && type == TREE_TYPE (t))
1578           {
1579             vec_free (vec);
1580             return t;
1581           }
1582         else
1583           {
1584             r = copy_node (t);
1585             TREE_TYPE (r) = type;
1586             CONSTRUCTOR_ELTS (r) = vec;
1587             return r;
1588           }
1589       }
1590
1591     case LAMBDA_EXPR:
1592       error ("lambda-expression in a constant expression");
1593       return error_mark_node;
1594
1595     default:
1596       break;
1597     }
1598
1599   gcc_assert (EXPR_P (t));
1600
1601   n = TREE_OPERAND_LENGTH (t);
1602   ops = XALLOCAVEC (tree, n);
1603   type = TREE_TYPE (t);
1604
1605   switch (code)
1606     {
1607     CASE_CONVERT:
1608     case IMPLICIT_CONV_EXPR:
1609     case DYNAMIC_CAST_EXPR:
1610     case STATIC_CAST_EXPR:
1611     case CONST_CAST_EXPR:
1612     case REINTERPRET_CAST_EXPR:
1613     case CAST_EXPR:
1614     case NEW_EXPR:
1615       type = strip_typedefs (type, remove_attributes);
1616       /* fallthrough */
1617
1618     default:
1619       for (i = 0; i < n; ++i)
1620         ops[i] = strip_typedefs_expr (TREE_OPERAND (t, i), remove_attributes);
1621       break;
1622     }
1623
1624   /* If nothing changed, return t.  */
1625   for (i = 0; i < n; ++i)
1626     if (ops[i] != TREE_OPERAND (t, i))
1627       break;
1628   if (i == n && type == TREE_TYPE (t))
1629     return t;
1630
1631   r = copy_node (t);
1632   TREE_TYPE (r) = type;
1633   for (i = 0; i < n; ++i)
1634     TREE_OPERAND (r, i) = ops[i];
1635   return r;
1636 }
1637
1638 /* Makes a copy of BINFO and TYPE, which is to be inherited into a
1639    graph dominated by T.  If BINFO is NULL, TYPE is a dependent base,
1640    and we do a shallow copy.  If BINFO is non-NULL, we do a deep copy.
1641    VIRT indicates whether TYPE is inherited virtually or not.
1642    IGO_PREV points at the previous binfo of the inheritance graph
1643    order chain.  The newly copied binfo's TREE_CHAIN forms this
1644    ordering.
1645
1646    The CLASSTYPE_VBASECLASSES vector of T is constructed in the
1647    correct order. That is in the order the bases themselves should be
1648    constructed in.
1649
1650    The BINFO_INHERITANCE of a virtual base class points to the binfo
1651    of the most derived type. ??? We could probably change this so that
1652    BINFO_INHERITANCE becomes synonymous with BINFO_PRIMARY, and hence
1653    remove a field.  They currently can only differ for primary virtual
1654    virtual bases.  */
1655
1656 tree
1657 copy_binfo (tree binfo, tree type, tree t, tree *igo_prev, int virt)
1658 {
1659   tree new_binfo;
1660
1661   if (virt)
1662     {
1663       /* See if we've already made this virtual base.  */
1664       new_binfo = binfo_for_vbase (type, t);
1665       if (new_binfo)
1666         return new_binfo;
1667     }
1668
1669   new_binfo = make_tree_binfo (binfo ? BINFO_N_BASE_BINFOS (binfo) : 0);
1670   BINFO_TYPE (new_binfo) = type;
1671
1672   /* Chain it into the inheritance graph.  */
1673   TREE_CHAIN (*igo_prev) = new_binfo;
1674   *igo_prev = new_binfo;
1675
1676   if (binfo && !BINFO_DEPENDENT_BASE_P (binfo))
1677     {
1678       int ix;
1679       tree base_binfo;
1680
1681       gcc_assert (SAME_BINFO_TYPE_P (BINFO_TYPE (binfo), type));
1682
1683       BINFO_OFFSET (new_binfo) = BINFO_OFFSET (binfo);
1684       BINFO_VIRTUALS (new_binfo) = BINFO_VIRTUALS (binfo);
1685
1686       /* We do not need to copy the accesses, as they are read only.  */
1687       BINFO_BASE_ACCESSES (new_binfo) = BINFO_BASE_ACCESSES (binfo);
1688
1689       /* Recursively copy base binfos of BINFO.  */
1690       for (ix = 0; BINFO_BASE_ITERATE (binfo, ix, base_binfo); ix++)
1691         {
1692           tree new_base_binfo;
1693           new_base_binfo = copy_binfo (base_binfo, BINFO_TYPE (base_binfo),
1694                                        t, igo_prev,
1695                                        BINFO_VIRTUAL_P (base_binfo));
1696
1697           if (!BINFO_INHERITANCE_CHAIN (new_base_binfo))
1698             BINFO_INHERITANCE_CHAIN (new_base_binfo) = new_binfo;
1699           BINFO_BASE_APPEND (new_binfo, new_base_binfo);
1700         }
1701     }
1702   else
1703     BINFO_DEPENDENT_BASE_P (new_binfo) = 1;
1704
1705   if (virt)
1706     {
1707       /* Push it onto the list after any virtual bases it contains
1708          will have been pushed.  */
1709       CLASSTYPE_VBASECLASSES (t)->quick_push (new_binfo);
1710       BINFO_VIRTUAL_P (new_binfo) = 1;
1711       BINFO_INHERITANCE_CHAIN (new_binfo) = TYPE_BINFO (t);
1712     }
1713
1714   return new_binfo;
1715 }
1716 \f
1717 /* Hashing of lists so that we don't make duplicates.
1718    The entry point is `list_hash_canon'.  */
1719
1720 struct list_proxy
1721 {
1722   tree purpose;
1723   tree value;
1724   tree chain;
1725 };
1726
1727 struct list_hasher : ggc_hasher<tree>
1728 {
1729   typedef list_proxy *compare_type;
1730
1731   static hashval_t hash (tree);
1732   static bool equal (tree, list_proxy *);
1733 };
1734
1735 /* Now here is the hash table.  When recording a list, it is added
1736    to the slot whose index is the hash code mod the table size.
1737    Note that the hash table is used for several kinds of lists.
1738    While all these live in the same table, they are completely independent,
1739    and the hash code is computed differently for each of these.  */
1740
1741 static GTY (()) hash_table<list_hasher> *list_hash_table;
1742
1743 /* Compare ENTRY (an entry in the hash table) with DATA (a list_proxy
1744    for a node we are thinking about adding).  */
1745
1746 bool
1747 list_hasher::equal (tree t, list_proxy *proxy)
1748 {
1749   return (TREE_VALUE (t) == proxy->value
1750           && TREE_PURPOSE (t) == proxy->purpose
1751           && TREE_CHAIN (t) == proxy->chain);
1752 }
1753
1754 /* Compute a hash code for a list (chain of TREE_LIST nodes
1755    with goodies in the TREE_PURPOSE, TREE_VALUE, and bits of the
1756    TREE_COMMON slots), by adding the hash codes of the individual entries.  */
1757
1758 static hashval_t
1759 list_hash_pieces (tree purpose, tree value, tree chain)
1760 {
1761   hashval_t hashcode = 0;
1762
1763   if (chain)
1764     hashcode += TREE_HASH (chain);
1765
1766   if (value)
1767     hashcode += TREE_HASH (value);
1768   else
1769     hashcode += 1007;
1770   if (purpose)
1771     hashcode += TREE_HASH (purpose);
1772   else
1773     hashcode += 1009;
1774   return hashcode;
1775 }
1776
1777 /* Hash an already existing TREE_LIST.  */
1778
1779 hashval_t
1780 list_hasher::hash (tree t)
1781 {
1782   return list_hash_pieces (TREE_PURPOSE (t),
1783                            TREE_VALUE (t),
1784                            TREE_CHAIN (t));
1785 }
1786
1787 /* Given list components PURPOSE, VALUE, AND CHAIN, return the canonical
1788    object for an identical list if one already exists.  Otherwise, build a
1789    new one, and record it as the canonical object.  */
1790
1791 tree
1792 hash_tree_cons (tree purpose, tree value, tree chain)
1793 {
1794   int hashcode = 0;
1795   tree *slot;
1796   struct list_proxy proxy;
1797
1798   /* Hash the list node.  */
1799   hashcode = list_hash_pieces (purpose, value, chain);
1800   /* Create a proxy for the TREE_LIST we would like to create.  We
1801      don't actually create it so as to avoid creating garbage.  */
1802   proxy.purpose = purpose;
1803   proxy.value = value;
1804   proxy.chain = chain;
1805   /* See if it is already in the table.  */
1806   slot = list_hash_table->find_slot_with_hash (&proxy, hashcode, INSERT);
1807   /* If not, create a new node.  */
1808   if (!*slot)
1809     *slot = tree_cons (purpose, value, chain);
1810   return (tree) *slot;
1811 }
1812
1813 /* Constructor for hashed lists.  */
1814
1815 tree
1816 hash_tree_chain (tree value, tree chain)
1817 {
1818   return hash_tree_cons (NULL_TREE, value, chain);
1819 }
1820 \f
1821 void
1822 debug_binfo (tree elem)
1823 {
1824   HOST_WIDE_INT n;
1825   tree virtuals;
1826
1827   fprintf (stderr, "type \"%s\", offset = " HOST_WIDE_INT_PRINT_DEC
1828            "\nvtable type:\n",
1829            TYPE_NAME_STRING (BINFO_TYPE (elem)),
1830            TREE_INT_CST_LOW (BINFO_OFFSET (elem)));
1831   debug_tree (BINFO_TYPE (elem));
1832   if (BINFO_VTABLE (elem))
1833     fprintf (stderr, "vtable decl \"%s\"\n",
1834              IDENTIFIER_POINTER (DECL_NAME (get_vtbl_decl_for_binfo (elem))));
1835   else
1836     fprintf (stderr, "no vtable decl yet\n");
1837   fprintf (stderr, "virtuals:\n");
1838   virtuals = BINFO_VIRTUALS (elem);
1839   n = 0;
1840
1841   while (virtuals)
1842     {
1843       tree fndecl = TREE_VALUE (virtuals);
1844       fprintf (stderr, "%s [%ld =? %ld]\n",
1845                IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (fndecl)),
1846                (long) n, (long) TREE_INT_CST_LOW (DECL_VINDEX (fndecl)));
1847       ++n;
1848       virtuals = TREE_CHAIN (virtuals);
1849     }
1850 }
1851
1852 /* Build a representation for the qualified name SCOPE::NAME.  TYPE is
1853    the type of the result expression, if known, or NULL_TREE if the
1854    resulting expression is type-dependent.  If TEMPLATE_P is true,
1855    NAME is known to be a template because the user explicitly used the
1856    "template" keyword after the "::".
1857
1858    All SCOPE_REFs should be built by use of this function.  */
1859
1860 tree
1861 build_qualified_name (tree type, tree scope, tree name, bool template_p)
1862 {
1863   tree t;
1864   if (type == error_mark_node
1865       || scope == error_mark_node
1866       || name == error_mark_node)
1867     return error_mark_node;
1868   t = build2 (SCOPE_REF, type, scope, name);
1869   QUALIFIED_NAME_IS_TEMPLATE (t) = template_p;
1870   PTRMEM_OK_P (t) = true;
1871   if (type)
1872     t = convert_from_reference (t);
1873   return t;
1874 }
1875
1876 /* Like check_qualified_type, but also check ref-qualifier and exception
1877    specification.  */
1878
1879 static bool
1880 cp_check_qualified_type (const_tree cand, const_tree base, int type_quals,
1881                          cp_ref_qualifier rqual, tree raises)
1882 {
1883   return (check_qualified_type (cand, base, type_quals)
1884           && comp_except_specs (raises, TYPE_RAISES_EXCEPTIONS (cand),
1885                                 ce_exact)
1886           && type_memfn_rqual (cand) == rqual);
1887 }
1888
1889 /* Build the FUNCTION_TYPE or METHOD_TYPE with the ref-qualifier RQUAL.  */
1890
1891 tree
1892 build_ref_qualified_type (tree type, cp_ref_qualifier rqual)
1893 {
1894   tree t;
1895
1896   if (rqual == type_memfn_rqual (type))
1897     return type;
1898
1899   int type_quals = TYPE_QUALS (type);
1900   tree raises = TYPE_RAISES_EXCEPTIONS (type);
1901   for (t = TYPE_MAIN_VARIANT (type); t; t = TYPE_NEXT_VARIANT (t))
1902     if (cp_check_qualified_type (t, type, type_quals, rqual, raises))
1903       return t;
1904
1905   t = build_variant_type_copy (type);
1906   switch (rqual)
1907     {
1908     case REF_QUAL_RVALUE:
1909       FUNCTION_RVALUE_QUALIFIED (t) = 1;
1910       FUNCTION_REF_QUALIFIED (t) = 1;
1911       break;
1912     case REF_QUAL_LVALUE:
1913       FUNCTION_RVALUE_QUALIFIED (t) = 0;
1914       FUNCTION_REF_QUALIFIED (t) = 1;
1915       break;
1916     default:
1917       FUNCTION_REF_QUALIFIED (t) = 0;
1918       break;
1919     }
1920
1921   if (TYPE_STRUCTURAL_EQUALITY_P (type))
1922     /* Propagate structural equality. */
1923     SET_TYPE_STRUCTURAL_EQUALITY (t);
1924   else if (TYPE_CANONICAL (type) != type)
1925     /* Build the underlying canonical type, since it is different
1926        from TYPE. */
1927     TYPE_CANONICAL (t) = build_ref_qualified_type (TYPE_CANONICAL (type),
1928                                                    rqual);
1929   else
1930     /* T is its own canonical type. */
1931     TYPE_CANONICAL (t) = t;
1932
1933   return t;
1934 }
1935
1936 /* Returns nonzero if X is an expression for a (possibly overloaded)
1937    function.  If "f" is a function or function template, "f", "c->f",
1938    "c.f", "C::f", and "f<int>" will all be considered possibly
1939    overloaded functions.  Returns 2 if the function is actually
1940    overloaded, i.e., if it is impossible to know the type of the
1941    function without performing overload resolution.  */
1942
1943 int
1944 is_overloaded_fn (tree x)
1945 {
1946   /* A baselink is also considered an overloaded function.  */
1947   if (TREE_CODE (x) == OFFSET_REF
1948       || TREE_CODE (x) == COMPONENT_REF)
1949     x = TREE_OPERAND (x, 1);
1950   if (BASELINK_P (x))
1951     x = BASELINK_FUNCTIONS (x);
1952   if (TREE_CODE (x) == TEMPLATE_ID_EXPR)
1953     x = TREE_OPERAND (x, 0);
1954   if (DECL_FUNCTION_TEMPLATE_P (OVL_CURRENT (x))
1955       || (TREE_CODE (x) == OVERLOAD && OVL_CHAIN (x)))
1956     return 2;
1957   return  (TREE_CODE (x) == FUNCTION_DECL
1958            || TREE_CODE (x) == OVERLOAD);
1959 }
1960
1961 /* X is the CALL_EXPR_FN of a CALL_EXPR.  If X represents a dependent name
1962    (14.6.2), return the IDENTIFIER_NODE for that name.  Otherwise, return
1963    NULL_TREE.  */
1964
1965 tree
1966 dependent_name (tree x)
1967 {
1968   if (identifier_p (x))
1969     return x;
1970   if (TREE_CODE (x) != COMPONENT_REF
1971       && TREE_CODE (x) != OFFSET_REF
1972       && TREE_CODE (x) != BASELINK
1973       && is_overloaded_fn (x))
1974     return DECL_NAME (get_first_fn (x));
1975   return NULL_TREE;
1976 }
1977
1978 /* Returns true iff X is an expression for an overloaded function
1979    whose type cannot be known without performing overload
1980    resolution.  */
1981
1982 bool
1983 really_overloaded_fn (tree x)
1984 {
1985   return is_overloaded_fn (x) == 2;
1986 }
1987
1988 tree
1989 get_fns (tree from)
1990 {
1991   gcc_assert (is_overloaded_fn (from));
1992   /* A baselink is also considered an overloaded function.  */
1993   if (TREE_CODE (from) == OFFSET_REF
1994       || TREE_CODE (from) == COMPONENT_REF)
1995     from = TREE_OPERAND (from, 1);
1996   if (BASELINK_P (from))
1997     from = BASELINK_FUNCTIONS (from);
1998   if (TREE_CODE (from) == TEMPLATE_ID_EXPR)
1999     from = TREE_OPERAND (from, 0);
2000   return from;
2001 }
2002
2003 tree
2004 get_first_fn (tree from)
2005 {
2006   return OVL_CURRENT (get_fns (from));
2007 }
2008
2009 /* Return a new OVL node, concatenating it with the old one.  */
2010
2011 tree
2012 ovl_cons (tree decl, tree chain)
2013 {
2014   tree result = make_node (OVERLOAD);
2015   TREE_TYPE (result) = unknown_type_node;
2016   OVL_FUNCTION (result) = decl;
2017   TREE_CHAIN (result) = chain;
2018
2019   return result;
2020 }
2021
2022 /* Build a new overloaded function. If this is the first one,
2023    just return it; otherwise, ovl_cons the _DECLs */
2024
2025 tree
2026 build_overload (tree decl, tree chain)
2027 {
2028   if (! chain && TREE_CODE (decl) != TEMPLATE_DECL)
2029     return decl;
2030   return ovl_cons (decl, chain);
2031 }
2032
2033 /* Return the scope where the overloaded functions OVL were found.  */
2034
2035 tree
2036 ovl_scope (tree ovl)
2037 {
2038   if (TREE_CODE (ovl) == OFFSET_REF
2039       || TREE_CODE (ovl) == COMPONENT_REF)
2040     ovl = TREE_OPERAND (ovl, 1);
2041   if (TREE_CODE (ovl) == BASELINK)
2042     return BINFO_TYPE (BASELINK_BINFO (ovl));
2043   if (TREE_CODE (ovl) == TEMPLATE_ID_EXPR)
2044     ovl = TREE_OPERAND (ovl, 0);
2045   /* Skip using-declarations.  */
2046   while (TREE_CODE (ovl) == OVERLOAD && OVL_USED (ovl) && OVL_CHAIN (ovl))
2047     ovl = OVL_CHAIN (ovl);
2048   return CP_DECL_CONTEXT (OVL_CURRENT (ovl));
2049 }
2050
2051 /* Return TRUE if FN is a non-static member function, FALSE otherwise.
2052    This function looks into BASELINK and OVERLOAD nodes.  */
2053
2054 bool
2055 non_static_member_function_p (tree fn)
2056 {
2057   if (fn == NULL_TREE)
2058     return false;
2059
2060   if (is_overloaded_fn (fn))
2061     fn = get_first_fn (fn);
2062
2063   return (DECL_P (fn)
2064           && DECL_NONSTATIC_MEMBER_FUNCTION_P (fn));
2065 }
2066
2067 \f
2068 #define PRINT_RING_SIZE 4
2069
2070 static const char *
2071 cxx_printable_name_internal (tree decl, int v, bool translate)
2072 {
2073   static unsigned int uid_ring[PRINT_RING_SIZE];
2074   static char *print_ring[PRINT_RING_SIZE];
2075   static bool trans_ring[PRINT_RING_SIZE];
2076   static int ring_counter;
2077   int i;
2078
2079   /* Only cache functions.  */
2080   if (v < 2
2081       || TREE_CODE (decl) != FUNCTION_DECL
2082       || DECL_LANG_SPECIFIC (decl) == 0)
2083     return lang_decl_name (decl, v, translate);
2084
2085   /* See if this print name is lying around.  */
2086   for (i = 0; i < PRINT_RING_SIZE; i++)
2087     if (uid_ring[i] == DECL_UID (decl) && translate == trans_ring[i])
2088       /* yes, so return it.  */
2089       return print_ring[i];
2090
2091   if (++ring_counter == PRINT_RING_SIZE)
2092     ring_counter = 0;
2093
2094   if (current_function_decl != NULL_TREE)
2095     {
2096       /* There may be both translated and untranslated versions of the
2097          name cached.  */
2098       for (i = 0; i < 2; i++)
2099         {
2100           if (uid_ring[ring_counter] == DECL_UID (current_function_decl))
2101             ring_counter += 1;
2102           if (ring_counter == PRINT_RING_SIZE)
2103             ring_counter = 0;
2104         }
2105       gcc_assert (uid_ring[ring_counter] != DECL_UID (current_function_decl));
2106     }
2107
2108   free (print_ring[ring_counter]);
2109
2110   print_ring[ring_counter] = xstrdup (lang_decl_name (decl, v, translate));
2111   uid_ring[ring_counter] = DECL_UID (decl);
2112   trans_ring[ring_counter] = translate;
2113   return print_ring[ring_counter];
2114 }
2115
2116 const char *
2117 cxx_printable_name (tree decl, int v)
2118 {
2119   return cxx_printable_name_internal (decl, v, false);
2120 }
2121
2122 const char *
2123 cxx_printable_name_translate (tree decl, int v)
2124 {
2125   return cxx_printable_name_internal (decl, v, true);
2126 }
2127 \f
2128 /* Build the FUNCTION_TYPE or METHOD_TYPE which may throw exceptions
2129    listed in RAISES.  */
2130
2131 tree
2132 build_exception_variant (tree type, tree raises)
2133 {
2134   tree v;
2135   int type_quals;
2136
2137   if (comp_except_specs (raises, TYPE_RAISES_EXCEPTIONS (type), ce_exact))
2138     return type;
2139
2140   type_quals = TYPE_QUALS (type);
2141   cp_ref_qualifier rqual = type_memfn_rqual (type);
2142   for (v = TYPE_MAIN_VARIANT (type); v; v = TYPE_NEXT_VARIANT (v))
2143     if (cp_check_qualified_type (v, type, type_quals, rqual, raises))
2144       return v;
2145
2146   /* Need to build a new variant.  */
2147   v = build_variant_type_copy (type);
2148   TYPE_RAISES_EXCEPTIONS (v) = raises;
2149   return v;
2150 }
2151
2152 /* Given a TEMPLATE_TEMPLATE_PARM node T, create a new
2153    BOUND_TEMPLATE_TEMPLATE_PARM bound with NEWARGS as its template
2154    arguments.  */
2155
2156 tree
2157 bind_template_template_parm (tree t, tree newargs)
2158 {
2159   tree decl = TYPE_NAME (t);
2160   tree t2;
2161
2162   t2 = cxx_make_type (BOUND_TEMPLATE_TEMPLATE_PARM);
2163   decl = build_decl (input_location,
2164                      TYPE_DECL, DECL_NAME (decl), NULL_TREE);
2165
2166   /* These nodes have to be created to reflect new TYPE_DECL and template
2167      arguments.  */
2168   TEMPLATE_TYPE_PARM_INDEX (t2) = copy_node (TEMPLATE_TYPE_PARM_INDEX (t));
2169   TEMPLATE_PARM_DECL (TEMPLATE_TYPE_PARM_INDEX (t2)) = decl;
2170   TEMPLATE_TEMPLATE_PARM_TEMPLATE_INFO (t2)
2171     = build_template_info (TEMPLATE_TEMPLATE_PARM_TEMPLATE_DECL (t), newargs);
2172
2173   TREE_TYPE (decl) = t2;
2174   TYPE_NAME (t2) = decl;
2175   TYPE_STUB_DECL (t2) = decl;
2176   TYPE_SIZE (t2) = 0;
2177   SET_TYPE_STRUCTURAL_EQUALITY (t2);
2178
2179   return t2;
2180 }
2181
2182 /* Called from count_trees via walk_tree.  */
2183
2184 static tree
2185 count_trees_r (tree *tp, int *walk_subtrees, void *data)
2186 {
2187   ++*((int *) data);
2188
2189   if (TYPE_P (*tp))
2190     *walk_subtrees = 0;
2191
2192   return NULL_TREE;
2193 }
2194
2195 /* Debugging function for measuring the rough complexity of a tree
2196    representation.  */
2197
2198 int
2199 count_trees (tree t)
2200 {
2201   int n_trees = 0;
2202   cp_walk_tree_without_duplicates (&t, count_trees_r, &n_trees);
2203   return n_trees;
2204 }
2205
2206 /* Called from verify_stmt_tree via walk_tree.  */
2207
2208 static tree
2209 verify_stmt_tree_r (tree* tp, int * /*walk_subtrees*/, void* data)
2210 {
2211   tree t = *tp;
2212   hash_table<pointer_hash <tree_node> > *statements
2213       = static_cast <hash_table<pointer_hash <tree_node> > *> (data);
2214   tree_node **slot;
2215
2216   if (!STATEMENT_CODE_P (TREE_CODE (t)))
2217     return NULL_TREE;
2218
2219   /* If this statement is already present in the hash table, then
2220      there is a circularity in the statement tree.  */
2221   gcc_assert (!statements->find (t));
2222
2223   slot = statements->find_slot (t, INSERT);
2224   *slot = t;
2225
2226   return NULL_TREE;
2227 }
2228
2229 /* Debugging function to check that the statement T has not been
2230    corrupted.  For now, this function simply checks that T contains no
2231    circularities.  */
2232
2233 void
2234 verify_stmt_tree (tree t)
2235 {
2236   hash_table<pointer_hash <tree_node> > statements (37);
2237   cp_walk_tree (&t, verify_stmt_tree_r, &statements, NULL);
2238 }
2239
2240 /* Check if the type T depends on a type with no linkage and if so, return
2241    it.  If RELAXED_P then do not consider a class type declared within
2242    a vague-linkage function to have no linkage.  */
2243
2244 tree
2245 no_linkage_check (tree t, bool relaxed_p)
2246 {
2247   tree r;
2248
2249   /* There's no point in checking linkage on template functions; we
2250      can't know their complete types.  */
2251   if (processing_template_decl)
2252     return NULL_TREE;
2253
2254   switch (TREE_CODE (t))
2255     {
2256     case RECORD_TYPE:
2257       if (TYPE_PTRMEMFUNC_P (t))
2258         goto ptrmem;
2259       /* Lambda types that don't have mangling scope have no linkage.  We
2260          check CLASSTYPE_LAMBDA_EXPR for error_mark_node because
2261          when we get here from pushtag none of the lambda information is
2262          set up yet, so we want to assume that the lambda has linkage and
2263          fix it up later if not.  */
2264       if (CLASSTYPE_LAMBDA_EXPR (t)
2265           && CLASSTYPE_LAMBDA_EXPR (t) != error_mark_node
2266           && LAMBDA_TYPE_EXTRA_SCOPE (t) == NULL_TREE)
2267         return t;
2268       /* Fall through.  */
2269     case UNION_TYPE:
2270       if (!CLASS_TYPE_P (t))
2271         return NULL_TREE;
2272       /* Fall through.  */
2273     case ENUMERAL_TYPE:
2274       /* Only treat anonymous types as having no linkage if they're at
2275          namespace scope.  This is core issue 966.  */
2276       if (TYPE_ANONYMOUS_P (t) && TYPE_NAMESPACE_SCOPE_P (t))
2277         return t;
2278
2279       for (r = CP_TYPE_CONTEXT (t); ; )
2280         {
2281           /* If we're a nested type of a !TREE_PUBLIC class, we might not
2282              have linkage, or we might just be in an anonymous namespace.
2283              If we're in a TREE_PUBLIC class, we have linkage.  */
2284           if (TYPE_P (r) && !TREE_PUBLIC (TYPE_NAME (r)))
2285             return no_linkage_check (TYPE_CONTEXT (t), relaxed_p);
2286           else if (TREE_CODE (r) == FUNCTION_DECL)
2287             {
2288               if (!relaxed_p || !vague_linkage_p (r))
2289                 return t;
2290               else
2291                 r = CP_DECL_CONTEXT (r);
2292             }
2293           else
2294             break;
2295         }
2296
2297       return NULL_TREE;
2298
2299     case ARRAY_TYPE:
2300     case POINTER_TYPE:
2301     case REFERENCE_TYPE:
2302     case VECTOR_TYPE:
2303       return no_linkage_check (TREE_TYPE (t), relaxed_p);
2304
2305     case OFFSET_TYPE:
2306     ptrmem:
2307       r = no_linkage_check (TYPE_PTRMEM_POINTED_TO_TYPE (t),
2308                             relaxed_p);
2309       if (r)
2310         return r;
2311       return no_linkage_check (TYPE_PTRMEM_CLASS_TYPE (t), relaxed_p);
2312
2313     case METHOD_TYPE:
2314       r = no_linkage_check (TYPE_METHOD_BASETYPE (t), relaxed_p);
2315       if (r)
2316         return r;
2317       /* Fall through.  */
2318     case FUNCTION_TYPE:
2319       {
2320         tree parm;
2321         for (parm = TYPE_ARG_TYPES (t);
2322              parm && parm != void_list_node;
2323              parm = TREE_CHAIN (parm))
2324           {
2325             r = no_linkage_check (TREE_VALUE (parm), relaxed_p);
2326             if (r)
2327               return r;
2328           }
2329         return no_linkage_check (TREE_TYPE (t), relaxed_p);
2330       }
2331
2332     default:
2333       return NULL_TREE;
2334     }
2335 }
2336
2337 extern int depth_reached;
2338
2339 void
2340 cxx_print_statistics (void)
2341 {
2342   print_search_statistics ();
2343   print_class_statistics ();
2344   print_template_statistics ();
2345   if (GATHER_STATISTICS)
2346     fprintf (stderr, "maximum template instantiation depth reached: %d\n",
2347              depth_reached);
2348 }
2349
2350 /* Return, as an INTEGER_CST node, the number of elements for TYPE
2351    (which is an ARRAY_TYPE).  This counts only elements of the top
2352    array.  */
2353
2354 tree
2355 array_type_nelts_top (tree type)
2356 {
2357   return fold_build2_loc (input_location,
2358                       PLUS_EXPR, sizetype,
2359                       array_type_nelts (type),
2360                       size_one_node);
2361 }
2362
2363 /* Return, as an INTEGER_CST node, the number of elements for TYPE
2364    (which is an ARRAY_TYPE).  This one is a recursive count of all
2365    ARRAY_TYPEs that are clumped together.  */
2366
2367 tree
2368 array_type_nelts_total (tree type)
2369 {
2370   tree sz = array_type_nelts_top (type);
2371   type = TREE_TYPE (type);
2372   while (TREE_CODE (type) == ARRAY_TYPE)
2373     {
2374       tree n = array_type_nelts_top (type);
2375       sz = fold_build2_loc (input_location,
2376                         MULT_EXPR, sizetype, sz, n);
2377       type = TREE_TYPE (type);
2378     }
2379   return sz;
2380 }
2381
2382 /* Called from break_out_target_exprs via mapcar.  */
2383
2384 static tree
2385 bot_manip (tree* tp, int* walk_subtrees, void* data)
2386 {
2387   splay_tree target_remap = ((splay_tree) data);
2388   tree t = *tp;
2389
2390   if (!TYPE_P (t) && TREE_CONSTANT (t) && !TREE_SIDE_EFFECTS (t))
2391     {
2392       /* There can't be any TARGET_EXPRs or their slot variables below this
2393          point.  But we must make a copy, in case subsequent processing
2394          alters any part of it.  For example, during gimplification a cast
2395          of the form (T) &X::f (where "f" is a member function) will lead
2396          to replacing the PTRMEM_CST for &X::f with a VAR_DECL.  */
2397       *walk_subtrees = 0;
2398       *tp = unshare_expr (t);
2399       return NULL_TREE;
2400     }
2401   if (TREE_CODE (t) == TARGET_EXPR)
2402     {
2403       tree u;
2404
2405       if (TREE_CODE (TREE_OPERAND (t, 1)) == AGGR_INIT_EXPR)
2406         {
2407           u = build_cplus_new (TREE_TYPE (t), TREE_OPERAND (t, 1),
2408                                tf_warning_or_error);
2409           if (AGGR_INIT_ZERO_FIRST (TREE_OPERAND (t, 1)))
2410             AGGR_INIT_ZERO_FIRST (TREE_OPERAND (u, 1)) = true;
2411         }
2412       else
2413         u = build_target_expr_with_type (TREE_OPERAND (t, 1), TREE_TYPE (t),
2414                                          tf_warning_or_error);
2415
2416       TARGET_EXPR_IMPLICIT_P (u) = TARGET_EXPR_IMPLICIT_P (t);
2417       TARGET_EXPR_LIST_INIT_P (u) = TARGET_EXPR_LIST_INIT_P (t);
2418       TARGET_EXPR_DIRECT_INIT_P (u) = TARGET_EXPR_DIRECT_INIT_P (t);
2419
2420       /* Map the old variable to the new one.  */
2421       splay_tree_insert (target_remap,
2422                          (splay_tree_key) TREE_OPERAND (t, 0),
2423                          (splay_tree_value) TREE_OPERAND (u, 0));
2424
2425       TREE_OPERAND (u, 1) = break_out_target_exprs (TREE_OPERAND (u, 1));
2426
2427       /* Replace the old expression with the new version.  */
2428       *tp = u;
2429       /* We don't have to go below this point; the recursive call to
2430          break_out_target_exprs will have handled anything below this
2431          point.  */
2432       *walk_subtrees = 0;
2433       return NULL_TREE;
2434     }
2435
2436   /* Make a copy of this node.  */
2437   t = copy_tree_r (tp, walk_subtrees, NULL);
2438   if (TREE_CODE (*tp) == CALL_EXPR)
2439     {
2440       set_flags_from_callee (*tp);
2441
2442       /* builtin_LINE and builtin_FILE get the location where the default
2443          argument is expanded, not where the call was written.  */
2444       tree callee = get_callee_fndecl (*tp);
2445       if (callee && DECL_BUILT_IN (callee))
2446         switch (DECL_FUNCTION_CODE (callee))
2447           {
2448           case BUILT_IN_FILE:
2449           case BUILT_IN_LINE:
2450             SET_EXPR_LOCATION (*tp, input_location);
2451           default:
2452             break;
2453           }
2454     }
2455   return t;
2456 }
2457
2458 /* Replace all remapped VAR_DECLs in T with their new equivalents.
2459    DATA is really a splay-tree mapping old variables to new
2460    variables.  */
2461
2462 static tree
2463 bot_replace (tree* t, int* /*walk_subtrees*/, void* data)
2464 {
2465   splay_tree target_remap = ((splay_tree) data);
2466
2467   if (VAR_P (*t))
2468     {
2469       splay_tree_node n = splay_tree_lookup (target_remap,
2470                                              (splay_tree_key) *t);
2471       if (n)
2472         *t = (tree) n->value;
2473     }
2474   else if (TREE_CODE (*t) == PARM_DECL
2475            && DECL_NAME (*t) == this_identifier
2476            && !DECL_CONTEXT (*t))
2477     {
2478       /* In an NSDMI we need to replace the 'this' parameter we used for
2479          parsing with the real one for this function.  */
2480       *t = current_class_ptr;
2481     }
2482   else if (TREE_CODE (*t) == CONVERT_EXPR
2483            && CONVERT_EXPR_VBASE_PATH (*t))
2484     {
2485       /* In an NSDMI build_base_path defers building conversions to virtual
2486          bases, and we handle it here.  */
2487       tree basetype = TYPE_MAIN_VARIANT (TREE_TYPE (TREE_TYPE (*t)));
2488       vec<tree, va_gc> *vbases = CLASSTYPE_VBASECLASSES (current_class_type);
2489       int i; tree binfo;
2490       FOR_EACH_VEC_SAFE_ELT (vbases, i, binfo)
2491         if (BINFO_TYPE (binfo) == basetype)
2492           break;
2493       *t = build_base_path (PLUS_EXPR, TREE_OPERAND (*t, 0), binfo, true,
2494                             tf_warning_or_error);
2495     }
2496
2497   return NULL_TREE;
2498 }
2499
2500 /* When we parse a default argument expression, we may create
2501    temporary variables via TARGET_EXPRs.  When we actually use the
2502    default-argument expression, we make a copy of the expression
2503    and replace the temporaries with appropriate local versions.  */
2504
2505 tree
2506 break_out_target_exprs (tree t)
2507 {
2508   static int target_remap_count;
2509   static splay_tree target_remap;
2510
2511   if (!target_remap_count++)
2512     target_remap = splay_tree_new (splay_tree_compare_pointers,
2513                                    /*splay_tree_delete_key_fn=*/NULL,
2514                                    /*splay_tree_delete_value_fn=*/NULL);
2515   cp_walk_tree (&t, bot_manip, target_remap, NULL);
2516   cp_walk_tree (&t, bot_replace, target_remap, NULL);
2517
2518   if (!--target_remap_count)
2519     {
2520       splay_tree_delete (target_remap);
2521       target_remap = NULL;
2522     }
2523
2524   return t;
2525 }
2526
2527 /* Build an expression for the subobject of OBJ at CONSTRUCTOR index INDEX,
2528    which we expect to have type TYPE.  */
2529
2530 tree
2531 build_ctor_subob_ref (tree index, tree type, tree obj)
2532 {
2533   if (index == NULL_TREE)
2534     /* Can't refer to a particular member of a vector.  */
2535     obj = NULL_TREE;
2536   else if (TREE_CODE (index) == INTEGER_CST)
2537     obj = cp_build_array_ref (input_location, obj, index, tf_none);
2538   else
2539     obj = build_class_member_access_expr (obj, index, NULL_TREE,
2540                                           /*reference*/false, tf_none);
2541   if (obj)
2542     gcc_assert (same_type_ignoring_top_level_qualifiers_p (type,
2543                                                            TREE_TYPE (obj)));
2544   return obj;
2545 }
2546
2547 /* Like substitute_placeholder_in_expr, but handle C++ tree codes and
2548    build up subexpressions as we go deeper.  */
2549
2550 static tree
2551 replace_placeholders_r (tree* t, int* walk_subtrees, void* data_)
2552 {
2553   tree obj = static_cast<tree>(data_);
2554
2555   if (TREE_CONSTANT (*t))
2556     {
2557       *walk_subtrees = false;
2558       return NULL_TREE;
2559     }
2560
2561   switch (TREE_CODE (*t))
2562     {
2563     case PLACEHOLDER_EXPR:
2564       gcc_assert (same_type_ignoring_top_level_qualifiers_p
2565                   (TREE_TYPE (*t), TREE_TYPE (obj)));
2566       *t = obj;
2567       *walk_subtrees = false;
2568       break;
2569
2570     case TARGET_EXPR:
2571       /* Don't mess with placeholders in an unrelated object.  */
2572       *walk_subtrees = false;
2573       break;
2574
2575     case CONSTRUCTOR:
2576       {
2577         constructor_elt *ce;
2578         vec<constructor_elt,va_gc> *v = CONSTRUCTOR_ELTS (*t);
2579         for (unsigned i = 0; vec_safe_iterate (v, i, &ce); ++i)
2580           {
2581             tree *valp = &ce->value;
2582             tree type = TREE_TYPE (*valp);
2583             tree subob = obj;
2584
2585             if (TREE_CODE (*valp) == CONSTRUCTOR
2586                 && AGGREGATE_TYPE_P (type))
2587               {
2588                 subob = build_ctor_subob_ref (ce->index, type, obj);
2589                 if (TREE_CODE (*valp) == TARGET_EXPR)
2590                   valp = &TARGET_EXPR_INITIAL (*valp);
2591               }
2592
2593             cp_walk_tree (valp, replace_placeholders_r,
2594                           subob, NULL);
2595           }
2596         *walk_subtrees = false;
2597         break;
2598       }
2599
2600     default:
2601       break;
2602     }
2603
2604   return NULL_TREE;
2605 }
2606
2607 tree
2608 replace_placeholders (tree exp, tree obj)
2609 {
2610   tree *tp = &exp;
2611   if (TREE_CODE (exp) == TARGET_EXPR)
2612     tp = &TARGET_EXPR_INITIAL (exp);
2613   cp_walk_tree (tp, replace_placeholders_r, obj, NULL);
2614   return exp;
2615 }
2616
2617 /* Similar to `build_nt', but for template definitions of dependent
2618    expressions  */
2619
2620 tree
2621 build_min_nt_loc (location_t loc, enum tree_code code, ...)
2622 {
2623   tree t;
2624   int length;
2625   int i;
2626   va_list p;
2627
2628   gcc_assert (TREE_CODE_CLASS (code) != tcc_vl_exp);
2629
2630   va_start (p, code);
2631
2632   t = make_node (code);
2633   SET_EXPR_LOCATION (t, loc);
2634   length = TREE_CODE_LENGTH (code);
2635
2636   for (i = 0; i < length; i++)
2637     {
2638       tree x = va_arg (p, tree);
2639       TREE_OPERAND (t, i) = x;
2640     }
2641
2642   va_end (p);
2643   return t;
2644 }
2645
2646
2647 /* Similar to `build', but for template definitions.  */
2648
2649 tree
2650 build_min (enum tree_code code, tree tt, ...)
2651 {
2652   tree t;
2653   int length;
2654   int i;
2655   va_list p;
2656
2657   gcc_assert (TREE_CODE_CLASS (code) != tcc_vl_exp);
2658
2659   va_start (p, tt);
2660
2661   t = make_node (code);
2662   length = TREE_CODE_LENGTH (code);
2663   TREE_TYPE (t) = tt;
2664
2665   for (i = 0; i < length; i++)
2666     {
2667       tree x = va_arg (p, tree);
2668       TREE_OPERAND (t, i) = x;
2669       if (x && !TYPE_P (x) && TREE_SIDE_EFFECTS (x))
2670         TREE_SIDE_EFFECTS (t) = 1;
2671     }
2672
2673   va_end (p);
2674   return t;
2675 }
2676
2677 /* Similar to `build', but for template definitions of non-dependent
2678    expressions. NON_DEP is the non-dependent expression that has been
2679    built.  */
2680
2681 tree
2682 build_min_non_dep (enum tree_code code, tree non_dep, ...)
2683 {
2684   tree t;
2685   int length;
2686   int i;
2687   va_list p;
2688
2689   gcc_assert (TREE_CODE_CLASS (code) != tcc_vl_exp);
2690
2691   va_start (p, non_dep);
2692
2693   if (REFERENCE_REF_P (non_dep))
2694     non_dep = TREE_OPERAND (non_dep, 0);
2695
2696   t = make_node (code);
2697   length = TREE_CODE_LENGTH (code);
2698   TREE_TYPE (t) = TREE_TYPE (non_dep);
2699   TREE_SIDE_EFFECTS (t) = TREE_SIDE_EFFECTS (non_dep);
2700
2701   for (i = 0; i < length; i++)
2702     {
2703       tree x = va_arg (p, tree);
2704       TREE_OPERAND (t, i) = x;
2705     }
2706
2707   if (code == COMPOUND_EXPR && TREE_CODE (non_dep) != COMPOUND_EXPR)
2708     /* This should not be considered a COMPOUND_EXPR, because it
2709        resolves to an overload.  */
2710     COMPOUND_EXPR_OVERLOADED (t) = 1;
2711
2712   va_end (p);
2713   return convert_from_reference (t);
2714 }
2715
2716 /* Similar to `build_nt_call_vec', but for template definitions of
2717    non-dependent expressions. NON_DEP is the non-dependent expression
2718    that has been built.  */
2719
2720 tree
2721 build_min_non_dep_call_vec (tree non_dep, tree fn, vec<tree, va_gc> *argvec)
2722 {
2723   tree t = build_nt_call_vec (fn, argvec);
2724   if (REFERENCE_REF_P (non_dep))
2725     non_dep = TREE_OPERAND (non_dep, 0);
2726   TREE_TYPE (t) = TREE_TYPE (non_dep);
2727   TREE_SIDE_EFFECTS (t) = TREE_SIDE_EFFECTS (non_dep);
2728   return convert_from_reference (t);
2729 }
2730
2731 tree
2732 get_type_decl (tree t)
2733 {
2734   if (TREE_CODE (t) == TYPE_DECL)
2735     return t;
2736   if (TYPE_P (t))
2737     return TYPE_STUB_DECL (t);
2738   gcc_assert (t == error_mark_node);
2739   return t;
2740 }
2741
2742 /* Returns the namespace that contains DECL, whether directly or
2743    indirectly.  */
2744
2745 tree
2746 decl_namespace_context (tree decl)
2747 {
2748   while (1)
2749     {
2750       if (TREE_CODE (decl) == NAMESPACE_DECL)
2751         return decl;
2752       else if (TYPE_P (decl))
2753         decl = CP_DECL_CONTEXT (TYPE_MAIN_DECL (decl));
2754       else
2755         decl = CP_DECL_CONTEXT (decl);
2756     }
2757 }
2758
2759 /* Returns true if decl is within an anonymous namespace, however deeply
2760    nested, or false otherwise.  */
2761
2762 bool
2763 decl_anon_ns_mem_p (const_tree decl)
2764 {
2765   while (1)
2766     {
2767       if (decl == NULL_TREE || decl == error_mark_node)
2768         return false;
2769       if (TREE_CODE (decl) == NAMESPACE_DECL
2770           && DECL_NAME (decl) == NULL_TREE)
2771         return true;
2772       /* Classes and namespaces inside anonymous namespaces have
2773          TREE_PUBLIC == 0, so we can shortcut the search.  */
2774       else if (TYPE_P (decl))
2775         return (TREE_PUBLIC (TYPE_MAIN_DECL (decl)) == 0);
2776       else if (TREE_CODE (decl) == NAMESPACE_DECL)
2777         return (TREE_PUBLIC (decl) == 0);
2778       else
2779         decl = DECL_CONTEXT (decl);
2780     }
2781 }
2782
2783 /* Subroutine of cp_tree_equal: t1 and t2 are the CALL_EXPR_FNs of two
2784    CALL_EXPRS.  Return whether they are equivalent.  */
2785
2786 static bool
2787 called_fns_equal (tree t1, tree t2)
2788 {
2789   /* Core 1321: dependent names are equivalent even if the overload sets
2790      are different.  But do compare explicit template arguments.  */
2791   tree name1 = dependent_name (t1);
2792   tree name2 = dependent_name (t2);
2793   if (name1 || name2)
2794     {
2795       tree targs1 = NULL_TREE, targs2 = NULL_TREE;
2796
2797       if (name1 != name2)
2798         return false;
2799
2800       if (TREE_CODE (t1) == TEMPLATE_ID_EXPR)
2801         targs1 = TREE_OPERAND (t1, 1);
2802       if (TREE_CODE (t2) == TEMPLATE_ID_EXPR)
2803         targs2 = TREE_OPERAND (t2, 1);
2804       return cp_tree_equal (targs1, targs2);
2805     }
2806   else
2807     return cp_tree_equal (t1, t2);
2808 }
2809
2810 /* Return truthvalue of whether T1 is the same tree structure as T2.
2811    Return 1 if they are the same. Return 0 if they are different.  */
2812
2813 bool
2814 cp_tree_equal (tree t1, tree t2)
2815 {
2816   enum tree_code code1, code2;
2817
2818   if (t1 == t2)
2819     return true;
2820   if (!t1 || !t2)
2821     return false;
2822
2823   code1 = TREE_CODE (t1);
2824   code2 = TREE_CODE (t2);
2825
2826   if (code1 != code2)
2827     return false;
2828
2829   switch (code1)
2830     {
2831     case VOID_CST:
2832       /* There's only a single VOID_CST node, so we should never reach
2833          here.  */
2834       gcc_unreachable ();
2835
2836     case INTEGER_CST:
2837       return tree_int_cst_equal (t1, t2);
2838
2839     case REAL_CST:
2840       return REAL_VALUES_EQUAL (TREE_REAL_CST (t1), TREE_REAL_CST (t2));
2841
2842     case STRING_CST:
2843       return TREE_STRING_LENGTH (t1) == TREE_STRING_LENGTH (t2)
2844         && !memcmp (TREE_STRING_POINTER (t1), TREE_STRING_POINTER (t2),
2845                     TREE_STRING_LENGTH (t1));
2846
2847     case FIXED_CST:
2848       return FIXED_VALUES_IDENTICAL (TREE_FIXED_CST (t1),
2849                                      TREE_FIXED_CST (t2));
2850
2851     case COMPLEX_CST:
2852       return cp_tree_equal (TREE_REALPART (t1), TREE_REALPART (t2))
2853         && cp_tree_equal (TREE_IMAGPART (t1), TREE_IMAGPART (t2));
2854
2855     case VECTOR_CST:
2856       return operand_equal_p (t1, t2, OEP_ONLY_CONST);
2857
2858     case CONSTRUCTOR:
2859       /* We need to do this when determining whether or not two
2860          non-type pointer to member function template arguments
2861          are the same.  */
2862       if (!same_type_p (TREE_TYPE (t1), TREE_TYPE (t2))
2863           || CONSTRUCTOR_NELTS (t1) != CONSTRUCTOR_NELTS (t2))
2864         return false;
2865       {
2866         tree field, value;
2867         unsigned int i;
2868         FOR_EACH_CONSTRUCTOR_ELT (CONSTRUCTOR_ELTS (t1), i, field, value)
2869           {
2870             constructor_elt *elt2 = CONSTRUCTOR_ELT (t2, i);
2871             if (!cp_tree_equal (field, elt2->index)
2872                 || !cp_tree_equal (value, elt2->value))
2873               return false;
2874           }
2875       }
2876       return true;
2877
2878     case TREE_LIST:
2879       if (!cp_tree_equal (TREE_PURPOSE (t1), TREE_PURPOSE (t2)))
2880         return false;
2881       if (!cp_tree_equal (TREE_VALUE (t1), TREE_VALUE (t2)))
2882         return false;
2883       return cp_tree_equal (TREE_CHAIN (t1), TREE_CHAIN (t2));
2884
2885     case SAVE_EXPR:
2886       return cp_tree_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
2887
2888     case CALL_EXPR:
2889       {
2890         tree arg1, arg2;
2891         call_expr_arg_iterator iter1, iter2;
2892         if (!called_fns_equal (CALL_EXPR_FN (t1), CALL_EXPR_FN (t2)))
2893           return false;
2894         for (arg1 = first_call_expr_arg (t1, &iter1),
2895                arg2 = first_call_expr_arg (t2, &iter2);
2896              arg1 && arg2;
2897              arg1 = next_call_expr_arg (&iter1),
2898                arg2 = next_call_expr_arg (&iter2))
2899           if (!cp_tree_equal (arg1, arg2))
2900             return false;
2901         if (arg1 || arg2)
2902           return false;
2903         return true;
2904       }
2905
2906     case TARGET_EXPR:
2907       {
2908         tree o1 = TREE_OPERAND (t1, 0);
2909         tree o2 = TREE_OPERAND (t2, 0);
2910
2911         /* Special case: if either target is an unallocated VAR_DECL,
2912            it means that it's going to be unified with whatever the
2913            TARGET_EXPR is really supposed to initialize, so treat it
2914            as being equivalent to anything.  */
2915         if (VAR_P (o1) && DECL_NAME (o1) == NULL_TREE
2916             && !DECL_RTL_SET_P (o1))
2917           /*Nop*/;
2918         else if (VAR_P (o2) && DECL_NAME (o2) == NULL_TREE
2919                  && !DECL_RTL_SET_P (o2))
2920           /*Nop*/;
2921         else if (!cp_tree_equal (o1, o2))
2922           return false;
2923
2924         return cp_tree_equal (TREE_OPERAND (t1, 1), TREE_OPERAND (t2, 1));
2925       }
2926
2927     case WITH_CLEANUP_EXPR:
2928       if (!cp_tree_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0)))
2929         return false;
2930       return cp_tree_equal (TREE_OPERAND (t1, 1), TREE_OPERAND (t1, 1));
2931
2932     case COMPONENT_REF:
2933       if (TREE_OPERAND (t1, 1) != TREE_OPERAND (t2, 1))
2934         return false;
2935       return cp_tree_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
2936
2937     case PARM_DECL:
2938       /* For comparing uses of parameters in late-specified return types
2939          with an out-of-class definition of the function, but can also come
2940          up for expressions that involve 'this' in a member function
2941          template.  */
2942
2943       if (comparing_specializations)
2944         /* When comparing hash table entries, only an exact match is
2945            good enough; we don't want to replace 'this' with the
2946            version from another function.  */
2947         return false;
2948
2949       if (same_type_p (TREE_TYPE (t1), TREE_TYPE (t2)))
2950         {
2951           if (DECL_ARTIFICIAL (t1) ^ DECL_ARTIFICIAL (t2))
2952             return false;
2953           if (DECL_ARTIFICIAL (t1)
2954               || (DECL_PARM_LEVEL (t1) == DECL_PARM_LEVEL (t2)
2955                   && DECL_PARM_INDEX (t1) == DECL_PARM_INDEX (t2)))
2956             return true;
2957         }
2958       return false;
2959
2960     case VAR_DECL:
2961     case CONST_DECL:
2962     case FIELD_DECL:
2963     case FUNCTION_DECL:
2964     case TEMPLATE_DECL:
2965     case IDENTIFIER_NODE:
2966     case SSA_NAME:
2967       return false;
2968
2969     case BASELINK:
2970       return (BASELINK_BINFO (t1) == BASELINK_BINFO (t2)
2971               && BASELINK_ACCESS_BINFO (t1) == BASELINK_ACCESS_BINFO (t2)
2972               && BASELINK_QUALIFIED_P (t1) == BASELINK_QUALIFIED_P (t2)
2973               && cp_tree_equal (BASELINK_FUNCTIONS (t1),
2974                                 BASELINK_FUNCTIONS (t2)));
2975
2976     case TEMPLATE_PARM_INDEX:
2977       return (TEMPLATE_PARM_IDX (t1) == TEMPLATE_PARM_IDX (t2)
2978               && TEMPLATE_PARM_LEVEL (t1) == TEMPLATE_PARM_LEVEL (t2)
2979               && (TEMPLATE_PARM_PARAMETER_PACK (t1)
2980                   == TEMPLATE_PARM_PARAMETER_PACK (t2))
2981               && same_type_p (TREE_TYPE (TEMPLATE_PARM_DECL (t1)),
2982                               TREE_TYPE (TEMPLATE_PARM_DECL (t2))));
2983
2984     case TEMPLATE_ID_EXPR:
2985       return (cp_tree_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0))
2986               && cp_tree_equal (TREE_OPERAND (t1, 1), TREE_OPERAND (t2, 1)));
2987
2988     case TREE_VEC:
2989       {
2990         unsigned ix;
2991         if (TREE_VEC_LENGTH (t1) != TREE_VEC_LENGTH (t2))
2992           return false;
2993         for (ix = TREE_VEC_LENGTH (t1); ix--;)
2994           if (!cp_tree_equal (TREE_VEC_ELT (t1, ix),
2995                               TREE_VEC_ELT (t2, ix)))
2996             return false;
2997         return true;
2998       }
2999
3000     case SIZEOF_EXPR:
3001     case ALIGNOF_EXPR:
3002       {
3003         tree o1 = TREE_OPERAND (t1, 0);
3004         tree o2 = TREE_OPERAND (t2, 0);
3005
3006         if (code1 == SIZEOF_EXPR)
3007           {
3008             if (SIZEOF_EXPR_TYPE_P (t1))
3009               o1 = TREE_TYPE (o1);
3010             if (SIZEOF_EXPR_TYPE_P (t2))
3011               o2 = TREE_TYPE (o2);
3012           }
3013         if (TREE_CODE (o1) != TREE_CODE (o2))
3014           return false;
3015         if (TYPE_P (o1))
3016           return same_type_p (o1, o2);
3017         else
3018           return cp_tree_equal (o1, o2);
3019       }
3020
3021     case MODOP_EXPR:
3022       {
3023         tree t1_op1, t2_op1;
3024
3025         if (!cp_tree_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0)))
3026           return false;
3027
3028         t1_op1 = TREE_OPERAND (t1, 1);
3029         t2_op1 = TREE_OPERAND (t2, 1);
3030         if (TREE_CODE (t1_op1) != TREE_CODE (t2_op1))
3031           return false;
3032
3033         return cp_tree_equal (TREE_OPERAND (t1, 2), TREE_OPERAND (t2, 2));
3034       }
3035
3036     case PTRMEM_CST:
3037       /* Two pointer-to-members are the same if they point to the same
3038          field or function in the same class.  */
3039       if (PTRMEM_CST_MEMBER (t1) != PTRMEM_CST_MEMBER (t2))
3040         return false;
3041
3042       return same_type_p (PTRMEM_CST_CLASS (t1), PTRMEM_CST_CLASS (t2));
3043
3044     case OVERLOAD:
3045       if (OVL_FUNCTION (t1) != OVL_FUNCTION (t2))
3046         return false;
3047       return cp_tree_equal (OVL_CHAIN (t1), OVL_CHAIN (t2));
3048
3049     case TRAIT_EXPR:
3050       if (TRAIT_EXPR_KIND (t1) != TRAIT_EXPR_KIND (t2))
3051         return false;
3052       return same_type_p (TRAIT_EXPR_TYPE1 (t1), TRAIT_EXPR_TYPE1 (t2))
3053         && cp_tree_equal (TRAIT_EXPR_TYPE2 (t1), TRAIT_EXPR_TYPE2 (t2));
3054
3055     case CAST_EXPR:
3056     case STATIC_CAST_EXPR:
3057     case REINTERPRET_CAST_EXPR:
3058     case CONST_CAST_EXPR:
3059     case DYNAMIC_CAST_EXPR:
3060     case IMPLICIT_CONV_EXPR:
3061     case NEW_EXPR:
3062     CASE_CONVERT:
3063     case NON_LVALUE_EXPR:
3064     case VIEW_CONVERT_EXPR:
3065       if (!same_type_p (TREE_TYPE (t1), TREE_TYPE (t2)))
3066         return false;
3067       /* Now compare operands as usual.  */
3068       break;
3069
3070     case DEFERRED_NOEXCEPT:
3071       return (cp_tree_equal (DEFERRED_NOEXCEPT_PATTERN (t1),
3072                              DEFERRED_NOEXCEPT_PATTERN (t2))
3073               && comp_template_args (DEFERRED_NOEXCEPT_ARGS (t1),
3074                                      DEFERRED_NOEXCEPT_ARGS (t2)));
3075       break;
3076
3077     default:
3078       break;
3079     }
3080
3081   switch (TREE_CODE_CLASS (code1))
3082     {
3083     case tcc_unary:
3084     case tcc_binary:
3085     case tcc_comparison:
3086     case tcc_expression:
3087     case tcc_vl_exp:
3088     case tcc_reference:
3089     case tcc_statement:
3090       {
3091         int i, n;
3092
3093         n = cp_tree_operand_length (t1);
3094         if (TREE_CODE_CLASS (code1) == tcc_vl_exp
3095             && n != TREE_OPERAND_LENGTH (t2))
3096           return false;
3097
3098         for (i = 0; i < n; ++i)
3099           if (!cp_tree_equal (TREE_OPERAND (t1, i), TREE_OPERAND (t2, i)))
3100             return false;
3101
3102         return true;
3103       }
3104
3105     case tcc_type:
3106       return same_type_p (t1, t2);
3107     default:
3108       gcc_unreachable ();
3109     }
3110   /* We can get here with --disable-checking.  */
3111   return false;
3112 }
3113
3114 /* The type of ARG when used as an lvalue.  */
3115
3116 tree
3117 lvalue_type (tree arg)
3118 {
3119   tree type = TREE_TYPE (arg);
3120   return type;
3121 }
3122
3123 /* The type of ARG for printing error messages; denote lvalues with
3124    reference types.  */
3125
3126 tree
3127 error_type (tree arg)
3128 {
3129   tree type = TREE_TYPE (arg);
3130
3131   if (TREE_CODE (type) == ARRAY_TYPE)
3132     ;
3133   else if (TREE_CODE (type) == ERROR_MARK)
3134     ;
3135   else if (real_lvalue_p (arg))
3136     type = build_reference_type (lvalue_type (arg));
3137   else if (MAYBE_CLASS_TYPE_P (type))
3138     type = lvalue_type (arg);
3139
3140   return type;
3141 }
3142
3143 /* Does FUNCTION use a variable-length argument list?  */
3144
3145 int
3146 varargs_function_p (const_tree function)
3147 {
3148   return stdarg_p (TREE_TYPE (function));
3149 }
3150
3151 /* Returns 1 if decl is a member of a class.  */
3152
3153 int
3154 member_p (const_tree decl)
3155 {
3156   const_tree const ctx = DECL_CONTEXT (decl);
3157   return (ctx && TYPE_P (ctx));
3158 }
3159
3160 /* Create a placeholder for member access where we don't actually have an
3161    object that the access is against.  */
3162
3163 tree
3164 build_dummy_object (tree type)
3165 {
3166   tree decl = build1 (CONVERT_EXPR, build_pointer_type (type), void_node);
3167   return cp_build_indirect_ref (decl, RO_NULL, tf_warning_or_error);
3168 }
3169
3170 /* We've gotten a reference to a member of TYPE.  Return *this if appropriate,
3171    or a dummy object otherwise.  If BINFOP is non-0, it is filled with the
3172    binfo path from current_class_type to TYPE, or 0.  */
3173
3174 tree
3175 maybe_dummy_object (tree type, tree* binfop)
3176 {
3177   tree decl, context;
3178   tree binfo;
3179   tree current = current_nonlambda_class_type ();
3180
3181   if (current
3182       && (binfo = lookup_base (current, type, ba_any, NULL,
3183                                tf_warning_or_error)))
3184     context = current;
3185   else
3186     {
3187       /* Reference from a nested class member function.  */
3188       context = type;
3189       binfo = TYPE_BINFO (type);
3190     }
3191
3192   if (binfop)
3193     *binfop = binfo;
3194
3195   if (current_class_ref
3196       /* current_class_ref might not correspond to current_class_type if
3197          we're in tsubst_default_argument or a lambda-declarator; in either
3198          case, we want to use current_class_ref if it matches CONTEXT.  */
3199       && (same_type_ignoring_top_level_qualifiers_p
3200           (TREE_TYPE (current_class_ref), context)))
3201     decl = current_class_ref;
3202   else
3203     decl = build_dummy_object (context);
3204
3205   return decl;
3206 }
3207
3208 /* Returns 1 if OB is a placeholder object, or a pointer to one.  */
3209
3210 int
3211 is_dummy_object (const_tree ob)
3212 {
3213   if (INDIRECT_REF_P (ob))
3214     ob = TREE_OPERAND (ob, 0);
3215   return (TREE_CODE (ob) == CONVERT_EXPR
3216           && TREE_OPERAND (ob, 0) == void_node);
3217 }
3218
3219 /* Returns 1 iff type T is something we want to treat as a scalar type for
3220    the purpose of deciding whether it is trivial/POD/standard-layout.  */
3221
3222 bool
3223 scalarish_type_p (const_tree t)
3224 {
3225   if (t == error_mark_node)
3226     return 1;
3227
3228   return (SCALAR_TYPE_P (t)
3229           || TREE_CODE (t) == VECTOR_TYPE);
3230 }
3231
3232 /* Returns true iff T requires non-trivial default initialization.  */
3233
3234 bool
3235 type_has_nontrivial_default_init (const_tree t)
3236 {
3237   t = strip_array_types (CONST_CAST_TREE (t));
3238
3239   if (CLASS_TYPE_P (t))
3240     return TYPE_HAS_COMPLEX_DFLT (t);
3241   else
3242     return 0;
3243 }
3244
3245 /* Returns true iff copying an object of type T (including via move
3246    constructor) is non-trivial.  That is, T has no non-trivial copy
3247    constructors and no non-trivial move constructors.  */
3248
3249 bool
3250 type_has_nontrivial_copy_init (const_tree t)
3251 {
3252   t = strip_array_types (CONST_CAST_TREE (t));
3253
3254   if (CLASS_TYPE_P (t))
3255     {
3256       gcc_assert (COMPLETE_TYPE_P (t));
3257       return ((TYPE_HAS_COPY_CTOR (t)
3258                && TYPE_HAS_COMPLEX_COPY_CTOR (t))
3259               || TYPE_HAS_COMPLEX_MOVE_CTOR (t));
3260     }
3261   else
3262     return 0;
3263 }
3264
3265 /* Returns 1 iff type T is a trivially copyable type, as defined in
3266    [basic.types] and [class].  */
3267
3268 bool
3269 trivially_copyable_p (const_tree t)
3270 {
3271   t = strip_array_types (CONST_CAST_TREE (t));
3272
3273   if (CLASS_TYPE_P (t))
3274     return ((!TYPE_HAS_COPY_CTOR (t)
3275              || !TYPE_HAS_COMPLEX_COPY_CTOR (t))
3276             && !TYPE_HAS_COMPLEX_MOVE_CTOR (t)
3277             && (!TYPE_HAS_COPY_ASSIGN (t)
3278                 || !TYPE_HAS_COMPLEX_COPY_ASSIGN (t))
3279             && !TYPE_HAS_COMPLEX_MOVE_ASSIGN (t)
3280             && TYPE_HAS_TRIVIAL_DESTRUCTOR (t));
3281   else
3282     return !CP_TYPE_VOLATILE_P (t) && scalarish_type_p (t);
3283 }
3284
3285 /* Returns 1 iff type T is a trivial type, as defined in [basic.types] and
3286    [class].  */
3287
3288 bool
3289 trivial_type_p (const_tree t)
3290 {
3291   t = strip_array_types (CONST_CAST_TREE (t));
3292
3293   if (CLASS_TYPE_P (t))
3294     return (TYPE_HAS_TRIVIAL_DFLT (t)
3295             && trivially_copyable_p (t));
3296   else
3297     return scalarish_type_p (t);
3298 }
3299
3300 /* Returns 1 iff type T is a POD type, as defined in [basic.types].  */
3301
3302 bool
3303 pod_type_p (const_tree t)
3304 {
3305   /* This CONST_CAST is okay because strip_array_types returns its
3306      argument unmodified and we assign it to a const_tree.  */
3307   t = strip_array_types (CONST_CAST_TREE(t));
3308
3309   if (!CLASS_TYPE_P (t))
3310     return scalarish_type_p (t);
3311   else if (cxx_dialect > cxx98)
3312     /* [class]/10: A POD struct is a class that is both a trivial class and a
3313        standard-layout class, and has no non-static data members of type
3314        non-POD struct, non-POD union (or array of such types).
3315
3316        We don't need to check individual members because if a member is
3317        non-std-layout or non-trivial, the class will be too.  */
3318     return (std_layout_type_p (t) && trivial_type_p (t));
3319   else
3320     /* The C++98 definition of POD is different.  */
3321     return !CLASSTYPE_NON_LAYOUT_POD_P (t);
3322 }
3323
3324 /* Returns true iff T is POD for the purpose of layout, as defined in the
3325    C++ ABI.  */
3326
3327 bool
3328 layout_pod_type_p (const_tree t)
3329 {
3330   t = strip_array_types (CONST_CAST_TREE (t));
3331
3332   if (CLASS_TYPE_P (t))
3333     return !CLASSTYPE_NON_LAYOUT_POD_P (t);
3334   else
3335     return scalarish_type_p (t);
3336 }
3337
3338 /* Returns true iff T is a standard-layout type, as defined in
3339    [basic.types].  */
3340
3341 bool
3342 std_layout_type_p (const_tree t)
3343 {
3344   t = strip_array_types (CONST_CAST_TREE (t));
3345
3346   if (CLASS_TYPE_P (t))
3347     return !CLASSTYPE_NON_STD_LAYOUT (t);
3348   else
3349     return scalarish_type_p (t);
3350 }
3351
3352 /* Nonzero iff type T is a class template implicit specialization.  */
3353
3354 bool
3355 class_tmpl_impl_spec_p (const_tree t)
3356 {
3357   return CLASS_TYPE_P (t) && CLASSTYPE_TEMPLATE_INSTANTIATION (t);
3358 }
3359
3360 /* Returns 1 iff zero initialization of type T means actually storing
3361    zeros in it.  */
3362
3363 int
3364 zero_init_p (const_tree t)
3365 {
3366   /* This CONST_CAST is okay because strip_array_types returns its
3367      argument unmodified and we assign it to a const_tree.  */
3368   t = strip_array_types (CONST_CAST_TREE(t));
3369
3370   if (t == error_mark_node)
3371     return 1;
3372
3373   /* NULL pointers to data members are initialized with -1.  */
3374   if (TYPE_PTRDATAMEM_P (t))
3375     return 0;
3376
3377   /* Classes that contain types that can't be zero-initialized, cannot
3378      be zero-initialized themselves.  */
3379   if (CLASS_TYPE_P (t) && CLASSTYPE_NON_ZERO_INIT_P (t))
3380     return 0;
3381
3382   return 1;
3383 }
3384
3385 /* Table of valid C++ attributes.  */
3386 const struct attribute_spec cxx_attribute_table[] =
3387 {
3388   /* { name, min_len, max_len, decl_req, type_req, fn_type_req, handler,
3389        affects_type_identity } */
3390   { "java_interface", 0, 0, false, false, false,
3391     handle_java_interface_attribute, false },
3392   { "com_interface",  0, 0, false, false, false,
3393     handle_com_interface_attribute, false },
3394   { "init_priority",  1, 1, true,  false, false,
3395     handle_init_priority_attribute, false },
3396   { "abi_tag", 1, -1, false, false, false,
3397     handle_abi_tag_attribute, true },
3398   { NULL,             0, 0, false, false, false, NULL, false }
3399 };
3400
3401 /* Handle a "java_interface" attribute; arguments as in
3402    struct attribute_spec.handler.  */
3403 static tree
3404 handle_java_interface_attribute (tree* node,
3405                                  tree name,
3406                                  tree /*args*/,
3407                                  int flags,
3408                                  bool* no_add_attrs)
3409 {
3410   if (DECL_P (*node)
3411       || !CLASS_TYPE_P (*node)
3412       || !TYPE_FOR_JAVA (*node))
3413     {
3414       error ("%qE attribute can only be applied to Java class definitions",
3415              name);
3416       *no_add_attrs = true;
3417       return NULL_TREE;
3418     }
3419   if (!(flags & (int) ATTR_FLAG_TYPE_IN_PLACE))
3420     *node = build_variant_type_copy (*node);
3421   TYPE_JAVA_INTERFACE (*node) = 1;
3422
3423   return NULL_TREE;
3424 }
3425
3426 /* Handle a "com_interface" attribute; arguments as in
3427    struct attribute_spec.handler.  */
3428 static tree
3429 handle_com_interface_attribute (tree* node,
3430                                 tree name,
3431                                 tree /*args*/,
3432                                 int /*flags*/,
3433                                 bool* no_add_attrs)
3434 {
3435   static int warned;
3436
3437   *no_add_attrs = true;
3438
3439   if (DECL_P (*node)
3440       || !CLASS_TYPE_P (*node)
3441       || *node != TYPE_MAIN_VARIANT (*node))
3442     {
3443       warning (OPT_Wattributes, "%qE attribute can only be applied "
3444                "to class definitions", name);
3445       return NULL_TREE;
3446     }
3447
3448   if (!warned++)
3449     warning (0, "%qE is obsolete; g++ vtables are now COM-compatible by default",
3450              name);
3451
3452   return NULL_TREE;
3453 }
3454
3455 /* Handle an "init_priority" attribute; arguments as in
3456    struct attribute_spec.handler.  */
3457 static tree
3458 handle_init_priority_attribute (tree* node,
3459                                 tree name,
3460                                 tree args,
3461                                 int /*flags*/,
3462                                 bool* no_add_attrs)
3463 {
3464   tree initp_expr = TREE_VALUE (args);
3465   tree decl = *node;
3466   tree type = TREE_TYPE (decl);
3467   int pri;
3468
3469   STRIP_NOPS (initp_expr);
3470   initp_expr = default_conversion (initp_expr);
3471
3472   if (!initp_expr || TREE_CODE (initp_expr) != INTEGER_CST)
3473     {
3474       error ("requested init_priority is not an integer constant");
3475       *no_add_attrs = true;
3476       return NULL_TREE;
3477     }
3478
3479   pri = TREE_INT_CST_LOW (initp_expr);
3480
3481   type = strip_array_types (type);
3482
3483   if (decl == NULL_TREE
3484       || !VAR_P (decl)
3485       || !TREE_STATIC (decl)
3486       || DECL_EXTERNAL (decl)
3487       || (TREE_CODE (type) != RECORD_TYPE
3488           && TREE_CODE (type) != UNION_TYPE)
3489       /* Static objects in functions are initialized the
3490          first time control passes through that
3491          function. This is not precise enough to pin down an
3492          init_priority value, so don't allow it.  */
3493       || current_function_decl)
3494     {
3495       error ("can only use %qE attribute on file-scope definitions "
3496              "of objects of class type", name);
3497       *no_add_attrs = true;
3498       return NULL_TREE;
3499     }
3500
3501   if (pri > MAX_INIT_PRIORITY || pri <= 0)
3502     {
3503       error ("requested init_priority is out of range");
3504       *no_add_attrs = true;
3505       return NULL_TREE;
3506     }
3507
3508   /* Check for init_priorities that are reserved for
3509      language and runtime support implementations.*/
3510   if (pri <= MAX_RESERVED_INIT_PRIORITY)
3511     {
3512       warning
3513         (0, "requested init_priority is reserved for internal use");
3514     }
3515
3516   if (SUPPORTS_INIT_PRIORITY)
3517     {
3518       SET_DECL_INIT_PRIORITY (decl, pri);
3519       DECL_HAS_INIT_PRIORITY_P (decl) = 1;
3520       return NULL_TREE;
3521     }
3522   else
3523     {
3524       error ("%qE attribute is not supported on this platform", name);
3525       *no_add_attrs = true;
3526       return NULL_TREE;
3527     }
3528 }
3529
3530 /* DECL is being redeclared; the old declaration had the abi tags in OLD,
3531    and the new one has the tags in NEW_.  Give an error if there are tags
3532    in NEW_ that weren't in OLD.  */
3533
3534 bool
3535 check_abi_tag_redeclaration (const_tree decl, const_tree old, const_tree new_)
3536 {
3537   if (old && TREE_CODE (TREE_VALUE (old)) == TREE_LIST)
3538     old = TREE_VALUE (old);
3539   if (new_ && TREE_CODE (TREE_VALUE (new_)) == TREE_LIST)
3540     new_ = TREE_VALUE (new_);
3541   bool err = false;
3542   for (const_tree t = new_; t; t = TREE_CHAIN (t))
3543     {
3544       tree str = TREE_VALUE (t);
3545       for (const_tree in = old; in; in = TREE_CHAIN (in))
3546         {
3547           tree ostr = TREE_VALUE (in);
3548           if (cp_tree_equal (str, ostr))
3549             goto found;
3550         }
3551       error ("redeclaration of %qD adds abi tag %E", decl, str);
3552       err = true;
3553     found:;
3554     }
3555   if (err)
3556     {
3557       inform (DECL_SOURCE_LOCATION (decl), "previous declaration here");
3558       return false;
3559     }
3560   return true;
3561 }
3562
3563 /* The abi_tag attribute with the name NAME was given ARGS.  If they are
3564    ill-formed, give an error and return false; otherwise, return true.  */
3565
3566 bool
3567 check_abi_tag_args (tree args, tree name)
3568 {
3569   if (!args)
3570     {
3571       error ("the %qE attribute requires arguments", name);
3572       return false;
3573     }
3574   for (tree arg = args; arg; arg = TREE_CHAIN (arg))
3575     {
3576       tree elt = TREE_VALUE (arg);
3577       if (TREE_CODE (elt) != STRING_CST
3578           || (!same_type_ignoring_top_level_qualifiers_p
3579               (strip_array_types (TREE_TYPE (elt)),
3580                char_type_node)))
3581         {
3582           error ("arguments to the %qE attribute must be narrow string "
3583                  "literals", name);
3584           return false;
3585         }
3586       const char *begin = TREE_STRING_POINTER (elt);
3587       const char *end = begin + TREE_STRING_LENGTH (elt);
3588       for (const char *p = begin; p != end; ++p)
3589         {
3590           char c = *p;
3591           if (p == begin)
3592             {
3593               if (!ISALPHA (c) && c != '_')
3594                 {
3595                   error ("arguments to the %qE attribute must contain valid "
3596                          "identifiers", name);
3597                   inform (input_location, "%<%c%> is not a valid first "
3598                           "character for an identifier", c);
3599                   return false;
3600                 }
3601             }
3602           else if (p == end - 1)
3603             gcc_assert (c == 0);
3604           else
3605             {
3606               if (!ISALNUM (c) && c != '_')
3607                 {
3608                   error ("arguments to the %qE attribute must contain valid "
3609                          "identifiers", name);
3610                   inform (input_location, "%<%c%> is not a valid character "
3611                           "in an identifier", c);
3612                   return false;
3613                 }
3614             }
3615         }
3616     }
3617   return true;
3618 }
3619
3620 /* Handle an "abi_tag" attribute; arguments as in
3621    struct attribute_spec.handler.  */
3622
3623 static tree
3624 handle_abi_tag_attribute (tree* node, tree name, tree args,
3625                           int flags, bool* no_add_attrs)
3626 {
3627   if (!check_abi_tag_args (args, name))
3628     goto fail;
3629
3630   if (TYPE_P (*node))
3631     {
3632       if (!OVERLOAD_TYPE_P (*node))
3633         {
3634           error ("%qE attribute applied to non-class, non-enum type %qT",
3635                  name, *node);
3636           goto fail;
3637         }
3638       else if (!(flags & (int)ATTR_FLAG_TYPE_IN_PLACE))
3639         {
3640           error ("%qE attribute applied to %qT after its definition",
3641                  name, *node);
3642           goto fail;
3643         }
3644       else if (CLASSTYPE_TEMPLATE_INSTANTIATION (*node))
3645         {
3646           warning (OPT_Wattributes, "ignoring %qE attribute applied to "
3647                    "template instantiation %qT", name, *node);
3648           goto fail;
3649         }
3650       else if (CLASSTYPE_TEMPLATE_SPECIALIZATION (*node))
3651         {
3652           warning (OPT_Wattributes, "ignoring %qE attribute applied to "
3653                    "template specialization %qT", name, *node);
3654           goto fail;
3655         }
3656
3657       tree attributes = TYPE_ATTRIBUTES (*node);
3658       tree decl = TYPE_NAME (*node);
3659
3660       /* Make sure all declarations have the same abi tags.  */
3661       if (DECL_SOURCE_LOCATION (decl) != input_location)
3662         {
3663           if (!check_abi_tag_redeclaration (decl,
3664                                             lookup_attribute ("abi_tag",
3665                                                               attributes),
3666                                             args))
3667             goto fail;
3668         }
3669     }
3670   else
3671     {
3672       if (TREE_CODE (*node) != FUNCTION_DECL
3673           && TREE_CODE (*node) != VAR_DECL)
3674         {
3675           error ("%qE attribute applied to non-function, non-variable %qD",
3676                  name, *node);
3677           goto fail;
3678         }
3679       else if (DECL_LANGUAGE (*node) == lang_c)
3680         {
3681           error ("%qE attribute applied to extern \"C\" declaration %qD",
3682                  name, *node);
3683           goto fail;
3684         }
3685     }
3686
3687   return NULL_TREE;
3688
3689  fail:
3690   *no_add_attrs = true;
3691   return NULL_TREE;
3692 }
3693
3694 /* Return a new PTRMEM_CST of the indicated TYPE.  The MEMBER is the
3695    thing pointed to by the constant.  */
3696
3697 tree
3698 make_ptrmem_cst (tree type, tree member)
3699 {
3700   tree ptrmem_cst = make_node (PTRMEM_CST);
3701   TREE_TYPE (ptrmem_cst) = type;
3702   PTRMEM_CST_MEMBER (ptrmem_cst) = member;
3703   return ptrmem_cst;
3704 }
3705
3706 /* Build a variant of TYPE that has the indicated ATTRIBUTES.  May
3707    return an existing type if an appropriate type already exists.  */
3708
3709 tree
3710 cp_build_type_attribute_variant (tree type, tree attributes)
3711 {
3712   tree new_type;
3713
3714   new_type = build_type_attribute_variant (type, attributes);
3715   if (TREE_CODE (new_type) == FUNCTION_TYPE
3716       || TREE_CODE (new_type) == METHOD_TYPE)
3717     {
3718       new_type = build_exception_variant (new_type,
3719                                           TYPE_RAISES_EXCEPTIONS (type));
3720       new_type = build_ref_qualified_type (new_type,
3721                                            type_memfn_rqual (type));
3722     }
3723
3724   /* Making a new main variant of a class type is broken.  */
3725   gcc_assert (!CLASS_TYPE_P (type) || new_type == type);
3726
3727   return new_type;
3728 }
3729
3730 /* Return TRUE if TYPE1 and TYPE2 are identical for type hashing purposes.
3731    Called only after doing all language independent checks.  Only
3732    to check TYPE_RAISES_EXCEPTIONS for FUNCTION_TYPE, the rest is already
3733    compared in type_hash_eq.  */
3734
3735 bool
3736 cxx_type_hash_eq (const_tree typea, const_tree typeb)
3737 {
3738   gcc_assert (TREE_CODE (typea) == FUNCTION_TYPE
3739               || TREE_CODE (typea) == METHOD_TYPE);
3740
3741   return comp_except_specs (TYPE_RAISES_EXCEPTIONS (typea),
3742                             TYPE_RAISES_EXCEPTIONS (typeb), ce_exact);
3743 }
3744
3745 /* Apply FUNC to all language-specific sub-trees of TP in a pre-order
3746    traversal.  Called from walk_tree.  */
3747
3748 tree
3749 cp_walk_subtrees (tree *tp, int *walk_subtrees_p, walk_tree_fn func,
3750                   void *data, hash_set<tree> *pset)
3751 {
3752   enum tree_code code = TREE_CODE (*tp);
3753   tree result;
3754
3755 #define WALK_SUBTREE(NODE)                              \
3756   do                                                    \
3757     {                                                   \
3758       result = cp_walk_tree (&(NODE), func, data, pset);        \
3759       if (result) goto out;                             \
3760     }                                                   \
3761   while (0)
3762
3763   /* Not one of the easy cases.  We must explicitly go through the
3764      children.  */
3765   result = NULL_TREE;
3766   switch (code)
3767     {
3768     case DEFAULT_ARG:
3769     case TEMPLATE_TEMPLATE_PARM:
3770     case BOUND_TEMPLATE_TEMPLATE_PARM:
3771     case UNBOUND_CLASS_TEMPLATE:
3772     case TEMPLATE_PARM_INDEX:
3773     case TEMPLATE_TYPE_PARM:
3774     case TYPENAME_TYPE:
3775     case TYPEOF_TYPE:
3776     case UNDERLYING_TYPE:
3777       /* None of these have subtrees other than those already walked
3778          above.  */
3779       *walk_subtrees_p = 0;
3780       break;
3781
3782     case BASELINK:
3783       WALK_SUBTREE (BASELINK_FUNCTIONS (*tp));
3784       *walk_subtrees_p = 0;
3785       break;
3786
3787     case PTRMEM_CST:
3788       WALK_SUBTREE (TREE_TYPE (*tp));
3789       *walk_subtrees_p = 0;
3790       break;
3791
3792     case TREE_LIST:
3793       WALK_SUBTREE (TREE_PURPOSE (*tp));
3794       break;
3795
3796     case OVERLOAD:
3797       WALK_SUBTREE (OVL_FUNCTION (*tp));
3798       WALK_SUBTREE (OVL_CHAIN (*tp));
3799       *walk_subtrees_p = 0;
3800       break;
3801
3802     case USING_DECL:
3803       WALK_SUBTREE (DECL_NAME (*tp));
3804       WALK_SUBTREE (USING_DECL_SCOPE (*tp));
3805       WALK_SUBTREE (USING_DECL_DECLS (*tp));
3806       *walk_subtrees_p = 0;
3807       break;
3808
3809     case RECORD_TYPE:
3810       if (TYPE_PTRMEMFUNC_P (*tp))
3811         WALK_SUBTREE (TYPE_PTRMEMFUNC_FN_TYPE_RAW (*tp));
3812       break;
3813
3814     case TYPE_ARGUMENT_PACK:
3815     case NONTYPE_ARGUMENT_PACK:
3816       {
3817         tree args = ARGUMENT_PACK_ARGS (*tp);
3818         int i, len = TREE_VEC_LENGTH (args);
3819         for (i = 0; i < len; i++)
3820           WALK_SUBTREE (TREE_VEC_ELT (args, i));
3821       }
3822       break;
3823
3824     case TYPE_PACK_EXPANSION:
3825       WALK_SUBTREE (TREE_TYPE (*tp));
3826       WALK_SUBTREE (PACK_EXPANSION_EXTRA_ARGS (*tp));
3827       *walk_subtrees_p = 0;
3828       break;
3829
3830     case EXPR_PACK_EXPANSION:
3831       WALK_SUBTREE (TREE_OPERAND (*tp, 0));
3832       WALK_SUBTREE (PACK_EXPANSION_EXTRA_ARGS (*tp));
3833       *walk_subtrees_p = 0;
3834       break;
3835
3836     case CAST_EXPR:
3837     case REINTERPRET_CAST_EXPR:
3838     case STATIC_CAST_EXPR:
3839     case CONST_CAST_EXPR:
3840     case DYNAMIC_CAST_EXPR:
3841     case IMPLICIT_CONV_EXPR:
3842       if (TREE_TYPE (*tp))
3843         WALK_SUBTREE (TREE_TYPE (*tp));
3844
3845       {
3846         int i;
3847         for (i = 0; i < TREE_CODE_LENGTH (TREE_CODE (*tp)); ++i)
3848           WALK_SUBTREE (TREE_OPERAND (*tp, i));
3849       }
3850       *walk_subtrees_p = 0;
3851       break;
3852
3853     case TRAIT_EXPR:
3854       WALK_SUBTREE (TRAIT_EXPR_TYPE1 (*tp));
3855       WALK_SUBTREE (TRAIT_EXPR_TYPE2 (*tp));
3856       *walk_subtrees_p = 0;
3857       break;
3858
3859     case DECLTYPE_TYPE:
3860       WALK_SUBTREE (DECLTYPE_TYPE_EXPR (*tp));
3861       *walk_subtrees_p = 0;
3862       break;
3863
3864
3865     default:
3866       return NULL_TREE;
3867     }
3868
3869   /* We didn't find what we were looking for.  */
3870  out:
3871   return result;
3872
3873 #undef WALK_SUBTREE
3874 }
3875
3876 /* Like save_expr, but for C++.  */
3877
3878 tree
3879 cp_save_expr (tree expr)
3880 {
3881   /* There is no reason to create a SAVE_EXPR within a template; if
3882      needed, we can create the SAVE_EXPR when instantiating the
3883      template.  Furthermore, the middle-end cannot handle C++-specific
3884      tree codes.  */
3885   if (processing_template_decl)
3886     return expr;
3887   return save_expr (expr);
3888 }
3889
3890 /* Initialize tree.c.  */
3891
3892 void
3893 init_tree (void)
3894 {
3895   list_hash_table = hash_table<list_hasher>::create_ggc (61);
3896 }
3897
3898 /* Returns the kind of special function that DECL (a FUNCTION_DECL)
3899    is.  Note that sfk_none is zero, so this function can be used as a
3900    predicate to test whether or not DECL is a special function.  */
3901
3902 special_function_kind
3903 special_function_p (const_tree decl)
3904 {
3905   /* Rather than doing all this stuff with magic names, we should
3906      probably have a field of type `special_function_kind' in
3907      DECL_LANG_SPECIFIC.  */
3908   if (DECL_INHERITED_CTOR_BASE (decl))
3909     return sfk_inheriting_constructor;
3910   if (DECL_COPY_CONSTRUCTOR_P (decl))
3911     return sfk_copy_constructor;
3912   if (DECL_MOVE_CONSTRUCTOR_P (decl))
3913     return sfk_move_constructor;
3914   if (DECL_CONSTRUCTOR_P (decl))
3915     return sfk_constructor;
3916   if (DECL_OVERLOADED_OPERATOR_P (decl) == NOP_EXPR)
3917     {
3918       if (copy_fn_p (decl))
3919         return sfk_copy_assignment;
3920       if (move_fn_p (decl))
3921         return sfk_move_assignment;
3922     }
3923   if (DECL_MAYBE_IN_CHARGE_DESTRUCTOR_P (decl))
3924     return sfk_destructor;
3925   if (DECL_COMPLETE_DESTRUCTOR_P (decl))
3926     return sfk_complete_destructor;
3927   if (DECL_BASE_DESTRUCTOR_P (decl))
3928     return sfk_base_destructor;
3929   if (DECL_DELETING_DESTRUCTOR_P (decl))
3930     return sfk_deleting_destructor;
3931   if (DECL_CONV_FN_P (decl))
3932     return sfk_conversion;
3933
3934   return sfk_none;
3935 }
3936
3937 /* Returns nonzero if TYPE is a character type, including wchar_t.  */
3938
3939 int
3940 char_type_p (tree type)
3941 {
3942   return (same_type_p (type, char_type_node)
3943           || same_type_p (type, unsigned_char_type_node)
3944           || same_type_p (type, signed_char_type_node)
3945           || same_type_p (type, char16_type_node)
3946           || same_type_p (type, char32_type_node)
3947           || same_type_p (type, wchar_type_node));
3948 }
3949
3950 /* Returns the kind of linkage associated with the indicated DECL.  Th
3951    value returned is as specified by the language standard; it is
3952    independent of implementation details regarding template
3953    instantiation, etc.  For example, it is possible that a declaration
3954    to which this function assigns external linkage would not show up
3955    as a global symbol when you run `nm' on the resulting object file.  */
3956
3957 linkage_kind
3958 decl_linkage (tree decl)
3959 {
3960   /* This function doesn't attempt to calculate the linkage from first
3961      principles as given in [basic.link].  Instead, it makes use of
3962      the fact that we have already set TREE_PUBLIC appropriately, and
3963      then handles a few special cases.  Ideally, we would calculate
3964      linkage first, and then transform that into a concrete
3965      implementation.  */
3966
3967   /* Things that don't have names have no linkage.  */
3968   if (!DECL_NAME (decl))
3969     return lk_none;
3970
3971   /* Fields have no linkage.  */
3972   if (TREE_CODE (decl) == FIELD_DECL)
3973     return lk_none;
3974
3975   /* Things that are TREE_PUBLIC have external linkage.  */
3976   if (TREE_PUBLIC (decl))
3977     return lk_external;
3978
3979   if (TREE_CODE (decl) == NAMESPACE_DECL)
3980     return lk_external;
3981
3982   /* Linkage of a CONST_DECL depends on the linkage of the enumeration
3983      type.  */
3984   if (TREE_CODE (decl) == CONST_DECL)
3985     return decl_linkage (TYPE_NAME (DECL_CONTEXT (decl)));
3986
3987   /* Things in local scope do not have linkage, if they don't have
3988      TREE_PUBLIC set.  */
3989   if (decl_function_context (decl))
3990     return lk_none;
3991
3992   /* Members of the anonymous namespace also have TREE_PUBLIC unset, but
3993      are considered to have external linkage for language purposes, as do
3994      template instantiations on targets without weak symbols.  DECLs really
3995      meant to have internal linkage have DECL_THIS_STATIC set.  */
3996   if (TREE_CODE (decl) == TYPE_DECL)
3997     return lk_external;
3998   if (VAR_OR_FUNCTION_DECL_P (decl))
3999     {
4000       if (!DECL_THIS_STATIC (decl))
4001         return lk_external;
4002
4003       /* Static data members and static member functions from classes
4004          in anonymous namespace also don't have TREE_PUBLIC set.  */
4005       if (DECL_CLASS_CONTEXT (decl))
4006         return lk_external;
4007     }
4008
4009   /* Everything else has internal linkage.  */
4010   return lk_internal;
4011 }
4012
4013 /* Returns the storage duration of the object or reference associated with
4014    the indicated DECL, which should be a VAR_DECL or PARM_DECL.  */
4015
4016 duration_kind
4017 decl_storage_duration (tree decl)
4018 {
4019   if (TREE_CODE (decl) == PARM_DECL)
4020     return dk_auto;
4021   if (TREE_CODE (decl) == FUNCTION_DECL)
4022     return dk_static;
4023   gcc_assert (VAR_P (decl));
4024   if (!TREE_STATIC (decl)
4025       && !DECL_EXTERNAL (decl))
4026     return dk_auto;
4027   if (DECL_THREAD_LOCAL_P (decl))
4028     return dk_thread;
4029   return dk_static;
4030 }
4031 \f
4032 /* EXP is an expression that we want to pre-evaluate.  Returns (in
4033    *INITP) an expression that will perform the pre-evaluation.  The
4034    value returned by this function is a side-effect free expression
4035    equivalent to the pre-evaluated expression.  Callers must ensure
4036    that *INITP is evaluated before EXP.  */
4037
4038 tree
4039 stabilize_expr (tree exp, tree* initp)
4040 {
4041   tree init_expr;
4042
4043   if (!TREE_SIDE_EFFECTS (exp))
4044     init_expr = NULL_TREE;
4045   else if (VOID_TYPE_P (TREE_TYPE (exp)))
4046     {
4047       init_expr = exp;
4048       exp = void_node;
4049     }
4050   /* There are no expressions with REFERENCE_TYPE, but there can be call
4051      arguments with such a type; just treat it as a pointer.  */
4052   else if (TREE_CODE (TREE_TYPE (exp)) == REFERENCE_TYPE
4053            || SCALAR_TYPE_P (TREE_TYPE (exp))
4054            || !lvalue_or_rvalue_with_address_p (exp))
4055     {
4056       init_expr = get_target_expr (exp);
4057       exp = TARGET_EXPR_SLOT (init_expr);
4058       if (CLASS_TYPE_P (TREE_TYPE (exp)))
4059         exp = move (exp);
4060       else
4061         exp = rvalue (exp);
4062     }
4063   else
4064     {
4065       bool xval = !real_lvalue_p (exp);
4066       exp = cp_build_addr_expr (exp, tf_warning_or_error);
4067       init_expr = get_target_expr (exp);
4068       exp = TARGET_EXPR_SLOT (init_expr);
4069       exp = cp_build_indirect_ref (exp, RO_NULL, tf_warning_or_error);
4070       if (xval)
4071         exp = move (exp);
4072     }
4073   *initp = init_expr;
4074
4075   gcc_assert (!TREE_SIDE_EFFECTS (exp));
4076   return exp;
4077 }
4078
4079 /* Add NEW_EXPR, an expression whose value we don't care about, after the
4080    similar expression ORIG.  */
4081
4082 tree
4083 add_stmt_to_compound (tree orig, tree new_expr)
4084 {
4085   if (!new_expr || !TREE_SIDE_EFFECTS (new_expr))
4086     return orig;
4087   if (!orig || !TREE_SIDE_EFFECTS (orig))
4088     return new_expr;
4089   return build2 (COMPOUND_EXPR, void_type_node, orig, new_expr);
4090 }
4091
4092 /* Like stabilize_expr, but for a call whose arguments we want to
4093    pre-evaluate.  CALL is modified in place to use the pre-evaluated
4094    arguments, while, upon return, *INITP contains an expression to
4095    compute the arguments.  */
4096
4097 void
4098 stabilize_call (tree call, tree *initp)
4099 {
4100   tree inits = NULL_TREE;
4101   int i;
4102   int nargs = call_expr_nargs (call);
4103
4104   if (call == error_mark_node || processing_template_decl)
4105     {
4106       *initp = NULL_TREE;
4107       return;
4108     }
4109
4110   gcc_assert (TREE_CODE (call) == CALL_EXPR);
4111
4112   for (i = 0; i < nargs; i++)
4113     {
4114       tree init;
4115       CALL_EXPR_ARG (call, i) =
4116         stabilize_expr (CALL_EXPR_ARG (call, i), &init);
4117       inits = add_stmt_to_compound (inits, init);
4118     }
4119
4120   *initp = inits;
4121 }
4122
4123 /* Like stabilize_expr, but for an AGGR_INIT_EXPR whose arguments we want
4124    to pre-evaluate.  CALL is modified in place to use the pre-evaluated
4125    arguments, while, upon return, *INITP contains an expression to
4126    compute the arguments.  */
4127
4128 static void
4129 stabilize_aggr_init (tree call, tree *initp)
4130 {
4131   tree inits = NULL_TREE;
4132   int i;
4133   int nargs = aggr_init_expr_nargs (call);
4134
4135   if (call == error_mark_node)
4136     return;
4137
4138   gcc_assert (TREE_CODE (call) == AGGR_INIT_EXPR);
4139
4140   for (i = 0; i < nargs; i++)
4141     {
4142       tree init;
4143       AGGR_INIT_EXPR_ARG (call, i) =
4144         stabilize_expr (AGGR_INIT_EXPR_ARG (call, i), &init);
4145       inits = add_stmt_to_compound (inits, init);
4146     }
4147
4148   *initp = inits;
4149 }
4150
4151 /* Like stabilize_expr, but for an initialization.
4152
4153    If the initialization is for an object of class type, this function
4154    takes care not to introduce additional temporaries.
4155
4156    Returns TRUE iff the expression was successfully pre-evaluated,
4157    i.e., if INIT is now side-effect free, except for, possibly, a
4158    single call to a constructor.  */
4159
4160 bool
4161 stabilize_init (tree init, tree *initp)
4162 {
4163   tree t = init;
4164
4165   *initp = NULL_TREE;
4166
4167   if (t == error_mark_node || processing_template_decl)
4168     return true;
4169
4170   if (TREE_CODE (t) == INIT_EXPR)
4171     t = TREE_OPERAND (t, 1);
4172   if (TREE_CODE (t) == TARGET_EXPR)
4173     t = TARGET_EXPR_INITIAL (t);
4174
4175   /* If the RHS can be stabilized without breaking copy elision, stabilize
4176      it.  We specifically don't stabilize class prvalues here because that
4177      would mean an extra copy, but they might be stabilized below.  */
4178   if (TREE_CODE (init) == INIT_EXPR
4179       && TREE_CODE (t) != CONSTRUCTOR
4180       && TREE_CODE (t) != AGGR_INIT_EXPR
4181       && (SCALAR_TYPE_P (TREE_TYPE (t))
4182           || lvalue_or_rvalue_with_address_p (t)))
4183     {
4184       TREE_OPERAND (init, 1) = stabilize_expr (t, initp);
4185       return true;
4186     }
4187
4188   if (TREE_CODE (t) == COMPOUND_EXPR
4189       && TREE_CODE (init) == INIT_EXPR)
4190     {
4191       tree last = expr_last (t);
4192       /* Handle stabilizing the EMPTY_CLASS_EXPR pattern.  */
4193       if (!TREE_SIDE_EFFECTS (last))
4194         {
4195           *initp = t;
4196           TREE_OPERAND (init, 1) = last;
4197           return true;
4198         }
4199     }
4200
4201   if (TREE_CODE (t) == CONSTRUCTOR)
4202     {
4203       /* Aggregate initialization: stabilize each of the field
4204          initializers.  */
4205       unsigned i;
4206       constructor_elt *ce;
4207       bool good = true;
4208       vec<constructor_elt, va_gc> *v = CONSTRUCTOR_ELTS (t);
4209       for (i = 0; vec_safe_iterate (v, i, &ce); ++i)
4210         {
4211           tree type = TREE_TYPE (ce->value);
4212           tree subinit;
4213           if (TREE_CODE (type) == REFERENCE_TYPE
4214               || SCALAR_TYPE_P (type))
4215             ce->value = stabilize_expr (ce->value, &subinit);
4216           else if (!stabilize_init (ce->value, &subinit))
4217             good = false;
4218           *initp = add_stmt_to_compound (*initp, subinit);
4219         }
4220       return good;
4221     }
4222
4223   if (TREE_CODE (t) == CALL_EXPR)
4224     {
4225       stabilize_call (t, initp);
4226       return true;
4227     }
4228
4229   if (TREE_CODE (t) == AGGR_INIT_EXPR)
4230     {
4231       stabilize_aggr_init (t, initp);
4232       return true;
4233     }
4234
4235   /* The initialization is being performed via a bitwise copy -- and
4236      the item copied may have side effects.  */
4237   return !TREE_SIDE_EFFECTS (init);
4238 }
4239
4240 /* Like "fold", but should be used whenever we might be processing the
4241    body of a template.  */
4242
4243 tree
4244 fold_if_not_in_template (tree expr)
4245 {
4246   /* In the body of a template, there is never any need to call
4247      "fold".  We will call fold later when actually instantiating the
4248      template.  Integral constant expressions in templates will be
4249      evaluated via instantiate_non_dependent_expr, as necessary.  */
4250   if (processing_template_decl)
4251     return expr;
4252
4253   /* Fold C++ front-end specific tree codes.  */
4254   if (TREE_CODE (expr) == UNARY_PLUS_EXPR)
4255     return fold_convert (TREE_TYPE (expr), TREE_OPERAND (expr, 0));
4256
4257   return fold (expr);
4258 }
4259
4260 /* Returns true if a cast to TYPE may appear in an integral constant
4261    expression.  */
4262
4263 bool
4264 cast_valid_in_integral_constant_expression_p (tree type)
4265 {
4266   return (INTEGRAL_OR_ENUMERATION_TYPE_P (type)
4267           || cxx_dialect >= cxx11
4268           || dependent_type_p (type)
4269           || type == error_mark_node);
4270 }
4271
4272 /* Return true if we need to fix linkage information of DECL.  */
4273
4274 static bool
4275 cp_fix_function_decl_p (tree decl)
4276 {
4277   /* Skip if DECL is not externally visible.  */
4278   if (!TREE_PUBLIC (decl))
4279     return false;
4280
4281   /* We need to fix DECL if it a appears to be exported but with no
4282      function body.  Thunks do not have CFGs and we may need to
4283      handle them specially later.   */
4284   if (!gimple_has_body_p (decl)
4285       && !DECL_THUNK_P (decl)
4286       && !DECL_EXTERNAL (decl))
4287     {
4288       struct cgraph_node *node = cgraph_node::get (decl);
4289
4290       /* Don't fix same_body aliases.  Although they don't have their own
4291          CFG, they share it with what they alias to.  */
4292       if (!node || !node->alias
4293           || !vec_safe_length (node->ref_list.references))
4294         return true;
4295     }
4296
4297   return false;
4298 }
4299
4300 /* Clean the C++ specific parts of the tree T. */
4301
4302 void
4303 cp_free_lang_data (tree t)
4304 {
4305   if (TREE_CODE (t) == METHOD_TYPE
4306       || TREE_CODE (t) == FUNCTION_TYPE)
4307     {
4308       /* Default args are not interesting anymore.  */
4309       tree argtypes = TYPE_ARG_TYPES (t);
4310       while (argtypes)
4311         {
4312           TREE_PURPOSE (argtypes) = 0;
4313           argtypes = TREE_CHAIN (argtypes);
4314         }
4315     }
4316   else if (TREE_CODE (t) == FUNCTION_DECL
4317            && cp_fix_function_decl_p (t))
4318     {
4319       /* If T is used in this translation unit at all,  the definition
4320          must exist somewhere else since we have decided to not emit it
4321          in this TU.  So make it an external reference.  */
4322       DECL_EXTERNAL (t) = 1;
4323       TREE_STATIC (t) = 0;
4324     }
4325   if (TREE_CODE (t) == NAMESPACE_DECL)
4326     {
4327       /* The list of users of a namespace isn't useful for the middle-end
4328          or debug generators.  */
4329       DECL_NAMESPACE_USERS (t) = NULL_TREE;
4330       /* Neither do we need the leftover chaining of namespaces
4331          from the binding level.  */
4332       DECL_CHAIN (t) = NULL_TREE;
4333     }
4334 }
4335
4336 /* Stub for c-common.  Please keep in sync with c-decl.c.
4337    FIXME: If address space support is target specific, then this
4338    should be a C target hook.  But currently this is not possible,
4339    because this function is called via REGISTER_TARGET_PRAGMAS.  */
4340 void
4341 c_register_addr_space (const char * /*word*/, addr_space_t /*as*/)
4342 {
4343 }
4344
4345 /* Return the number of operands in T that we care about for things like
4346    mangling.  */
4347
4348 int
4349 cp_tree_operand_length (const_tree t)
4350 {
4351   enum tree_code code = TREE_CODE (t);
4352
4353   switch (code)
4354     {
4355     case PREINCREMENT_EXPR:
4356     case PREDECREMENT_EXPR:
4357     case POSTINCREMENT_EXPR:
4358     case POSTDECREMENT_EXPR:
4359       return 1;
4360
4361     case ARRAY_REF:
4362       return 2;
4363
4364     case EXPR_PACK_EXPANSION:
4365       return 1;
4366
4367     default:
4368       return TREE_OPERAND_LENGTH (t);
4369     }
4370 }
4371
4372 /* Implement -Wzero_as_null_pointer_constant.  Return true if the
4373    conditions for the warning hold, false otherwise.  */
4374 bool
4375 maybe_warn_zero_as_null_pointer_constant (tree expr, location_t loc)
4376 {
4377   if (c_inhibit_evaluation_warnings == 0
4378       && !NULLPTR_TYPE_P (TREE_TYPE (expr)))
4379     {
4380       warning_at (loc, OPT_Wzero_as_null_pointer_constant,
4381                   "zero as null pointer constant");
4382       return true;
4383     }
4384   return false;
4385 }
4386 \f
4387 #if defined ENABLE_TREE_CHECKING && (GCC_VERSION >= 2007)
4388 /* Complain that some language-specific thing hanging off a tree
4389    node has been accessed improperly.  */
4390
4391 void
4392 lang_check_failed (const char* file, int line, const char* function)
4393 {
4394   internal_error ("lang_* check: failed in %s, at %s:%d",
4395                   function, trim_filename (file), line);
4396 }
4397 #endif /* ENABLE_TREE_CHECKING */
4398
4399 #include "gt-cp-tree.h"