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