gcc/cp/tree.c

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