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