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