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