gcc/cp/tree.c

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