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