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
   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 "real.h"
  31 #include "rtl.h"
  32 #include "toplev.h"
  33 #include "insn-config.h"
  34 #include "integrate.h"
  35 #include "tree-inline.h"
  36 #include "debug.h"
  37 #include "target.h"
  38 #include "convert.h"
  39 #include "tree-flow.h"
  40
  41 static tree bot_manip (tree *, int *, void *);
  42 static tree bot_replace (tree *, int *, void *);
  43 static tree build_cplus_array_type_1 (tree, tree);
  44 static int list_hash_eq (const void *, const void *);
  45 static hashval_t list_hash_pieces (tree, tree, tree);
  46 static hashval_t list_hash (const void *);
  47 static cp_lvalue_kind lvalue_p_1 (tree, int);
  48 static tree build_target_expr (tree, tree);
  49 static tree count_trees_r (tree *, int *, void *);
  50 static tree verify_stmt_tree_r (tree *, int *, void *);
  51 static tree build_local_temp (tree);
  52
  53 static tree handle_java_interface_attribute (tree *, tree, tree, int, bool *);
  54 static tree handle_com_interface_attribute (tree *, tree, tree, int, bool *);
  55 static tree handle_init_priority_attribute (tree *, tree, tree, int, bool *);
  56
  57 /* If REF is an lvalue, returns the kind of lvalue that REF is.
  58    Otherwise, returns clk_none.  If TREAT_CLASS_RVALUES_AS_LVALUES is
  59    nonzero, rvalues of class type are considered lvalues.  */
  60
  61 static cp_lvalue_kind
  62 lvalue_p_1 (tree ref,
  63             int treat_class_rvalues_as_lvalues)
  64 {
  65   cp_lvalue_kind op1_lvalue_kind = clk_none;
  66   cp_lvalue_kind op2_lvalue_kind = clk_none;
  67
  68   /* Expressions of reference type are sometimes wrapped in
  69      INDIRECT_REFs.  INDIRECT_REFs are just internal compiler
  70      representation, not part of the language, so we have to look
  71      through them.  */
  72   if (TREE_CODE (ref) == INDIRECT_REF
  73       && TREE_CODE (TREE_TYPE (TREE_OPERAND (ref, 0)))
  74           == REFERENCE_TYPE)
  75     return lvalue_p_1 (TREE_OPERAND (ref, 0),
  76                        treat_class_rvalues_as_lvalues);
  77
  78   if (TREE_CODE (TREE_TYPE (ref)) == REFERENCE_TYPE)
  79     {
  80       /* unnamed rvalue references are rvalues */
  81       if (TYPE_REF_IS_RVALUE (TREE_TYPE (ref))
  82           && TREE_CODE (ref) != PARM_DECL
  83           && TREE_CODE (ref) != VAR_DECL
  84           && TREE_CODE (ref) != COMPONENT_REF)
  85         return clk_none;
  86
  87       /* lvalue references and named rvalue references are lvalues.  */
  88       return clk_ordinary;
  89     }
  90
  91   if (ref == current_class_ptr)
  92     return clk_none;
  93
  94   switch (TREE_CODE (ref))
  95     {
  96     case SAVE_EXPR:
  97       return clk_none;
  98       /* preincrements and predecrements are valid lvals, provided
  99          what they refer to are valid lvals.  */
 100     case PREINCREMENT_EXPR:
 101     case PREDECREMENT_EXPR:
 102     case TRY_CATCH_EXPR:
 103     case WITH_CLEANUP_EXPR:
 104     case REALPART_EXPR:
 105     case IMAGPART_EXPR:
 106       return lvalue_p_1 (TREE_OPERAND (ref, 0),
 107                          treat_class_rvalues_as_lvalues);
 108
 109     case COMPONENT_REF:
 110       op1_lvalue_kind = lvalue_p_1 (TREE_OPERAND (ref, 0),
 111                                     treat_class_rvalues_as_lvalues);
 112       /* Look at the member designator.  */
 113       if (!op1_lvalue_kind)
 114         ;
 115       else if (is_overloaded_fn (TREE_OPERAND (ref, 1)))
 116         /* The "field" can be a FUNCTION_DECL or an OVERLOAD in some
 117            situations.  If we're seeing a COMPONENT_REF, it's a non-static
 118            member, so it isn't an lvalue. */
 119         op1_lvalue_kind = clk_none;
 120       else if (TREE_CODE (TREE_OPERAND (ref, 1)) != FIELD_DECL)
 121         /* This can be IDENTIFIER_NODE in a template.  */;
 122       else if (DECL_C_BIT_FIELD (TREE_OPERAND (ref, 1)))
 123         {
 124           /* Clear the ordinary bit.  If this object was a class
 125              rvalue we want to preserve that information.  */
 126           op1_lvalue_kind &= ~clk_ordinary;
 127           /* The lvalue is for a bitfield.  */
 128           op1_lvalue_kind |= clk_bitfield;
 129         }
 130       else if (DECL_PACKED (TREE_OPERAND (ref, 1)))
 131         op1_lvalue_kind |= clk_packed;
 132
 133       return op1_lvalue_kind;
 134
 135     case STRING_CST:
 136     case COMPOUND_LITERAL_EXPR:
 137       return clk_ordinary;
 138
 139     case CONST_DECL:
 140     case VAR_DECL:
 141       if (TREE_READONLY (ref) && ! TREE_STATIC (ref)
 142           && DECL_LANG_SPECIFIC (ref)
 143           && DECL_IN_AGGR_P (ref))
 144         return clk_none;
 145     case INDIRECT_REF:
 146     case ARRAY_REF:
 147     case PARM_DECL:
 148     case RESULT_DECL:
 149       if (TREE_CODE (TREE_TYPE (ref)) != METHOD_TYPE)
 150         return clk_ordinary;
 151       break;
 152
 153       /* A currently unresolved scope ref.  */
 154     case SCOPE_REF:
 155       gcc_unreachable ();
 156     case MAX_EXPR:
 157     case MIN_EXPR:
 158       /* Disallow <? and >? as lvalues if either argument side-effects.  */
 159       if (TREE_SIDE_EFFECTS (TREE_OPERAND (ref, 0))
 160           || TREE_SIDE_EFFECTS (TREE_OPERAND (ref, 1)))
 161         return clk_none;
 162       op1_lvalue_kind = lvalue_p_1 (TREE_OPERAND (ref, 0),
 163                                     treat_class_rvalues_as_lvalues);
 164       op2_lvalue_kind = lvalue_p_1 (TREE_OPERAND (ref, 1),
 165                                     treat_class_rvalues_as_lvalues);
 166       break;
 167
 168     case COND_EXPR:
 169       op1_lvalue_kind = lvalue_p_1 (TREE_OPERAND (ref, 1)
 170                                     ? TREE_OPERAND (ref, 1)
 171                                     : TREE_OPERAND (ref, 0),
 172                                     treat_class_rvalues_as_lvalues);
 173       op2_lvalue_kind = lvalue_p_1 (TREE_OPERAND (ref, 2),
 174                                     treat_class_rvalues_as_lvalues);
 175       break;
 176
 177     case MODIFY_EXPR:
 178       return clk_ordinary;
 179
 180     case COMPOUND_EXPR:
 181       return lvalue_p_1 (TREE_OPERAND (ref, 1),
 182                          treat_class_rvalues_as_lvalues);
 183
 184     case TARGET_EXPR:
 185       return treat_class_rvalues_as_lvalues ? clk_class : clk_none;
 186
 187     case VA_ARG_EXPR:
 188       return (treat_class_rvalues_as_lvalues
 189               && CLASS_TYPE_P (TREE_TYPE (ref))
 190               ? clk_class : clk_none);
 191
 192     case CALL_EXPR:
 193       /* Any class-valued call would be wrapped in a TARGET_EXPR.  */
 194       return clk_none;
 195
 196     case FUNCTION_DECL:
 197       /* All functions (except non-static-member functions) are
 198          lvalues.  */
 199       return (DECL_NONSTATIC_MEMBER_FUNCTION_P (ref)
 200               ? clk_none : clk_ordinary);
 201
 202     case BASELINK:
 203       /* We now represent a reference to a single static member function
 204          with a BASELINK.  */
 205       return lvalue_p_1 (BASELINK_FUNCTIONS (ref),
 206                          treat_class_rvalues_as_lvalues);
 207
 208     case NON_DEPENDENT_EXPR:
 209       /* We must consider NON_DEPENDENT_EXPRs to be lvalues so that
 210          things like "&E" where "E" is an expression with a
 211          non-dependent type work. It is safe to be lenient because an
 212          error will be issued when the template is instantiated if "E"
 213          is not an lvalue.  */
 214       return clk_ordinary;
 215
 216     default:
 217       break;
 218     }
 219
 220   /* If one operand is not an lvalue at all, then this expression is
 221      not an lvalue.  */
 222   if (!op1_lvalue_kind || !op2_lvalue_kind)
 223     return clk_none;
 224
 225   /* Otherwise, it's an lvalue, and it has all the odd properties
 226      contributed by either operand.  */
 227   op1_lvalue_kind = op1_lvalue_kind | op2_lvalue_kind;
 228   /* It's not an ordinary lvalue if it involves either a bit-field or
 229      a class rvalue.  */
 230   if ((op1_lvalue_kind & ~clk_ordinary) != clk_none)
 231     op1_lvalue_kind &= ~clk_ordinary;
 232   return op1_lvalue_kind;
 233 }
 234
 235 /* Returns the kind of lvalue that REF is, in the sense of
 236    [basic.lval].  This function should really be named lvalue_p; it
 237    computes the C++ definition of lvalue.  */
 238
 239 cp_lvalue_kind
 240 real_lvalue_p (tree ref)
 241 {
 242   return lvalue_p_1 (ref,
 243                      /*treat_class_rvalues_as_lvalues=*/0);
 244 }
 245
 246 /* This differs from real_lvalue_p in that class rvalues are
 247    considered lvalues.  */
 248
 249 int
 250 lvalue_p (tree ref)
 251 {
 252   return
 253     (lvalue_p_1 (ref, /*class rvalue ok*/ 1) != clk_none);
 254 }
 255
 256 /* Test whether DECL is a builtin that may appear in a
 257    constant-expression. */
 258
 259 bool
 260 builtin_valid_in_constant_expr_p (const_tree decl)
 261 {
 262   /* At present BUILT_IN_CONSTANT_P is the only builtin we're allowing
 263      in constant-expressions.  We may want to add other builtins later. */
 264   return DECL_IS_BUILTIN_CONSTANT_P (decl);
 265 }
 266
 267 /* Build a TARGET_EXPR, initializing the DECL with the VALUE.  */
 268
 269 static tree
 270 build_target_expr (tree decl, tree value)
 271 {
 272   tree t;
 273
 274 #ifdef ENABLE_CHECKING
 275   gcc_assert (VOID_TYPE_P (TREE_TYPE (value))
 276               || TREE_TYPE (decl) == TREE_TYPE (value)
 277               || useless_type_conversion_p (TREE_TYPE (decl),
 278                                             TREE_TYPE (value)));
 279 #endif
 280
 281   t = build4 (TARGET_EXPR, TREE_TYPE (decl), decl, value,
 282               cxx_maybe_build_cleanup (decl), NULL_TREE);
 283   /* We always set TREE_SIDE_EFFECTS so that expand_expr does not
 284      ignore the TARGET_EXPR.  If there really turn out to be no
 285      side-effects, then the optimizer should be able to get rid of
 286      whatever code is generated anyhow.  */
 287   TREE_SIDE_EFFECTS (t) = 1;
 288
 289   return t;
 290 }
 291
 292 /* Return an undeclared local temporary of type TYPE for use in building a
 293    TARGET_EXPR.  */
 294
 295 static tree
 296 build_local_temp (tree type)
 297 {
 298   tree slot = build_decl (VAR_DECL, NULL_TREE, type);
 299   DECL_ARTIFICIAL (slot) = 1;
 300   DECL_IGNORED_P (slot) = 1;
 301   DECL_CONTEXT (slot) = current_function_decl;
 302   layout_decl (slot, 0);
 303   return slot;
 304 }
 305
 306 /* Set various status flags when building an AGGR_INIT_EXPR object T.  */
 307
 308 static void
 309 process_aggr_init_operands (tree t)
 310 {
 311   bool side_effects;
 312
 313   side_effects = TREE_SIDE_EFFECTS (t);
 314   if (!side_effects)
 315     {
 316       int i, n;
 317       n = TREE_OPERAND_LENGTH (t);
 318       for (i = 1; i < n; i++)
 319         {
 320           tree op = TREE_OPERAND (t, i);
 321           if (op && TREE_SIDE_EFFECTS (op))
 322             {
 323               side_effects = 1;
 324               break;
 325             }
 326         }
 327     }
 328   TREE_SIDE_EFFECTS (t) = side_effects;
 329 }
 330
 331 /* Build an AGGR_INIT_EXPR of class tcc_vl_exp with the indicated RETURN_TYPE,
 332    FN, and SLOT.  NARGS is the number of call arguments which are specified
 333    as a tree array ARGS.  */
 334
 335 static tree
 336 build_aggr_init_array (tree return_type, tree fn, tree slot, int nargs,
 337                        tree *args)
 338 {
 339   tree t;
 340   int i;
 341
 342   t = build_vl_exp (AGGR_INIT_EXPR, nargs + 3);
 343   TREE_TYPE (t) = return_type;
 344   AGGR_INIT_EXPR_FN (t) = fn;
 345   AGGR_INIT_EXPR_SLOT (t) = slot;
 346   for (i = 0; i < nargs; i++)
 347     AGGR_INIT_EXPR_ARG (t, i) = args[i];
 348   process_aggr_init_operands (t);
 349   return t;
 350 }
 351
 352 /* INIT is a CALL_EXPR or AGGR_INIT_EXPR which needs info about its
 353    target.  TYPE is the type to be initialized.
 354
 355    Build an AGGR_INIT_EXPR to represent the initialization.  This function
 356    differs from build_cplus_new in that an AGGR_INIT_EXPR can only be used
 357    to initialize another object, whereas a TARGET_EXPR can either
 358    initialize another object or create its own temporary object, and as a
 359    result building up a TARGET_EXPR requires that the type's destructor be
 360    callable.  */
 361
 362 tree
 363 build_aggr_init_expr (tree type, tree init)
 364 {
 365   tree fn;
 366   tree slot;
 367   tree rval;
 368   int is_ctor;
 369
 370   /* Make sure that we're not trying to create an instance of an
 371      abstract class.  */
 372   abstract_virtuals_error (NULL_TREE, type);
 373
 374   if (TREE_CODE (init) == CALL_EXPR)
 375     fn = CALL_EXPR_FN (init);
 376   else if (TREE_CODE (init) == AGGR_INIT_EXPR)
 377     fn = AGGR_INIT_EXPR_FN (init);
 378   else
 379     return convert (type, init);
 380
 381   is_ctor = (TREE_CODE (fn) == ADDR_EXPR
 382              && TREE_CODE (TREE_OPERAND (fn, 0)) == FUNCTION_DECL
 383              && DECL_CONSTRUCTOR_P (TREE_OPERAND (fn, 0)));
 384
 385   /* We split the CALL_EXPR into its function and its arguments here.
 386      Then, in expand_expr, we put them back together.  The reason for
 387      this is that this expression might be a default argument
 388      expression.  In that case, we need a new temporary every time the
 389      expression is used.  That's what break_out_target_exprs does; it
 390      replaces every AGGR_INIT_EXPR with a copy that uses a fresh
 391      temporary slot.  Then, expand_expr builds up a call-expression
 392      using the new slot.  */
 393
 394   /* If we don't need to use a constructor to create an object of this
 395      type, don't mess with AGGR_INIT_EXPR.  */
 396   if (is_ctor || TREE_ADDRESSABLE (type))
 397     {
 398       slot = build_local_temp (type);
 399
 400       if (TREE_CODE(init) == CALL_EXPR)
 401         rval = build_aggr_init_array (void_type_node, fn, slot,
 402                                       call_expr_nargs (init),
 403                                       CALL_EXPR_ARGP (init));
 404       else
 405         rval = build_aggr_init_array (void_type_node, fn, slot,
 406                                       aggr_init_expr_nargs (init),
 407                                       AGGR_INIT_EXPR_ARGP (init));
 408       TREE_SIDE_EFFECTS (rval) = 1;
 409       AGGR_INIT_VIA_CTOR_P (rval) = is_ctor;
 410     }
 411   else
 412     rval = init;
 413
 414   return rval;
 415 }
 416
 417 /* INIT is a CALL_EXPR or AGGR_INIT_EXPR which needs info about its
 418    target.  TYPE is the type that this initialization should appear to
 419    have.
 420
 421    Build an encapsulation of the initialization to perform
 422    and return it so that it can be processed by language-independent
 423    and language-specific expression expanders.  */
 424
 425 tree
 426 build_cplus_new (tree type, tree init)
 427 {
 428   tree rval = build_aggr_init_expr (type, init);
 429   tree slot;
 430
 431   if (TREE_CODE (rval) == AGGR_INIT_EXPR)
 432     slot = AGGR_INIT_EXPR_SLOT (rval);
 433   else if (TREE_CODE (rval) == CALL_EXPR)
 434     slot = build_local_temp (type);
 435   else
 436     return rval;
 437
 438   rval = build_target_expr (slot, rval);
 439   TARGET_EXPR_IMPLICIT_P (rval) = 1;
 440
 441   return rval;
 442 }
 443
 444 /* Build a TARGET_EXPR using INIT to initialize a new temporary of the
 445    indicated TYPE.  */
 446
 447 tree
 448 build_target_expr_with_type (tree init, tree type)
 449 {
 450   gcc_assert (!VOID_TYPE_P (type));
 451
 452   if (TREE_CODE (init) == TARGET_EXPR)
 453     return init;
 454   else if (CLASS_TYPE_P (type) && !TYPE_HAS_TRIVIAL_INIT_REF (type)
 455            && !VOID_TYPE_P (TREE_TYPE (init))
 456            && TREE_CODE (init) != COND_EXPR
 457            && TREE_CODE (init) != CONSTRUCTOR
 458            && TREE_CODE (init) != VA_ARG_EXPR)
 459     /* We need to build up a copy constructor call.  A void initializer
 460        means we're being called from bot_manip.  COND_EXPR is a special
 461        case because we already have copies on the arms and we don't want
 462        another one here.  A CONSTRUCTOR is aggregate initialization, which
 463        is handled separately.  A VA_ARG_EXPR is magic creation of an
 464        aggregate; there's no additional work to be done.  */
 465     return force_rvalue (init);
 466
 467   return force_target_expr (type, init);
 468 }
 469
 470 /* Like the above function, but without the checking.  This function should
 471    only be used by code which is deliberately trying to subvert the type
 472    system, such as call_builtin_trap.  */
 473
 474 tree
 475 force_target_expr (tree type, tree init)
 476 {
 477   tree slot;
 478
 479   gcc_assert (!VOID_TYPE_P (type));
 480
 481   slot = build_local_temp (type);
 482   return build_target_expr (slot, init);
 483 }
 484
 485 /* Like build_target_expr_with_type, but use the type of INIT.  */
 486
 487 tree
 488 get_target_expr (tree init)
 489 {
 490   return build_target_expr_with_type (init, TREE_TYPE (init));
 491 }
 492
 493 /* If EXPR is a bitfield reference, convert it to the declared type of
 494    the bitfield, and return the resulting expression.  Otherwise,
 495    return EXPR itself.  */
 496
 497 tree
 498 convert_bitfield_to_declared_type (tree expr)
 499 {
 500   tree bitfield_type;
 501
 502   bitfield_type = is_bitfield_expr_with_lowered_type (expr);
 503   if (bitfield_type)
 504     expr = convert_to_integer (TYPE_MAIN_VARIANT (bitfield_type),
 505                                expr);
 506   return expr;
 507 }
 508
 509 /* EXPR is being used in an rvalue context.  Return a version of EXPR
 510    that is marked as an rvalue.  */
 511
 512 tree
 513 rvalue (tree expr)
 514 {
 515   tree type;
 516
 517   if (error_operand_p (expr))
 518     return expr;
 519
 520   /* [basic.lval]
 521
 522      Non-class rvalues always have cv-unqualified types.  */
 523   type = TREE_TYPE (expr);
 524   if (!CLASS_TYPE_P (type) && cp_type_quals (type))
 525     type = TYPE_MAIN_VARIANT (type);
 526
 527   if (!processing_template_decl && real_lvalue_p (expr))
 528     expr = build1 (NON_LVALUE_EXPR, type, expr);
 529   else if (type != TREE_TYPE (expr))
 530     expr = build_nop (type, expr);
 531
 532   return expr;
 533 }
 534
 535 \f
 536 /* Hash an ARRAY_TYPE.  K is really of type `tree'.  */
 537
 538 static hashval_t
 539 cplus_array_hash (const void* k)
 540 {
 541   hashval_t hash;
 542   const_tree const t = (const_tree) k;
 543
 544   hash = TYPE_UID (TREE_TYPE (t));
 545   if (TYPE_DOMAIN (t))
 546     hash ^= TYPE_UID (TYPE_DOMAIN (t));
 547   return hash;
 548 }
 549
 550 typedef struct cplus_array_info {
 551   tree type;
 552   tree domain;
 553 } cplus_array_info;
 554
 555 /* Compare two ARRAY_TYPEs.  K1 is really of type `tree', K2 is really
 556    of type `cplus_array_info*'. */
 557
 558 static int
 559 cplus_array_compare (const void * k1, const void * k2)
 560 {
 561   const_tree const t1 = (const_tree) k1;
 562   const cplus_array_info *const t2 = (const cplus_array_info*) k2;
 563
 564   return (TREE_TYPE (t1) == t2->type && TYPE_DOMAIN (t1) == t2->domain);
 565 }
 566
 567 /* Hash table containing all of the C++ array types, including
 568    dependent array types and array types whose element type is
 569    cv-qualified.  */
 570 static GTY ((param_is (union tree_node))) htab_t cplus_array_htab;
 571
 572
 573 static tree
 574 build_cplus_array_type_1 (tree elt_type, tree index_type)
 575 {
 576   tree t;
 577
 578   if (elt_type == error_mark_node || index_type == error_mark_node)
 579     return error_mark_node;
 580
 581   if (processing_template_decl
 582       && (dependent_type_p (elt_type)
 583           || (index_type && !TREE_CONSTANT (TYPE_MAX_VALUE (index_type)))))
 584     {
 585       void **e;
 586       cplus_array_info cai;
 587       hashval_t hash;
 588
 589       if (cplus_array_htab == NULL)
 590         cplus_array_htab = htab_create_ggc (61, &cplus_array_hash,
 591                                             &cplus_array_compare, NULL);
 592
 593       hash = TYPE_UID (elt_type);
 594       if (index_type)
 595         hash ^= TYPE_UID (index_type);
 596       cai.type = elt_type;
 597       cai.domain = index_type;
 598
 599       e = htab_find_slot_with_hash (cplus_array_htab, &cai, hash, INSERT);
 600       if (*e)
 601         /* We have found the type: we're done.  */
 602         return (tree) *e;
 603       else
 604         {
 605           /* Build a new array type.  */
 606           t = make_node (ARRAY_TYPE);
 607           TREE_TYPE (t) = elt_type;
 608           TYPE_DOMAIN (t) = index_type;
 609
 610           /* Store it in the hash table. */
 611           *e = t;
 612
 613           /* Set the canonical type for this new node.  */
 614           if (TYPE_STRUCTURAL_EQUALITY_P (elt_type)
 615               || (index_type && TYPE_STRUCTURAL_EQUALITY_P (index_type)))
 616             SET_TYPE_STRUCTURAL_EQUALITY (t);
 617           else if (TYPE_CANONICAL (elt_type) != elt_type
 618                    || (index_type
 619                        && TYPE_CANONICAL (index_type) != index_type))
 620             TYPE_CANONICAL (t)
 621                 = build_cplus_array_type
 622                    (TYPE_CANONICAL (elt_type),
 623                     index_type ? TYPE_CANONICAL (index_type) : index_type);
 624           else
 625             TYPE_CANONICAL (t) = t;
 626         }
 627     }
 628   else
 629     t = build_array_type (elt_type, index_type);
 630
 631   /* Push these needs up so that initialization takes place
 632      more easily.  */
 633   TYPE_NEEDS_CONSTRUCTING (t)
 634     = TYPE_NEEDS_CONSTRUCTING (TYPE_MAIN_VARIANT (elt_type));
 635   TYPE_HAS_NONTRIVIAL_DESTRUCTOR (t)
 636     = TYPE_HAS_NONTRIVIAL_DESTRUCTOR (TYPE_MAIN_VARIANT (elt_type));
 637   return t;
 638 }
 639
 640 tree
 641 build_cplus_array_type (tree elt_type, tree index_type)
 642 {
 643   tree t;
 644   int type_quals = cp_type_quals (elt_type);
 645
 646   if (type_quals != TYPE_UNQUALIFIED)
 647     elt_type = cp_build_qualified_type (elt_type, TYPE_UNQUALIFIED);
 648
 649   t = build_cplus_array_type_1 (elt_type, index_type);
 650
 651   if (type_quals != TYPE_UNQUALIFIED)
 652     t = cp_build_qualified_type (t, type_quals);
 653
 654   return t;
 655 }
 656
 657 /* Return an ARRAY_TYPE with element type ELT and length N.  */
 658
 659 tree
 660 build_array_of_n_type (tree elt, int n)
 661 {
 662   return build_cplus_array_type (elt, build_index_type (size_int (n - 1)));
 663 }
 664
 665 /* Return a reference type node referring to TO_TYPE.  If RVAL is
 666    true, return an rvalue reference type, otherwise return an lvalue
 667    reference type.  If a type node exists, reuse it, otherwise create
 668    a new one.  */
 669 tree
 670 cp_build_reference_type (tree to_type, bool rval)
 671 {
 672   tree lvalue_ref, t;
 673   lvalue_ref = build_reference_type (to_type);
 674   if (!rval)
 675     return lvalue_ref;
 676
 677   /* This code to create rvalue reference types is based on and tied
 678      to the code creating lvalue reference types in the middle-end
 679      functions build_reference_type_for_mode and build_reference_type.
 680
 681      It works by putting the rvalue reference type nodes after the
 682      lvalue reference nodes in the TYPE_NEXT_REF_TO linked list, so
 683      they will effectively be ignored by the middle end.  */
 684
 685   for (t = lvalue_ref; (t = TYPE_NEXT_REF_TO (t)); )
 686     if (TYPE_REF_IS_RVALUE (t))
 687       return t;
 688
 689   t = copy_node (lvalue_ref);
 690
 691   TYPE_REF_IS_RVALUE (t) = true;
 692   TYPE_NEXT_REF_TO (t) = TYPE_NEXT_REF_TO (lvalue_ref);
 693   TYPE_NEXT_REF_TO (lvalue_ref) = t;
 694   TYPE_MAIN_VARIANT (t) = t;
 695
 696   if (TYPE_STRUCTURAL_EQUALITY_P (to_type))
 697     SET_TYPE_STRUCTURAL_EQUALITY (t);
 698   else if (TYPE_CANONICAL (to_type) != to_type)
 699     TYPE_CANONICAL (t)
 700       = cp_build_reference_type (TYPE_CANONICAL (to_type), rval);
 701   else
 702     TYPE_CANONICAL (t) = t;
 703
 704   layout_type (t);
 705
 706   return t;
 707
 708 }
 709
 710 /* Used by the C++ front end to build qualified array types.  However,
 711    the C version of this function does not properly maintain canonical
 712    types (which are not used in C).  */
 713 tree
 714 c_build_qualified_type (tree type, int type_quals)
 715 {
 716   return cp_build_qualified_type (type, type_quals);
 717 }
 718
 719 \f
 720 /* Make a variant of TYPE, qualified with the TYPE_QUALS.  Handles
 721    arrays correctly.  In particular, if TYPE is an array of T's, and
 722    TYPE_QUALS is non-empty, returns an array of qualified T's.
 723
 724    FLAGS determines how to deal with ill-formed qualifications. If
 725    tf_ignore_bad_quals is set, then bad qualifications are dropped
 726    (this is permitted if TYPE was introduced via a typedef or template
 727    type parameter). If bad qualifications are dropped and tf_warning
 728    is set, then a warning is issued for non-const qualifications.  If
 729    tf_ignore_bad_quals is not set and tf_error is not set, we
 730    return error_mark_node. Otherwise, we issue an error, and ignore
 731    the qualifications.
 732
 733    Qualification of a reference type is valid when the reference came
 734    via a typedef or template type argument. [dcl.ref] No such
 735    dispensation is provided for qualifying a function type.  [dcl.fct]
 736    DR 295 queries this and the proposed resolution brings it into line
 737    with qualifying a reference.  We implement the DR.  We also behave
 738    in a similar manner for restricting non-pointer types.  */
 739
 740 tree
 741 cp_build_qualified_type_real (tree type,
 742                               int type_quals,
 743                               tsubst_flags_t complain)
 744 {
 745   tree result;
 746   int bad_quals = TYPE_UNQUALIFIED;
 747
 748   if (type == error_mark_node)
 749     return type;
 750
 751   if (type_quals == cp_type_quals (type))
 752     return type;
 753
 754   if (TREE_CODE (type) == ARRAY_TYPE)
 755     {
 756       /* In C++, the qualification really applies to the array element
 757          type.  Obtain the appropriately qualified element type.  */
 758       tree t;
 759       tree element_type
 760         = cp_build_qualified_type_real (TREE_TYPE (type),
 761                                         type_quals,
 762                                         complain);
 763
 764       if (element_type == error_mark_node)
 765         return error_mark_node;
 766
 767       /* See if we already have an identically qualified type.  */
 768       for (t = TYPE_MAIN_VARIANT (type); t; t = TYPE_NEXT_VARIANT (t))
 769         if (cp_type_quals (t) == type_quals
 770             && TYPE_NAME (t) == TYPE_NAME (type)
 771             && TYPE_CONTEXT (t) == TYPE_CONTEXT (type))
 772           break;
 773
 774       if (!t)
 775       {
 776         t = build_cplus_array_type_1 (element_type, TYPE_DOMAIN (type));
 777
 778         if (TYPE_MAIN_VARIANT (t) != TYPE_MAIN_VARIANT (type))
 779           {
 780             /* Set the main variant of the newly-created ARRAY_TYPE
 781                (with cv-qualified element type) to the main variant of
 782                the unqualified ARRAY_TYPE we started with.  */
 783             tree last_variant = t;
 784             tree m = TYPE_MAIN_VARIANT (type);
 785
 786             /* Find the last variant on the new ARRAY_TYPEs list of
 787                variants, setting the main variant of each of the other
 788                types to the main variant of our unqualified
 789                ARRAY_TYPE.  */
 790             while (TYPE_NEXT_VARIANT (last_variant))
 791               {
 792                 TYPE_MAIN_VARIANT (last_variant) = m;
 793                 last_variant = TYPE_NEXT_VARIANT (last_variant);
 794               }
 795
 796             /* Splice in the newly-created variants.  */
 797             TYPE_NEXT_VARIANT (last_variant) = TYPE_NEXT_VARIANT (m);
 798             TYPE_NEXT_VARIANT (m) = t;
 799             TYPE_MAIN_VARIANT (last_variant) = m;
 800           }
 801       }
 802
 803       /* Even if we already had this variant, we update
 804          TYPE_NEEDS_CONSTRUCTING and TYPE_HAS_NONTRIVIAL_DESTRUCTOR in case
 805          they changed since the variant was originally created.
 806
 807          This seems hokey; if there is some way to use a previous
 808          variant *without* coming through here,
 809          TYPE_NEEDS_CONSTRUCTING will never be updated.  */
 810       TYPE_NEEDS_CONSTRUCTING (t)
 811         = TYPE_NEEDS_CONSTRUCTING (TYPE_MAIN_VARIANT (element_type));
 812       TYPE_HAS_NONTRIVIAL_DESTRUCTOR (t)
 813         = TYPE_HAS_NONTRIVIAL_DESTRUCTOR (TYPE_MAIN_VARIANT (element_type));
 814       return t;
 815     }
 816   else if (TYPE_PTRMEMFUNC_P (type))
 817     {
 818       /* For a pointer-to-member type, we can't just return a
 819          cv-qualified version of the RECORD_TYPE.  If we do, we
 820          haven't changed the field that contains the actual pointer to
 821          a method, and so TYPE_PTRMEMFUNC_FN_TYPE will be wrong.  */
 822       tree t;
 823
 824       t = TYPE_PTRMEMFUNC_FN_TYPE (type);
 825       t = cp_build_qualified_type_real (t, type_quals, complain);
 826       return build_ptrmemfunc_type (t);
 827     }
 828   else if (TREE_CODE (type) == TYPE_PACK_EXPANSION)
 829     {
 830       tree t = PACK_EXPANSION_PATTERN (type);
 831
 832       t = cp_build_qualified_type_real (t, type_quals, complain);
 833       return make_pack_expansion (t);
 834     }
 835
 836   /* A reference or method type shall not be cv-qualified.
 837      [dcl.ref], [dcl.fct]  */
 838   if (type_quals & (TYPE_QUAL_CONST | TYPE_QUAL_VOLATILE)
 839       && (TREE_CODE (type) == REFERENCE_TYPE
 840           || TREE_CODE (type) == METHOD_TYPE))
 841     {
 842       bad_quals |= type_quals & (TYPE_QUAL_CONST | TYPE_QUAL_VOLATILE);
 843       type_quals &= ~(TYPE_QUAL_CONST | TYPE_QUAL_VOLATILE);
 844     }
 845
 846   /* A restrict-qualified type must be a pointer (or reference)
 847      to object or incomplete type, or a function type. */
 848   if ((type_quals & TYPE_QUAL_RESTRICT)
 849       && TREE_CODE (type) != TEMPLATE_TYPE_PARM
 850       && TREE_CODE (type) != TYPENAME_TYPE
 851       && TREE_CODE (type) != FUNCTION_TYPE
 852       && !POINTER_TYPE_P (type))
 853     {
 854       bad_quals |= TYPE_QUAL_RESTRICT;
 855       type_quals &= ~TYPE_QUAL_RESTRICT;
 856     }
 857
 858   if (bad_quals == TYPE_UNQUALIFIED)
 859     /*OK*/;
 860   else if (!(complain & (tf_error | tf_ignore_bad_quals)))
 861     return error_mark_node;
 862   else
 863     {
 864       if (complain & tf_ignore_bad_quals)
 865         /* We're not going to warn about constifying things that can't
 866            be constified.  */
 867         bad_quals &= ~TYPE_QUAL_CONST;
 868       if (bad_quals)
 869         {
 870           tree bad_type = build_qualified_type (ptr_type_node, bad_quals);
 871
 872           if (!(complain & tf_ignore_bad_quals))
 873             error ("%qV qualifiers cannot be applied to %qT",
 874                    bad_type, type);
 875         }
 876     }
 877
 878   /* Retrieve (or create) the appropriately qualified variant.  */
 879   result = build_qualified_type (type, type_quals);
 880
 881   /* If this was a pointer-to-method type, and we just made a copy,
 882      then we need to unshare the record that holds the cached
 883      pointer-to-member-function type, because these will be distinct
 884      between the unqualified and qualified types.  */
 885   if (result != type
 886       && TREE_CODE (type) == POINTER_TYPE
 887       && TREE_CODE (TREE_TYPE (type)) == METHOD_TYPE
 888       && TYPE_LANG_SPECIFIC (result) == TYPE_LANG_SPECIFIC (type))
 889     TYPE_LANG_SPECIFIC (result) = NULL;
 890
 891   /* We may also have ended up building a new copy of the canonical
 892      type of a pointer-to-method type, which could have the same
 893      sharing problem described above.  */
 894   if (TYPE_CANONICAL (result) != TYPE_CANONICAL (type)
 895       && TREE_CODE (type) == POINTER_TYPE
 896       && TREE_CODE (TREE_TYPE (type)) == METHOD_TYPE
 897       && (TYPE_LANG_SPECIFIC (TYPE_CANONICAL (result))
 898           == TYPE_LANG_SPECIFIC (TYPE_CANONICAL (type))))
 899     TYPE_LANG_SPECIFIC (TYPE_CANONICAL (result)) = NULL;
 900
 901
 902   return result;
 903 }
 904
 905 /* Returns the canonical version of TYPE.  In other words, if TYPE is
 906    a typedef, returns the underlying type.  The cv-qualification of
 907    the type returned matches the type input; they will always be
 908    compatible types.  */
 909
 910 tree
 911 canonical_type_variant (tree t)
 912 {
 913   if (t == error_mark_node)
 914     return error_mark_node;
 915
 916   return cp_build_qualified_type (TYPE_MAIN_VARIANT (t), cp_type_quals (t));
 917 }
 918 \f
 919 /* Makes a copy of BINFO and TYPE, which is to be inherited into a
 920    graph dominated by T.  If BINFO is NULL, TYPE is a dependent base,
 921    and we do a shallow copy.  If BINFO is non-NULL, we do a deep copy.
 922    VIRT indicates whether TYPE is inherited virtually or not.
 923    IGO_PREV points at the previous binfo of the inheritance graph
 924    order chain.  The newly copied binfo's TREE_CHAIN forms this
 925    ordering.
 926
 927    The CLASSTYPE_VBASECLASSES vector of T is constructed in the
 928    correct order. That is in the order the bases themselves should be
 929    constructed in.
 930
 931    The BINFO_INHERITANCE of a virtual base class points to the binfo
 932    of the most derived type. ??? We could probably change this so that
 933    BINFO_INHERITANCE becomes synonymous with BINFO_PRIMARY, and hence
 934    remove a field.  They currently can only differ for primary virtual
 935    virtual bases.  */
 936
 937 tree
 938 copy_binfo (tree binfo, tree type, tree t, tree *igo_prev, int virt)
 939 {
 940   tree new_binfo;
 941
 942   if (virt)
 943     {
 944       /* See if we've already made this virtual base.  */
 945       new_binfo = binfo_for_vbase (type, t);
 946       if (new_binfo)
 947         return new_binfo;
 948     }
 949
 950   new_binfo = make_tree_binfo (binfo ? BINFO_N_BASE_BINFOS (binfo) : 0);
 951   BINFO_TYPE (new_binfo) = type;
 952
 953   /* Chain it into the inheritance graph.  */
 954   TREE_CHAIN (*igo_prev) = new_binfo;
 955   *igo_prev = new_binfo;
 956
 957   if (binfo)
 958     {
 959       int ix;
 960       tree base_binfo;
 961
 962       gcc_assert (!BINFO_DEPENDENT_BASE_P (binfo));
 963       gcc_assert (SAME_BINFO_TYPE_P (BINFO_TYPE (binfo), type));
 964
 965       BINFO_OFFSET (new_binfo) = BINFO_OFFSET (binfo);
 966       BINFO_VIRTUALS (new_binfo) = BINFO_VIRTUALS (binfo);
 967
 968       /* We do not need to copy the accesses, as they are read only.  */
 969       BINFO_BASE_ACCESSES (new_binfo) = BINFO_BASE_ACCESSES (binfo);
 970
 971       /* Recursively copy base binfos of BINFO.  */
 972       for (ix = 0; BINFO_BASE_ITERATE (binfo, ix, base_binfo); ix++)
 973         {
 974           tree new_base_binfo;
 975
 976           gcc_assert (!BINFO_DEPENDENT_BASE_P (base_binfo));
 977           new_base_binfo = copy_binfo (base_binfo, BINFO_TYPE (base_binfo),
 978                                        t, igo_prev,
 979                                        BINFO_VIRTUAL_P (base_binfo));
 980
 981           if (!BINFO_INHERITANCE_CHAIN (new_base_binfo))
 982             BINFO_INHERITANCE_CHAIN (new_base_binfo) = new_binfo;
 983           BINFO_BASE_APPEND (new_binfo, new_base_binfo);
 984         }
 985     }
 986   else
 987     BINFO_DEPENDENT_BASE_P (new_binfo) = 1;
 988
 989   if (virt)
 990     {
 991       /* Push it onto the list after any virtual bases it contains
 992          will have been pushed.  */
 993       VEC_quick_push (tree, CLASSTYPE_VBASECLASSES (t), new_binfo);
 994       BINFO_VIRTUAL_P (new_binfo) = 1;
 995       BINFO_INHERITANCE_CHAIN (new_binfo) = TYPE_BINFO (t);
 996     }
 997
 998   return new_binfo;
 999 }
1000 \f
1001 /* Hashing of lists so that we don't make duplicates.
1002    The entry point is `list_hash_canon'.  */
1003
1004 /* Now here is the hash table.  When recording a list, it is added
1005    to the slot whose index is the hash code mod the table size.
1006    Note that the hash table is used for several kinds of lists.
1007    While all these live in the same table, they are completely independent,
1008    and the hash code is computed differently for each of these.  */
1009
1010 static GTY ((param_is (union tree_node))) htab_t list_hash_table;
1011
1012 struct list_proxy
1013 {
1014   tree purpose;
1015   tree value;
1016   tree chain;
1017 };
1018
1019 /* Compare ENTRY (an entry in the hash table) with DATA (a list_proxy
1020    for a node we are thinking about adding).  */
1021
1022 static int
1023 list_hash_eq (const void* entry, const void* data)
1024 {
1025   const_tree const t = (const_tree) entry;
1026   const struct list_proxy *const proxy = (const struct list_proxy *) data;
1027
1028   return (TREE_VALUE (t) == proxy->value
1029           && TREE_PURPOSE (t) == proxy->purpose
1030           && TREE_CHAIN (t) == proxy->chain);
1031 }
1032
1033 /* Compute a hash code for a list (chain of TREE_LIST nodes
1034    with goodies in the TREE_PURPOSE, TREE_VALUE, and bits of the
1035    TREE_COMMON slots), by adding the hash codes of the individual entries.  */
1036
1037 static hashval_t
1038 list_hash_pieces (tree purpose, tree value, tree chain)
1039 {
1040   hashval_t hashcode = 0;
1041
1042   if (chain)
1043     hashcode += TREE_HASH (chain);
1044
1045   if (value)
1046     hashcode += TREE_HASH (value);
1047   else
1048     hashcode += 1007;
1049   if (purpose)
1050     hashcode += TREE_HASH (purpose);
1051   else
1052     hashcode += 1009;
1053   return hashcode;
1054 }
1055
1056 /* Hash an already existing TREE_LIST.  */
1057
1058 static hashval_t
1059 list_hash (const void* p)
1060 {
1061   const_tree const t = (const_tree) p;
1062   return list_hash_pieces (TREE_PURPOSE (t),
1063                            TREE_VALUE (t),
1064                            TREE_CHAIN (t));
1065 }
1066
1067 /* Given list components PURPOSE, VALUE, AND CHAIN, return the canonical
1068    object for an identical list if one already exists.  Otherwise, build a
1069    new one, and record it as the canonical object.  */
1070
1071 tree
1072 hash_tree_cons (tree purpose, tree value, tree chain)
1073 {
1074   int hashcode = 0;
1075   void **slot;
1076   struct list_proxy proxy;
1077
1078   /* Hash the list node.  */
1079   hashcode = list_hash_pieces (purpose, value, chain);
1080   /* Create a proxy for the TREE_LIST we would like to create.  We
1081      don't actually create it so as to avoid creating garbage.  */
1082   proxy.purpose = purpose;
1083   proxy.value = value;
1084   proxy.chain = chain;
1085   /* See if it is already in the table.  */
1086   slot = htab_find_slot_with_hash (list_hash_table, &proxy, hashcode,
1087                                    INSERT);
1088   /* If not, create a new node.  */
1089   if (!*slot)
1090     *slot = tree_cons (purpose, value, chain);
1091   return (tree) *slot;
1092 }
1093
1094 /* Constructor for hashed lists.  */
1095
1096 tree
1097 hash_tree_chain (tree value, tree chain)
1098 {
1099   return hash_tree_cons (NULL_TREE, value, chain);
1100 }
1101 \f
1102 void
1103 debug_binfo (tree elem)
1104 {
1105   HOST_WIDE_INT n;
1106   tree virtuals;
1107
1108   fprintf (stderr, "type \"%s\", offset = " HOST_WIDE_INT_PRINT_DEC
1109            "\nvtable type:\n",
1110            TYPE_NAME_STRING (BINFO_TYPE (elem)),
1111            TREE_INT_CST_LOW (BINFO_OFFSET (elem)));
1112   debug_tree (BINFO_TYPE (elem));
1113   if (BINFO_VTABLE (elem))
1114     fprintf (stderr, "vtable decl \"%s\"\n",
1115              IDENTIFIER_POINTER (DECL_NAME (get_vtbl_decl_for_binfo (elem))));
1116   else
1117     fprintf (stderr, "no vtable decl yet\n");
1118   fprintf (stderr, "virtuals:\n");
1119   virtuals = BINFO_VIRTUALS (elem);
1120   n = 0;
1121
1122   while (virtuals)
1123     {
1124       tree fndecl = TREE_VALUE (virtuals);
1125       fprintf (stderr, "%s [%ld =? %ld]\n",
1126                IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (fndecl)),
1127                (long) n, (long) TREE_INT_CST_LOW (DECL_VINDEX (fndecl)));
1128       ++n;
1129       virtuals = TREE_CHAIN (virtuals);
1130     }
1131 }
1132
1133 /* Build a representation for the qualified name SCOPE::NAME.  TYPE is
1134    the type of the result expression, if known, or NULL_TREE if the
1135    resulting expression is type-dependent.  If TEMPLATE_P is true,
1136    NAME is known to be a template because the user explicitly used the
1137    "template" keyword after the "::".
1138
1139    All SCOPE_REFs should be built by use of this function.  */
1140
1141 tree
1142 build_qualified_name (tree type, tree scope, tree name, bool template_p)
1143 {
1144   tree t;
1145   if (type == error_mark_node
1146       || scope == error_mark_node
1147       || name == error_mark_node)
1148     return error_mark_node;
1149   t = build2 (SCOPE_REF, type, scope, name);
1150   QUALIFIED_NAME_IS_TEMPLATE (t) = template_p;
1151   return t;
1152 }
1153
1154 /* Returns nonzero if X is an expression for a (possibly overloaded)
1155    function.  If "f" is a function or function template, "f", "c->f",
1156    "c.f", "C::f", and "f<int>" will all be considered possibly
1157    overloaded functions.  Returns 2 if the function is actually
1158    overloaded, i.e., if it is impossible to know the type of the
1159    function without performing overload resolution.  */
1160
1161 int
1162 is_overloaded_fn (tree x)
1163 {
1164   /* A baselink is also considered an overloaded function.  */
1165   if (TREE_CODE (x) == OFFSET_REF
1166       || TREE_CODE (x) == COMPONENT_REF)
1167     x = TREE_OPERAND (x, 1);
1168   if (BASELINK_P (x))
1169     x = BASELINK_FUNCTIONS (x);
1170   if (TREE_CODE (x) == TEMPLATE_ID_EXPR
1171       || DECL_FUNCTION_TEMPLATE_P (OVL_CURRENT (x))
1172       || (TREE_CODE (x) == OVERLOAD && OVL_CHAIN (x)))
1173     return 2;
1174   return  (TREE_CODE (x) == FUNCTION_DECL
1175            || TREE_CODE (x) == OVERLOAD);
1176 }
1177
1178 /* Returns true iff X is an expression for an overloaded function
1179    whose type cannot be known without performing overload
1180    resolution.  */
1181
1182 bool
1183 really_overloaded_fn (tree x)
1184 {
1185   return is_overloaded_fn (x) == 2;
1186 }
1187
1188 tree
1189 get_first_fn (tree from)
1190 {
1191   gcc_assert (is_overloaded_fn (from));
1192   /* A baselink is also considered an overloaded function.  */
1193   if (TREE_CODE (from) == COMPONENT_REF)
1194     from = TREE_OPERAND (from, 1);
1195   if (BASELINK_P (from))
1196     from = BASELINK_FUNCTIONS (from);
1197   return OVL_CURRENT (from);
1198 }
1199
1200 /* Return a new OVL node, concatenating it with the old one.  */
1201
1202 tree
1203 ovl_cons (tree decl, tree chain)
1204 {
1205   tree result = make_node (OVERLOAD);
1206   TREE_TYPE (result) = unknown_type_node;
1207   OVL_FUNCTION (result) = decl;
1208   TREE_CHAIN (result) = chain;
1209
1210   return result;
1211 }
1212
1213 /* Build a new overloaded function. If this is the first one,
1214    just return it; otherwise, ovl_cons the _DECLs */
1215
1216 tree
1217 build_overload (tree decl, tree chain)
1218 {
1219   if (! chain && TREE_CODE (decl) != TEMPLATE_DECL)
1220     return decl;
1221   if (chain && TREE_CODE (chain) != OVERLOAD)
1222     chain = ovl_cons (chain, NULL_TREE);
1223   return ovl_cons (decl, chain);
1224 }
1225
1226 \f
1227 #define PRINT_RING_SIZE 4
1228
1229 const char *
1230 cxx_printable_name (tree decl, int v)
1231 {
1232   static unsigned int uid_ring[PRINT_RING_SIZE];
1233   static char *print_ring[PRINT_RING_SIZE];
1234   static int ring_counter;
1235   int i;
1236
1237   /* Only cache functions.  */
1238   if (v < 2
1239       || TREE_CODE (decl) != FUNCTION_DECL
1240       || DECL_LANG_SPECIFIC (decl) == 0)
1241     return lang_decl_name (decl, v);
1242
1243   /* See if this print name is lying around.  */
1244   for (i = 0; i < PRINT_RING_SIZE; i++)
1245     if (uid_ring[i] == DECL_UID (decl))
1246       /* yes, so return it.  */
1247       return print_ring[i];
1248
1249   if (++ring_counter == PRINT_RING_SIZE)
1250     ring_counter = 0;
1251
1252   if (current_function_decl != NULL_TREE)
1253     {
1254       if (uid_ring[ring_counter] == DECL_UID (current_function_decl))
1255         ring_counter += 1;
1256       if (ring_counter == PRINT_RING_SIZE)
1257         ring_counter = 0;
1258       gcc_assert (uid_ring[ring_counter] != DECL_UID (current_function_decl));
1259     }
1260
1261   if (print_ring[ring_counter])
1262     free (print_ring[ring_counter]);
1263
1264   print_ring[ring_counter] = xstrdup (lang_decl_name (decl, v));
1265   uid_ring[ring_counter] = DECL_UID (decl);
1266   return print_ring[ring_counter];
1267 }
1268 \f
1269 /* Build the FUNCTION_TYPE or METHOD_TYPE which may throw exceptions
1270    listed in RAISES.  */
1271
1272 tree
1273 build_exception_variant (tree type, tree raises)
1274 {
1275   tree v = TYPE_MAIN_VARIANT (type);
1276   int type_quals = TYPE_QUALS (type);
1277
1278   for (; v; v = TYPE_NEXT_VARIANT (v))
1279     if (check_qualified_type (v, type, type_quals)
1280         && comp_except_specs (raises, TYPE_RAISES_EXCEPTIONS (v), 1))
1281       return v;
1282
1283   /* Need to build a new variant.  */
1284   v = build_variant_type_copy (type);
1285   TYPE_RAISES_EXCEPTIONS (v) = raises;
1286   return v;
1287 }
1288
1289 /* Given a TEMPLATE_TEMPLATE_PARM node T, create a new
1290    BOUND_TEMPLATE_TEMPLATE_PARM bound with NEWARGS as its template
1291    arguments.  */
1292
1293 tree
1294 bind_template_template_parm (tree t, tree newargs)
1295 {
1296   tree decl = TYPE_NAME (t);
1297   tree t2;
1298
1299   t2 = cxx_make_type (BOUND_TEMPLATE_TEMPLATE_PARM);
1300   decl = build_decl (TYPE_DECL, DECL_NAME (decl), NULL_TREE);
1301
1302   /* These nodes have to be created to reflect new TYPE_DECL and template
1303      arguments.  */
1304   TEMPLATE_TYPE_PARM_INDEX (t2) = copy_node (TEMPLATE_TYPE_PARM_INDEX (t));
1305   TEMPLATE_PARM_DECL (TEMPLATE_TYPE_PARM_INDEX (t2)) = decl;
1306   TEMPLATE_TEMPLATE_PARM_TEMPLATE_INFO (t2)
1307     = tree_cons (TEMPLATE_TEMPLATE_PARM_TEMPLATE_DECL (t),
1308                  newargs, NULL_TREE);
1309
1310   TREE_TYPE (decl) = t2;
1311   TYPE_NAME (t2) = decl;
1312   TYPE_STUB_DECL (t2) = decl;
1313   TYPE_SIZE (t2) = 0;
1314   SET_TYPE_STRUCTURAL_EQUALITY (t2);
1315
1316   return t2;
1317 }
1318
1319 /* Called from count_trees via walk_tree.  */
1320
1321 static tree
1322 count_trees_r (tree *tp, int *walk_subtrees, void *data)
1323 {
1324   ++*((int *) data);
1325
1326   if (TYPE_P (*tp))
1327     *walk_subtrees = 0;
1328
1329   return NULL_TREE;
1330 }
1331
1332 /* Debugging function for measuring the rough complexity of a tree
1333    representation.  */
1334
1335 int
1336 count_trees (tree t)
1337 {
1338   int n_trees = 0;
1339   cp_walk_tree_without_duplicates (&t, count_trees_r, &n_trees);
1340   return n_trees;
1341 }
1342
1343 /* Called from verify_stmt_tree via walk_tree.  */
1344
1345 static tree
1346 verify_stmt_tree_r (tree* tp,
1347                     int* walk_subtrees ATTRIBUTE_UNUSED ,
1348                     void* data)
1349 {
1350   tree t = *tp;
1351   htab_t *statements = (htab_t *) data;
1352   void **slot;
1353
1354   if (!STATEMENT_CODE_P (TREE_CODE (t)))
1355     return NULL_TREE;
1356
1357   /* If this statement is already present in the hash table, then
1358      there is a circularity in the statement tree.  */
1359   gcc_assert (!htab_find (*statements, t));
1360
1361   slot = htab_find_slot (*statements, t, INSERT);
1362   *slot = t;
1363
1364   return NULL_TREE;
1365 }
1366
1367 /* Debugging function to check that the statement T has not been
1368    corrupted.  For now, this function simply checks that T contains no
1369    circularities.  */
1370
1371 void
1372 verify_stmt_tree (tree t)
1373 {
1374   htab_t statements;
1375   statements = htab_create (37, htab_hash_pointer, htab_eq_pointer, NULL);
1376   cp_walk_tree (&t, verify_stmt_tree_r, &statements, NULL);
1377   htab_delete (statements);
1378 }
1379
1380 /* Check if the type T depends on a type with no linkage and if so, return
1381    it.  If RELAXED_P then do not consider a class type declared within
1382    a TREE_PUBLIC function to have no linkage.  */
1383
1384 tree
1385 no_linkage_check (tree t, bool relaxed_p)
1386 {
1387   tree r;
1388
1389   /* There's no point in checking linkage on template functions; we
1390      can't know their complete types.  */
1391   if (processing_template_decl)
1392     return NULL_TREE;
1393
1394   switch (TREE_CODE (t))
1395     {
1396       tree fn;
1397
1398     case RECORD_TYPE:
1399       if (TYPE_PTRMEMFUNC_P (t))
1400         goto ptrmem;
1401       /* Fall through.  */
1402     case UNION_TYPE:
1403       if (!CLASS_TYPE_P (t))
1404         return NULL_TREE;
1405       /* Fall through.  */
1406     case ENUMERAL_TYPE:
1407       if (TYPE_ANONYMOUS_P (t))
1408         return t;
1409       fn = decl_function_context (TYPE_MAIN_DECL (t));
1410       if (fn && (!relaxed_p || !TREE_PUBLIC (fn)))
1411         return t;
1412       return NULL_TREE;
1413
1414     case ARRAY_TYPE:
1415     case POINTER_TYPE:
1416     case REFERENCE_TYPE:
1417       return no_linkage_check (TREE_TYPE (t), relaxed_p);
1418
1419     case OFFSET_TYPE:
1420     ptrmem:
1421       r = no_linkage_check (TYPE_PTRMEM_POINTED_TO_TYPE (t),
1422                             relaxed_p);
1423       if (r)
1424         return r;
1425       return no_linkage_check (TYPE_PTRMEM_CLASS_TYPE (t), relaxed_p);
1426
1427     case METHOD_TYPE:
1428       r = no_linkage_check (TYPE_METHOD_BASETYPE (t), relaxed_p);
1429       if (r)
1430         return r;
1431       /* Fall through.  */
1432     case FUNCTION_TYPE:
1433       {
1434         tree parm;
1435         for (parm = TYPE_ARG_TYPES (t);
1436              parm && parm != void_list_node;
1437              parm = TREE_CHAIN (parm))
1438           {
1439             r = no_linkage_check (TREE_VALUE (parm), relaxed_p);
1440             if (r)
1441               return r;
1442           }
1443         return no_linkage_check (TREE_TYPE (t), relaxed_p);
1444       }
1445
1446     default:
1447       return NULL_TREE;
1448     }
1449 }
1450
1451 #ifdef GATHER_STATISTICS
1452 extern int depth_reached;
1453 #endif
1454
1455 void
1456 cxx_print_statistics (void)
1457 {
1458   print_search_statistics ();
1459   print_class_statistics ();
1460 #ifdef GATHER_STATISTICS
1461   fprintf (stderr, "maximum template instantiation depth reached: %d\n",
1462            depth_reached);
1463 #endif
1464 }
1465
1466 /* Return, as an INTEGER_CST node, the number of elements for TYPE
1467    (which is an ARRAY_TYPE).  This counts only elements of the top
1468    array.  */
1469
1470 tree
1471 array_type_nelts_top (tree type)
1472 {
1473   return fold_build2 (PLUS_EXPR, sizetype,
1474                       array_type_nelts (type),
1475                       size_one_node);
1476 }
1477
1478 /* Return, as an INTEGER_CST node, the number of elements for TYPE
1479    (which is an ARRAY_TYPE).  This one is a recursive count of all
1480    ARRAY_TYPEs that are clumped together.  */
1481
1482 tree
1483 array_type_nelts_total (tree type)
1484 {
1485   tree sz = array_type_nelts_top (type);
1486   type = TREE_TYPE (type);
1487   while (TREE_CODE (type) == ARRAY_TYPE)
1488     {
1489       tree n = array_type_nelts_top (type);
1490       sz = fold_build2 (MULT_EXPR, sizetype, sz, n);
1491       type = TREE_TYPE (type);
1492     }
1493   return sz;
1494 }
1495
1496 /* Called from break_out_target_exprs via mapcar.  */
1497
1498 static tree
1499 bot_manip (tree* tp, int* walk_subtrees, void* data)
1500 {
1501   splay_tree target_remap = ((splay_tree) data);
1502   tree t = *tp;
1503
1504   if (!TYPE_P (t) && TREE_CONSTANT (t))
1505     {
1506       /* There can't be any TARGET_EXPRs or their slot variables below
1507          this point.  We used to check !TREE_SIDE_EFFECTS, but then we
1508          failed to copy an ADDR_EXPR of the slot VAR_DECL.  */
1509       *walk_subtrees = 0;
1510       return NULL_TREE;
1511     }
1512   if (TREE_CODE (t) == TARGET_EXPR)
1513     {
1514       tree u;
1515
1516       if (TREE_CODE (TREE_OPERAND (t, 1)) == AGGR_INIT_EXPR)
1517         u = build_cplus_new (TREE_TYPE (t), TREE_OPERAND (t, 1));
1518       else
1519         u = build_target_expr_with_type (TREE_OPERAND (t, 1), TREE_TYPE (t));
1520
1521       /* Map the old variable to the new one.  */
1522       splay_tree_insert (target_remap,
1523                          (splay_tree_key) TREE_OPERAND (t, 0),
1524                          (splay_tree_value) TREE_OPERAND (u, 0));
1525
1526       TREE_OPERAND (u, 1) = break_out_target_exprs (TREE_OPERAND (u, 1));
1527
1528       /* Replace the old expression with the new version.  */
1529       *tp = u;
1530       /* We don't have to go below this point; the recursive call to
1531          break_out_target_exprs will have handled anything below this
1532          point.  */
1533       *walk_subtrees = 0;
1534       return NULL_TREE;
1535     }
1536
1537   /* Make a copy of this node.  */
1538   return copy_tree_r (tp, walk_subtrees, NULL);
1539 }
1540
1541 /* Replace all remapped VAR_DECLs in T with their new equivalents.
1542    DATA is really a splay-tree mapping old variables to new
1543    variables.  */
1544
1545 static tree
1546 bot_replace (tree* t,
1547              int* walk_subtrees ATTRIBUTE_UNUSED ,
1548              void* data)
1549 {
1550   splay_tree target_remap = ((splay_tree) data);
1551
1552   if (TREE_CODE (*t) == VAR_DECL)
1553     {
1554       splay_tree_node n = splay_tree_lookup (target_remap,
1555                                              (splay_tree_key) *t);
1556       if (n)
1557         *t = (tree) n->value;
1558     }
1559
1560   return NULL_TREE;
1561 }
1562
1563 /* When we parse a default argument expression, we may create
1564    temporary variables via TARGET_EXPRs.  When we actually use the
1565    default-argument expression, we make a copy of the expression, but
1566    we must replace the temporaries with appropriate local versions.  */
1567
1568 tree
1569 break_out_target_exprs (tree t)
1570 {
1571   static int target_remap_count;
1572   static splay_tree target_remap;
1573
1574   if (!target_remap_count++)
1575     target_remap = splay_tree_new (splay_tree_compare_pointers,
1576                                    /*splay_tree_delete_key_fn=*/NULL,
1577                                    /*splay_tree_delete_value_fn=*/NULL);
1578   cp_walk_tree (&t, bot_manip, target_remap, NULL);
1579   cp_walk_tree (&t, bot_replace, target_remap, NULL);
1580
1581   if (!--target_remap_count)
1582     {
1583       splay_tree_delete (target_remap);
1584       target_remap = NULL;
1585     }
1586
1587   return t;
1588 }
1589
1590 /* Similar to `build_nt', but for template definitions of dependent
1591    expressions  */
1592
1593 tree
1594 build_min_nt (enum tree_code code, ...)
1595 {
1596   tree t;
1597   int length;
1598   int i;
1599   va_list p;
1600
1601   gcc_assert (TREE_CODE_CLASS (code) != tcc_vl_exp);
1602
1603   va_start (p, code);
1604
1605   t = make_node (code);
1606   length = TREE_CODE_LENGTH (code);
1607
1608   for (i = 0; i < length; i++)
1609     {
1610       tree x = va_arg (p, tree);
1611       TREE_OPERAND (t, i) = x;
1612     }
1613
1614   va_end (p);
1615   return t;
1616 }
1617
1618
1619 /* Similar to `build', but for template definitions.  */
1620
1621 tree
1622 build_min (enum tree_code code, tree tt, ...)
1623 {
1624   tree t;
1625   int length;
1626   int i;
1627   va_list p;
1628
1629   gcc_assert (TREE_CODE_CLASS (code) != tcc_vl_exp);
1630
1631   va_start (p, tt);
1632
1633   t = make_node (code);
1634   length = TREE_CODE_LENGTH (code);
1635   TREE_TYPE (t) = tt;
1636
1637   for (i = 0; i < length; i++)
1638     {
1639       tree x = va_arg (p, tree);
1640       TREE_OPERAND (t, i) = x;
1641       if (x && !TYPE_P (x) && TREE_SIDE_EFFECTS (x))
1642         TREE_SIDE_EFFECTS (t) = 1;
1643     }
1644
1645   va_end (p);
1646   return t;
1647 }
1648
1649 /* Similar to `build', but for template definitions of non-dependent
1650    expressions. NON_DEP is the non-dependent expression that has been
1651    built.  */
1652
1653 tree
1654 build_min_non_dep (enum tree_code code, tree non_dep, ...)
1655 {
1656   tree t;
1657   int length;
1658   int i;
1659   va_list p;
1660
1661   gcc_assert (TREE_CODE_CLASS (code) != tcc_vl_exp);
1662
1663   va_start (p, non_dep);
1664
1665   t = make_node (code);
1666   length = TREE_CODE_LENGTH (code);
1667   TREE_TYPE (t) = TREE_TYPE (non_dep);
1668   TREE_SIDE_EFFECTS (t) = TREE_SIDE_EFFECTS (non_dep);
1669
1670   for (i = 0; i < length; i++)
1671     {
1672       tree x = va_arg (p, tree);
1673       TREE_OPERAND (t, i) = x;
1674     }
1675
1676   if (code == COMPOUND_EXPR && TREE_CODE (non_dep) != COMPOUND_EXPR)
1677     /* This should not be considered a COMPOUND_EXPR, because it
1678        resolves to an overload.  */
1679     COMPOUND_EXPR_OVERLOADED (t) = 1;
1680
1681   va_end (p);
1682   return t;
1683 }
1684
1685 /* Similar to `build_call_list', but for template definitions of non-dependent
1686    expressions. NON_DEP is the non-dependent expression that has been
1687    built.  */
1688
1689 tree
1690 build_min_non_dep_call_list (tree non_dep, tree fn, tree arglist)
1691 {
1692   tree t = build_nt_call_list (fn, arglist);
1693   TREE_TYPE (t) = TREE_TYPE (non_dep);
1694   TREE_SIDE_EFFECTS (t) = TREE_SIDE_EFFECTS (non_dep);
1695   return t;
1696 }
1697
1698 tree
1699 get_type_decl (tree t)
1700 {
1701   if (TREE_CODE (t) == TYPE_DECL)
1702     return t;
1703   if (TYPE_P (t))
1704     return TYPE_STUB_DECL (t);
1705   gcc_assert (t == error_mark_node);
1706   return t;
1707 }
1708
1709 /* Returns the namespace that contains DECL, whether directly or
1710    indirectly.  */
1711
1712 tree
1713 decl_namespace_context (tree decl)
1714 {
1715   while (1)
1716     {
1717       if (TREE_CODE (decl) == NAMESPACE_DECL)
1718         return decl;
1719       else if (TYPE_P (decl))
1720         decl = CP_DECL_CONTEXT (TYPE_MAIN_DECL (decl));
1721       else
1722         decl = CP_DECL_CONTEXT (decl);
1723     }
1724 }
1725
1726 /* Returns true if decl is within an anonymous namespace, however deeply
1727    nested, or false otherwise.  */
1728
1729 bool
1730 decl_anon_ns_mem_p (const_tree decl)
1731 {
1732   while (1)
1733     {
1734       if (decl == NULL_TREE || decl == error_mark_node)
1735         return false;
1736       if (TREE_CODE (decl) == NAMESPACE_DECL
1737           && DECL_NAME (decl) == NULL_TREE)
1738         return true;
1739       /* Classes and namespaces inside anonymous namespaces have
1740          TREE_PUBLIC == 0, so we can shortcut the search.  */
1741       else if (TYPE_P (decl))
1742         return (TREE_PUBLIC (TYPE_NAME (decl)) == 0);
1743       else if (TREE_CODE (decl) == NAMESPACE_DECL)
1744         return (TREE_PUBLIC (decl) == 0);
1745       else
1746         decl = DECL_CONTEXT (decl);
1747     }
1748 }
1749
1750 /* Return truthvalue of whether T1 is the same tree structure as T2.
1751    Return 1 if they are the same. Return 0 if they are different.  */
1752
1753 bool
1754 cp_tree_equal (tree t1, tree t2)
1755 {
1756   enum tree_code code1, code2;
1757
1758   if (t1 == t2)
1759     return true;
1760   if (!t1 || !t2)
1761     return false;
1762
1763   for (code1 = TREE_CODE (t1);
1764        CONVERT_EXPR_CODE_P (code1)
1765          || code1 == NON_LVALUE_EXPR;
1766        code1 = TREE_CODE (t1))
1767     t1 = TREE_OPERAND (t1, 0);
1768   for (code2 = TREE_CODE (t2);
1769        CONVERT_EXPR_CODE_P (code2)
1770          || code1 == NON_LVALUE_EXPR;
1771        code2 = TREE_CODE (t2))
1772     t2 = TREE_OPERAND (t2, 0);
1773
1774   /* They might have become equal now.  */
1775   if (t1 == t2)
1776     return true;
1777
1778   if (code1 != code2)
1779     return false;
1780
1781   switch (code1)
1782     {
1783     case INTEGER_CST:
1784       return TREE_INT_CST_LOW (t1) == TREE_INT_CST_LOW (t2)
1785         && TREE_INT_CST_HIGH (t1) == TREE_INT_CST_HIGH (t2);
1786
1787     case REAL_CST:
1788       return REAL_VALUES_EQUAL (TREE_REAL_CST (t1), TREE_REAL_CST (t2));
1789
1790     case STRING_CST:
1791       return TREE_STRING_LENGTH (t1) == TREE_STRING_LENGTH (t2)
1792         && !memcmp (TREE_STRING_POINTER (t1), TREE_STRING_POINTER (t2),
1793                     TREE_STRING_LENGTH (t1));
1794
1795     case FIXED_CST:
1796       return FIXED_VALUES_IDENTICAL (TREE_FIXED_CST (t1),
1797                                      TREE_FIXED_CST (t2));
1798
1799     case COMPLEX_CST:
1800       return cp_tree_equal (TREE_REALPART (t1), TREE_REALPART (t2))
1801         && cp_tree_equal (TREE_IMAGPART (t1), TREE_IMAGPART (t2));
1802
1803     case CONSTRUCTOR:
1804       /* We need to do this when determining whether or not two
1805          non-type pointer to member function template arguments
1806          are the same.  */
1807       if (!(same_type_p (TREE_TYPE (t1), TREE_TYPE (t2))
1808             /* The first operand is RTL.  */
1809             && TREE_OPERAND (t1, 0) == TREE_OPERAND (t2, 0)))
1810         return false;
1811       return cp_tree_equal (TREE_OPERAND (t1, 1), TREE_OPERAND (t2, 1));
1812
1813     case TREE_LIST:
1814       if (!cp_tree_equal (TREE_PURPOSE (t1), TREE_PURPOSE (t2)))
1815         return false;
1816       if (!cp_tree_equal (TREE_VALUE (t1), TREE_VALUE (t2)))
1817         return false;
1818       return cp_tree_equal (TREE_CHAIN (t1), TREE_CHAIN (t2));
1819
1820     case SAVE_EXPR:
1821       return cp_tree_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
1822
1823     case CALL_EXPR:
1824       {
1825         tree arg1, arg2;
1826         call_expr_arg_iterator iter1, iter2;
1827         if (!cp_tree_equal (CALL_EXPR_FN (t1), CALL_EXPR_FN (t2)))
1828           return false;
1829         for (arg1 = first_call_expr_arg (t1, &iter1),
1830                arg2 = first_call_expr_arg (t2, &iter2);
1831              arg1 && arg2;
1832              arg1 = next_call_expr_arg (&iter1),
1833                arg2 = next_call_expr_arg (&iter2))
1834           if (!cp_tree_equal (arg1, arg2))
1835             return false;
1836         return (arg1 || arg2);
1837       }
1838
1839     case TARGET_EXPR:
1840       {
1841         tree o1 = TREE_OPERAND (t1, 0);
1842         tree o2 = TREE_OPERAND (t2, 0);
1843
1844         /* Special case: if either target is an unallocated VAR_DECL,
1845            it means that it's going to be unified with whatever the
1846            TARGET_EXPR is really supposed to initialize, so treat it
1847            as being equivalent to anything.  */
1848         if (TREE_CODE (o1) == VAR_DECL && DECL_NAME (o1) == NULL_TREE
1849             && !DECL_RTL_SET_P (o1))
1850           /*Nop*/;
1851         else if (TREE_CODE (o2) == VAR_DECL && DECL_NAME (o2) == NULL_TREE
1852                  && !DECL_RTL_SET_P (o2))
1853           /*Nop*/;
1854         else if (!cp_tree_equal (o1, o2))
1855           return false;
1856
1857         return cp_tree_equal (TREE_OPERAND (t1, 1), TREE_OPERAND (t2, 1));
1858       }
1859
1860     case WITH_CLEANUP_EXPR:
1861       if (!cp_tree_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0)))
1862         return false;
1863       return cp_tree_equal (TREE_OPERAND (t1, 1), TREE_OPERAND (t1, 1));
1864
1865     case COMPONENT_REF:
1866       if (TREE_OPERAND (t1, 1) != TREE_OPERAND (t2, 1))
1867         return false;
1868       return cp_tree_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
1869
1870     case PARM_DECL:
1871       /* For comparing uses of parameters in late-specified return types
1872          with an out-of-class definition of the function.  */
1873       if ((!DECL_CONTEXT (t1) || !DECL_CONTEXT (t2))
1874           && same_type_p (TREE_TYPE (t1), TREE_TYPE (t2))
1875           && DECL_NAME (t1) == DECL_NAME (t2))
1876         return true;
1877       else
1878         return false;
1879
1880     case VAR_DECL:
1881     case CONST_DECL:
1882     case FUNCTION_DECL:
1883     case TEMPLATE_DECL:
1884     case IDENTIFIER_NODE:
1885     case SSA_NAME:
1886       return false;
1887
1888     case BASELINK:
1889       return (BASELINK_BINFO (t1) == BASELINK_BINFO (t2)
1890               && BASELINK_ACCESS_BINFO (t1) == BASELINK_ACCESS_BINFO (t2)
1891               && cp_tree_equal (BASELINK_FUNCTIONS (t1),
1892                                 BASELINK_FUNCTIONS (t2)));
1893
1894     case TEMPLATE_PARM_INDEX:
1895       return (TEMPLATE_PARM_IDX (t1) == TEMPLATE_PARM_IDX (t2)
1896               && TEMPLATE_PARM_LEVEL (t1) == TEMPLATE_PARM_LEVEL (t2)
1897               && same_type_p (TREE_TYPE (TEMPLATE_PARM_DECL (t1)),
1898                               TREE_TYPE (TEMPLATE_PARM_DECL (t2))));
1899
1900     case TEMPLATE_ID_EXPR:
1901       {
1902         unsigned ix;
1903         tree vec1, vec2;
1904
1905         if (!cp_tree_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0)))
1906           return false;
1907         vec1 = TREE_OPERAND (t1, 1);
1908         vec2 = TREE_OPERAND (t2, 1);
1909
1910         if (!vec1 || !vec2)
1911           return !vec1 && !vec2;
1912
1913         if (TREE_VEC_LENGTH (vec1) != TREE_VEC_LENGTH (vec2))
1914           return false;
1915
1916         for (ix = TREE_VEC_LENGTH (vec1); ix--;)
1917           if (!cp_tree_equal (TREE_VEC_ELT (vec1, ix),
1918                               TREE_VEC_ELT (vec2, ix)))
1919             return false;
1920
1921         return true;
1922       }
1923
1924     case SIZEOF_EXPR:
1925     case ALIGNOF_EXPR:
1926       {
1927         tree o1 = TREE_OPERAND (t1, 0);
1928         tree o2 = TREE_OPERAND (t2, 0);
1929
1930         if (TREE_CODE (o1) != TREE_CODE (o2))
1931           return false;
1932         if (TYPE_P (o1))
1933           return same_type_p (o1, o2);
1934         else
1935           return cp_tree_equal (o1, o2);
1936       }
1937
1938     case MODOP_EXPR:
1939       {
1940         tree t1_op1, t2_op1;
1941
1942         if (!cp_tree_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0)))
1943           return false;
1944
1945         t1_op1 = TREE_OPERAND (t1, 1);
1946         t2_op1 = TREE_OPERAND (t2, 1);
1947         if (TREE_CODE (t1_op1) != TREE_CODE (t2_op1))
1948           return false;
1949
1950         return cp_tree_equal (TREE_OPERAND (t1, 2), TREE_OPERAND (t2, 2));
1951       }
1952
1953     case PTRMEM_CST:
1954       /* Two pointer-to-members are the same if they point to the same
1955          field or function in the same class.  */
1956       if (PTRMEM_CST_MEMBER (t1) != PTRMEM_CST_MEMBER (t2))
1957         return false;
1958
1959       return same_type_p (PTRMEM_CST_CLASS (t1), PTRMEM_CST_CLASS (t2));
1960
1961     case OVERLOAD:
1962       if (OVL_FUNCTION (t1) != OVL_FUNCTION (t2))
1963         return false;
1964       return cp_tree_equal (OVL_CHAIN (t1), OVL_CHAIN (t2));
1965
1966     case TRAIT_EXPR:
1967       if (TRAIT_EXPR_KIND (t1) != TRAIT_EXPR_KIND (t2))
1968         return false;
1969       return same_type_p (TRAIT_EXPR_TYPE1 (t1), TRAIT_EXPR_TYPE1 (t2))
1970         && same_type_p (TRAIT_EXPR_TYPE2 (t1), TRAIT_EXPR_TYPE2 (t2));
1971
1972     default:
1973       break;
1974     }
1975
1976   switch (TREE_CODE_CLASS (code1))
1977     {
1978     case tcc_unary:
1979     case tcc_binary:
1980     case tcc_comparison:
1981     case tcc_expression:
1982     case tcc_vl_exp:
1983     case tcc_reference:
1984     case tcc_statement:
1985       {
1986         int i, n;
1987
1988         n = TREE_OPERAND_LENGTH (t1);
1989         if (TREE_CODE_CLASS (code1) == tcc_vl_exp
1990             && n != TREE_OPERAND_LENGTH (t2))
1991           return false;
1992
1993         for (i = 0; i < n; ++i)
1994           if (!cp_tree_equal (TREE_OPERAND (t1, i), TREE_OPERAND (t2, i)))
1995             return false;
1996
1997         return true;
1998       }
1999
2000     case tcc_type:
2001       return same_type_p (t1, t2);
2002     default:
2003       gcc_unreachable ();
2004     }
2005   /* We can get here with --disable-checking.  */
2006   return false;
2007 }
2008
2009 /* The type of ARG when used as an lvalue.  */
2010
2011 tree
2012 lvalue_type (tree arg)
2013 {
2014   tree type = TREE_TYPE (arg);
2015   return type;
2016 }
2017
2018 /* The type of ARG for printing error messages; denote lvalues with
2019    reference types.  */
2020
2021 tree
2022 error_type (tree arg)
2023 {
2024   tree type = TREE_TYPE (arg);
2025
2026   if (TREE_CODE (type) == ARRAY_TYPE)
2027     ;
2028   else if (TREE_CODE (type) == ERROR_MARK)
2029     ;
2030   else if (real_lvalue_p (arg))
2031     type = build_reference_type (lvalue_type (arg));
2032   else if (MAYBE_CLASS_TYPE_P (type))
2033     type = lvalue_type (arg);
2034
2035   return type;
2036 }
2037
2038 /* Does FUNCTION use a variable-length argument list?  */
2039
2040 int
2041 varargs_function_p (const_tree function)
2042 {
2043   const_tree parm = TYPE_ARG_TYPES (TREE_TYPE (function));
2044   for (; parm; parm = TREE_CHAIN (parm))
2045     if (TREE_VALUE (parm) == void_type_node)
2046       return 0;
2047   return 1;
2048 }
2049
2050 /* Returns 1 if decl is a member of a class.  */
2051
2052 int
2053 member_p (const_tree decl)
2054 {
2055   const_tree const ctx = DECL_CONTEXT (decl);
2056   return (ctx && TYPE_P (ctx));
2057 }
2058
2059 /* Create a placeholder for member access where we don't actually have an
2060    object that the access is against.  */
2061
2062 tree
2063 build_dummy_object (tree type)
2064 {
2065   tree decl = build1 (NOP_EXPR, build_pointer_type (type), void_zero_node);
2066   return cp_build_indirect_ref (decl, NULL, tf_warning_or_error);
2067 }
2068
2069 /* We've gotten a reference to a member of TYPE.  Return *this if appropriate,
2070    or a dummy object otherwise.  If BINFOP is non-0, it is filled with the
2071    binfo path from current_class_type to TYPE, or 0.  */
2072
2073 tree
2074 maybe_dummy_object (tree type, tree* binfop)
2075 {
2076   tree decl, context;
2077   tree binfo;
2078
2079   if (current_class_type
2080       && (binfo = lookup_base (current_class_type, type,
2081                                ba_unique | ba_quiet, NULL)))
2082     context = current_class_type;
2083   else
2084     {
2085       /* Reference from a nested class member function.  */
2086       context = type;
2087       binfo = TYPE_BINFO (type);
2088     }
2089
2090   if (binfop)
2091     *binfop = binfo;
2092
2093   if (current_class_ref && context == current_class_type
2094       /* Kludge: Make sure that current_class_type is actually
2095          correct.  It might not be if we're in the middle of
2096          tsubst_default_argument.  */
2097       && same_type_p (TYPE_MAIN_VARIANT (TREE_TYPE (current_class_ref)),
2098                       current_class_type))
2099     decl = current_class_ref;
2100   else
2101     decl = build_dummy_object (context);
2102
2103   return decl;
2104 }
2105
2106 /* Returns 1 if OB is a placeholder object, or a pointer to one.  */
2107
2108 int
2109 is_dummy_object (const_tree ob)
2110 {
2111   if (TREE_CODE (ob) == INDIRECT_REF)
2112     ob = TREE_OPERAND (ob, 0);
2113   return (TREE_CODE (ob) == NOP_EXPR
2114           && TREE_OPERAND (ob, 0) == void_zero_node);
2115 }
2116
2117 /* Returns 1 iff type T is a POD type, as defined in [basic.types].  */
2118
2119 int
2120 pod_type_p (const_tree t)
2121 {
2122   /* This CONST_CAST is okay because strip_array_types returns its
2123      argument unmodified and we assign it to a const_tree.  */
2124   t = strip_array_types (CONST_CAST_TREE(t));
2125
2126   if (t == error_mark_node)
2127     return 1;
2128   if (INTEGRAL_TYPE_P (t))
2129     return 1;  /* integral, character or enumeral type */
2130   if (FLOAT_TYPE_P (t))
2131     return 1;
2132   if (TYPE_PTR_P (t))
2133     return 1; /* pointer to non-member */
2134   if (TYPE_PTR_TO_MEMBER_P (t))
2135     return 1; /* pointer to member */
2136
2137   if (TREE_CODE (t) == VECTOR_TYPE)
2138     return 1; /* vectors are (small) arrays of scalars */
2139
2140   if (! RECORD_OR_UNION_CODE_P (TREE_CODE (t)))
2141     return 0; /* other non-class type (reference or function) */
2142   if (! CLASS_TYPE_P (t))
2143     return 1; /* struct created by the back end */
2144   if (CLASSTYPE_NON_POD_P (t))
2145     return 0;
2146   return 1;
2147 }
2148
2149 /* Nonzero iff type T is a class template implicit specialization.  */
2150
2151 bool
2152 class_tmpl_impl_spec_p (const_tree t)
2153 {
2154   return CLASS_TYPE_P (t) && CLASSTYPE_TEMPLATE_INSTANTIATION (t);
2155 }
2156
2157 /* Returns 1 iff zero initialization of type T means actually storing
2158    zeros in it.  */
2159
2160 int
2161 zero_init_p (const_tree t)
2162 {
2163   /* This CONST_CAST is okay because strip_array_types returns its
2164      argument unmodified and we assign it to a const_tree.  */
2165   t = strip_array_types (CONST_CAST_TREE(t));
2166
2167   if (t == error_mark_node)
2168     return 1;
2169
2170   /* NULL pointers to data members are initialized with -1.  */
2171   if (TYPE_PTRMEM_P (t))
2172     return 0;
2173
2174   /* Classes that contain types that can't be zero-initialized, cannot
2175      be zero-initialized themselves.  */
2176   if (CLASS_TYPE_P (t) && CLASSTYPE_NON_ZERO_INIT_P (t))
2177     return 0;
2178
2179   return 1;
2180 }
2181
2182 /* Table of valid C++ attributes.  */
2183 const struct attribute_spec cxx_attribute_table[] =
2184 {
2185   /* { name, min_len, max_len, decl_req, type_req, fn_type_req, handler } */
2186   { "java_interface", 0, 0, false, false, false, handle_java_interface_attribute },
2187   { "com_interface",  0, 0, false, false, false, handle_com_interface_attribute },
2188   { "init_priority",  1, 1, true,  false, false, handle_init_priority_attribute },
2189   { NULL,             0, 0, false, false, false, NULL }
2190 };
2191
2192 /* Handle a "java_interface" attribute; arguments as in
2193    struct attribute_spec.handler.  */
2194 static tree
2195 handle_java_interface_attribute (tree* node,
2196                                  tree name,
2197                                  tree args ATTRIBUTE_UNUSED ,
2198                                  int flags,
2199                                  bool* no_add_attrs)
2200 {
2201   if (DECL_P (*node)
2202       || !CLASS_TYPE_P (*node)
2203       || !TYPE_FOR_JAVA (*node))
2204     {
2205       error ("%qE attribute can only be applied to Java class definitions",
2206              name);
2207       *no_add_attrs = true;
2208       return NULL_TREE;
2209     }
2210   if (!(flags & (int) ATTR_FLAG_TYPE_IN_PLACE))
2211     *node = build_variant_type_copy (*node);
2212   TYPE_JAVA_INTERFACE (*node) = 1;
2213
2214   return NULL_TREE;
2215 }
2216
2217 /* Handle a "com_interface" attribute; arguments as in
2218    struct attribute_spec.handler.  */
2219 static tree
2220 handle_com_interface_attribute (tree* node,
2221                                 tree name,
2222                                 tree args ATTRIBUTE_UNUSED ,
2223                                 int flags ATTRIBUTE_UNUSED ,
2224                                 bool* no_add_attrs)
2225 {
2226   static int warned;
2227
2228   *no_add_attrs = true;
2229
2230   if (DECL_P (*node)
2231       || !CLASS_TYPE_P (*node)
2232       || *node != TYPE_MAIN_VARIANT (*node))
2233     {
2234       warning (OPT_Wattributes, "%qE attribute can only be applied "
2235                "to class definitions", name);
2236       return NULL_TREE;
2237     }
2238
2239   if (!warned++)
2240     warning (0, "%qE is obsolete; g++ vtables are now COM-compatible by default",
2241              name);
2242
2243   return NULL_TREE;
2244 }
2245
2246 /* Handle an "init_priority" attribute; arguments as in
2247    struct attribute_spec.handler.  */
2248 static tree
2249 handle_init_priority_attribute (tree* node,
2250                                 tree name,
2251                                 tree args,
2252                                 int flags ATTRIBUTE_UNUSED ,
2253                                 bool* no_add_attrs)
2254 {
2255   tree initp_expr = TREE_VALUE (args);
2256   tree decl = *node;
2257   tree type = TREE_TYPE (decl);
2258   int pri;
2259
2260   STRIP_NOPS (initp_expr);
2261
2262   if (!initp_expr || TREE_CODE (initp_expr) != INTEGER_CST)
2263     {
2264       error ("requested init_priority is not an integer constant");
2265       *no_add_attrs = true;
2266       return NULL_TREE;
2267     }
2268
2269   pri = TREE_INT_CST_LOW (initp_expr);
2270
2271   type = strip_array_types (type);
2272
2273   if (decl == NULL_TREE
2274       || TREE_CODE (decl) != VAR_DECL
2275       || !TREE_STATIC (decl)
2276       || DECL_EXTERNAL (decl)
2277       || (TREE_CODE (type) != RECORD_TYPE
2278           && TREE_CODE (type) != UNION_TYPE)
2279       /* Static objects in functions are initialized the
2280          first time control passes through that
2281          function. This is not precise enough to pin down an
2282          init_priority value, so don't allow it.  */
2283       || current_function_decl)
2284     {
2285       error ("can only use %qE attribute on file-scope definitions "
2286              "of objects of class type", name);
2287       *no_add_attrs = true;
2288       return NULL_TREE;
2289     }
2290
2291   if (pri > MAX_INIT_PRIORITY || pri <= 0)
2292     {
2293       error ("requested init_priority is out of range");
2294       *no_add_attrs = true;
2295       return NULL_TREE;
2296     }
2297
2298   /* Check for init_priorities that are reserved for
2299      language and runtime support implementations.*/
2300   if (pri <= MAX_RESERVED_INIT_PRIORITY)
2301     {
2302       warning
2303         (0, "requested init_priority is reserved for internal use");
2304     }
2305
2306   if (SUPPORTS_INIT_PRIORITY)
2307     {
2308       SET_DECL_INIT_PRIORITY (decl, pri);
2309       DECL_HAS_INIT_PRIORITY_P (decl) = 1;
2310       return NULL_TREE;
2311     }
2312   else
2313     {
2314       error ("%qE attribute is not supported on this platform", name);
2315       *no_add_attrs = true;
2316       return NULL_TREE;
2317     }
2318 }
2319
2320 /* Return a new PTRMEM_CST of the indicated TYPE.  The MEMBER is the
2321    thing pointed to by the constant.  */
2322
2323 tree
2324 make_ptrmem_cst (tree type, tree member)
2325 {
2326   tree ptrmem_cst = make_node (PTRMEM_CST);
2327   TREE_TYPE (ptrmem_cst) = type;
2328   PTRMEM_CST_MEMBER (ptrmem_cst) = member;
2329   return ptrmem_cst;
2330 }
2331
2332 /* Build a variant of TYPE that has the indicated ATTRIBUTES.  May
2333    return an existing type if an appropriate type already exists.  */
2334
2335 tree
2336 cp_build_type_attribute_variant (tree type, tree attributes)
2337 {
2338   tree new_type;
2339
2340   new_type = build_type_attribute_variant (type, attributes);
2341   if (TREE_CODE (new_type) == FUNCTION_TYPE
2342       && (TYPE_RAISES_EXCEPTIONS (new_type)
2343           != TYPE_RAISES_EXCEPTIONS (type)))
2344     new_type = build_exception_variant (new_type,
2345                                         TYPE_RAISES_EXCEPTIONS (type));
2346
2347   /* Making a new main variant of a class type is broken.  */
2348   gcc_assert (!CLASS_TYPE_P (type) || new_type == type);
2349
2350   return new_type;
2351 }
2352
2353 /* Return TRUE if TYPE1 and TYPE2 are identical for type hashing purposes.
2354    Called only after doing all language independent checks.  Only
2355    to check TYPE_RAISES_EXCEPTIONS for FUNCTION_TYPE, the rest is already
2356    compared in type_hash_eq.  */
2357
2358 bool
2359 cxx_type_hash_eq (const_tree typea, const_tree typeb)
2360 {
2361   gcc_assert (TREE_CODE (typea) == FUNCTION_TYPE);
2362
2363   return comp_except_specs (TYPE_RAISES_EXCEPTIONS (typea),
2364                             TYPE_RAISES_EXCEPTIONS (typeb), 1);
2365 }
2366
2367 /* Apply FUNC to all language-specific sub-trees of TP in a pre-order
2368    traversal.  Called from walk_tree.  */
2369
2370 tree
2371 cp_walk_subtrees (tree *tp, int *walk_subtrees_p, walk_tree_fn func,
2372                   void *data, struct pointer_set_t *pset)
2373 {
2374   enum tree_code code = TREE_CODE (*tp);
2375   tree result;
2376
2377 #define WALK_SUBTREE(NODE)                              \
2378   do                                                    \
2379     {                                                   \
2380       result = cp_walk_tree (&(NODE), func, data, pset);        \
2381       if (result) goto out;                             \
2382     }                                                   \
2383   while (0)
2384
2385   /* Not one of the easy cases.  We must explicitly go through the
2386      children.  */
2387   result = NULL_TREE;
2388   switch (code)
2389     {
2390     case DEFAULT_ARG:
2391     case TEMPLATE_TEMPLATE_PARM:
2392     case BOUND_TEMPLATE_TEMPLATE_PARM:
2393     case UNBOUND_CLASS_TEMPLATE:
2394     case TEMPLATE_PARM_INDEX:
2395     case TEMPLATE_TYPE_PARM:
2396     case TYPENAME_TYPE:
2397     case TYPEOF_TYPE:
2398       /* None of these have subtrees other than those already walked
2399          above.  */
2400       *walk_subtrees_p = 0;
2401       break;
2402
2403     case BASELINK:
2404       WALK_SUBTREE (BASELINK_FUNCTIONS (*tp));
2405       *walk_subtrees_p = 0;
2406       break;
2407
2408     case PTRMEM_CST:
2409       WALK_SUBTREE (TREE_TYPE (*tp));
2410       *walk_subtrees_p = 0;
2411       break;
2412
2413     case TREE_LIST:
2414       WALK_SUBTREE (TREE_PURPOSE (*tp));
2415       break;
2416
2417     case OVERLOAD:
2418       WALK_SUBTREE (OVL_FUNCTION (*tp));
2419       WALK_SUBTREE (OVL_CHAIN (*tp));
2420       *walk_subtrees_p = 0;
2421       break;
2422
2423     case USING_DECL:
2424       WALK_SUBTREE (DECL_NAME (*tp));
2425       WALK_SUBTREE (USING_DECL_SCOPE (*tp));
2426       WALK_SUBTREE (USING_DECL_DECLS (*tp));
2427       *walk_subtrees_p = 0;
2428       break;
2429
2430     case RECORD_TYPE:
2431       if (TYPE_PTRMEMFUNC_P (*tp))
2432         WALK_SUBTREE (TYPE_PTRMEMFUNC_FN_TYPE (*tp));
2433       break;
2434
2435     case TYPE_ARGUMENT_PACK:
2436     case NONTYPE_ARGUMENT_PACK:
2437       {
2438         tree args = ARGUMENT_PACK_ARGS (*tp);
2439         int i, len = TREE_VEC_LENGTH (args);
2440         for (i = 0; i < len; i++)
2441           WALK_SUBTREE (TREE_VEC_ELT (args, i));
2442       }
2443       break;
2444
2445     case TYPE_PACK_EXPANSION:
2446       WALK_SUBTREE (TREE_TYPE (*tp));
2447       *walk_subtrees_p = 0;
2448       break;
2449
2450     case EXPR_PACK_EXPANSION:
2451       WALK_SUBTREE (TREE_OPERAND (*tp, 0));
2452       *walk_subtrees_p = 0;
2453       break;
2454
2455     case CAST_EXPR:
2456     case REINTERPRET_CAST_EXPR:
2457     case STATIC_CAST_EXPR:
2458     case CONST_CAST_EXPR:
2459     case DYNAMIC_CAST_EXPR:
2460       if (TREE_TYPE (*tp))
2461         WALK_SUBTREE (TREE_TYPE (*tp));
2462
2463       {
2464         int i;
2465         for (i = 0; i < TREE_CODE_LENGTH (TREE_CODE (*tp)); ++i)
2466           WALK_SUBTREE (TREE_OPERAND (*tp, i));
2467       }
2468       *walk_subtrees_p = 0;
2469       break;
2470
2471     case TRAIT_EXPR:
2472       WALK_SUBTREE (TRAIT_EXPR_TYPE1 (*tp));
2473       WALK_SUBTREE (TRAIT_EXPR_TYPE2 (*tp));
2474       *walk_subtrees_p = 0;
2475       break;
2476
2477     case DECLTYPE_TYPE:
2478       WALK_SUBTREE (DECLTYPE_TYPE_EXPR (*tp));
2479       *walk_subtrees_p = 0;
2480       break;
2481
2482
2483     default:
2484       return NULL_TREE;
2485     }
2486
2487   /* We didn't find what we were looking for.  */
2488  out:
2489   return result;
2490
2491 #undef WALK_SUBTREE
2492 }
2493
2494 /* Like save_expr, but for C++.  */
2495
2496 tree
2497 cp_save_expr (tree expr)
2498 {
2499   /* There is no reason to create a SAVE_EXPR within a template; if
2500      needed, we can create the SAVE_EXPR when instantiating the
2501      template.  Furthermore, the middle-end cannot handle C++-specific
2502      tree codes.  */
2503   if (processing_template_decl)
2504     return expr;
2505   return save_expr (expr);
2506 }
2507
2508 /* Initialize tree.c.  */
2509
2510 void
2511 init_tree (void)
2512 {
2513   list_hash_table = htab_create_ggc (31, list_hash, list_hash_eq, NULL);
2514 }
2515
2516 /* Returns the kind of special function that DECL (a FUNCTION_DECL)
2517    is.  Note that sfk_none is zero, so this function can be used as a
2518    predicate to test whether or not DECL is a special function.  */
2519
2520 special_function_kind
2521 special_function_p (const_tree decl)
2522 {
2523   /* Rather than doing all this stuff with magic names, we should
2524      probably have a field of type `special_function_kind' in
2525      DECL_LANG_SPECIFIC.  */
2526   if (DECL_COPY_CONSTRUCTOR_P (decl))
2527     return sfk_copy_constructor;
2528   if (DECL_CONSTRUCTOR_P (decl))
2529     return sfk_constructor;
2530   if (DECL_OVERLOADED_OPERATOR_P (decl) == NOP_EXPR)
2531     return sfk_assignment_operator;
2532   if (DECL_MAYBE_IN_CHARGE_DESTRUCTOR_P (decl))
2533     return sfk_destructor;
2534   if (DECL_COMPLETE_DESTRUCTOR_P (decl))
2535     return sfk_complete_destructor;
2536   if (DECL_BASE_DESTRUCTOR_P (decl))
2537     return sfk_base_destructor;
2538   if (DECL_DELETING_DESTRUCTOR_P (decl))
2539     return sfk_deleting_destructor;
2540   if (DECL_CONV_FN_P (decl))
2541     return sfk_conversion;
2542
2543   return sfk_none;
2544 }
2545
2546 /* Returns nonzero if TYPE is a character type, including wchar_t.  */
2547
2548 int
2549 char_type_p (tree type)
2550 {
2551   return (same_type_p (type, char_type_node)
2552           || same_type_p (type, unsigned_char_type_node)
2553           || same_type_p (type, signed_char_type_node)
2554           || same_type_p (type, char16_type_node)
2555           || same_type_p (type, char32_type_node)
2556           || same_type_p (type, wchar_type_node));
2557 }
2558
2559 /* Returns the kind of linkage associated with the indicated DECL.  Th
2560    value returned is as specified by the language standard; it is
2561    independent of implementation details regarding template
2562    instantiation, etc.  For example, it is possible that a declaration
2563    to which this function assigns external linkage would not show up
2564    as a global symbol when you run `nm' on the resulting object file.  */
2565
2566 linkage_kind
2567 decl_linkage (tree decl)
2568 {
2569   /* This function doesn't attempt to calculate the linkage from first
2570      principles as given in [basic.link].  Instead, it makes use of
2571      the fact that we have already set TREE_PUBLIC appropriately, and
2572      then handles a few special cases.  Ideally, we would calculate
2573      linkage first, and then transform that into a concrete
2574      implementation.  */
2575
2576   /* Things that don't have names have no linkage.  */
2577   if (!DECL_NAME (decl))
2578     return lk_none;
2579
2580   /* Fields have no linkage.  */
2581   if (TREE_CODE (decl) == FIELD_DECL)
2582     return lk_none;
2583
2584   /* Things that are TREE_PUBLIC have external linkage.  */
2585   if (TREE_PUBLIC (decl))
2586     return lk_external;
2587
2588   if (TREE_CODE (decl) == NAMESPACE_DECL)
2589     return lk_external;
2590
2591   /* Linkage of a CONST_DECL depends on the linkage of the enumeration
2592      type.  */
2593   if (TREE_CODE (decl) == CONST_DECL)
2594     return decl_linkage (TYPE_NAME (TREE_TYPE (decl)));
2595
2596   /* Some things that are not TREE_PUBLIC have external linkage, too.
2597      For example, on targets that don't have weak symbols, we make all
2598      template instantiations have internal linkage (in the object
2599      file), but the symbols should still be treated as having external
2600      linkage from the point of view of the language.  */
2601   if (TREE_CODE (decl) != TYPE_DECL && DECL_LANG_SPECIFIC (decl)
2602       && DECL_COMDAT (decl))
2603     return lk_external;
2604
2605   /* Things in local scope do not have linkage, if they don't have
2606      TREE_PUBLIC set.  */
2607   if (decl_function_context (decl))
2608     return lk_none;
2609
2610   /* Members of the anonymous namespace also have TREE_PUBLIC unset, but
2611      are considered to have external linkage for language purposes.  DECLs
2612      really meant to have internal linkage have DECL_THIS_STATIC set.  */
2613   if (TREE_CODE (decl) == TYPE_DECL)
2614     return lk_external;
2615   if (TREE_CODE (decl) == VAR_DECL || TREE_CODE (decl) == FUNCTION_DECL)
2616     {
2617       if (!DECL_THIS_STATIC (decl))
2618         return lk_external;
2619
2620       /* Static data members and static member functions from classes
2621          in anonymous namespace also don't have TREE_PUBLIC set.  */
2622       if (DECL_CLASS_CONTEXT (decl))
2623         return lk_external;
2624     }
2625
2626   /* Everything else has internal linkage.  */
2627   return lk_internal;
2628 }
2629 \f
2630 /* EXP is an expression that we want to pre-evaluate.  Returns (in
2631    *INITP) an expression that will perform the pre-evaluation.  The
2632    value returned by this function is a side-effect free expression
2633    equivalent to the pre-evaluated expression.  Callers must ensure
2634    that *INITP is evaluated before EXP.  */
2635
2636 tree
2637 stabilize_expr (tree exp, tree* initp)
2638 {
2639   tree init_expr;
2640
2641   if (!TREE_SIDE_EFFECTS (exp))
2642     init_expr = NULL_TREE;
2643   else if (!real_lvalue_p (exp)
2644            || !TYPE_NEEDS_CONSTRUCTING (TREE_TYPE (exp)))
2645     {
2646       init_expr = get_target_expr (exp);
2647       exp = TARGET_EXPR_SLOT (init_expr);
2648     }
2649   else
2650     {
2651       exp = cp_build_unary_op (ADDR_EXPR, exp, 1, tf_warning_or_error);
2652       init_expr = get_target_expr (exp);
2653       exp = TARGET_EXPR_SLOT (init_expr);
2654       exp = cp_build_indirect_ref (exp, 0, tf_warning_or_error);
2655     }
2656   *initp = init_expr;
2657
2658   gcc_assert (!TREE_SIDE_EFFECTS (exp));
2659   return exp;
2660 }
2661
2662 /* Add NEW_EXPR, an expression whose value we don't care about, after the
2663    similar expression ORIG.  */
2664
2665 tree
2666 add_stmt_to_compound (tree orig, tree new_expr)
2667 {
2668   if (!new_expr || !TREE_SIDE_EFFECTS (new_expr))
2669     return orig;
2670   if (!orig || !TREE_SIDE_EFFECTS (orig))
2671     return new_expr;
2672   return build2 (COMPOUND_EXPR, void_type_node, orig, new_expr);
2673 }
2674
2675 /* Like stabilize_expr, but for a call whose arguments we want to
2676    pre-evaluate.  CALL is modified in place to use the pre-evaluated
2677    arguments, while, upon return, *INITP contains an expression to
2678    compute the arguments.  */
2679
2680 void
2681 stabilize_call (tree call, tree *initp)
2682 {
2683   tree inits = NULL_TREE;
2684   int i;
2685   int nargs = call_expr_nargs (call);
2686
2687   if (call == error_mark_node || processing_template_decl)
2688     {
2689       *initp = NULL_TREE;
2690       return;
2691     }
2692
2693   gcc_assert (TREE_CODE (call) == CALL_EXPR);
2694
2695   for (i = 0; i < nargs; i++)
2696     {
2697       tree init;
2698       CALL_EXPR_ARG (call, i) =
2699         stabilize_expr (CALL_EXPR_ARG (call, i), &init);
2700       inits = add_stmt_to_compound (inits, init);
2701     }
2702
2703   *initp = inits;
2704 }
2705
2706 /* Like stabilize_expr, but for an AGGR_INIT_EXPR whose arguments we want
2707    to pre-evaluate.  CALL is modified in place to use the pre-evaluated
2708    arguments, while, upon return, *INITP contains an expression to
2709    compute the arguments.  */
2710
2711 void
2712 stabilize_aggr_init (tree call, tree *initp)
2713 {
2714   tree inits = NULL_TREE;
2715   int i;
2716   int nargs = aggr_init_expr_nargs (call);
2717
2718   if (call == error_mark_node)
2719     return;
2720
2721   gcc_assert (TREE_CODE (call) == AGGR_INIT_EXPR);
2722
2723   for (i = 0; i < nargs; i++)
2724     {
2725       tree init;
2726       AGGR_INIT_EXPR_ARG (call, i) =
2727         stabilize_expr (AGGR_INIT_EXPR_ARG (call, i), &init);
2728       inits = add_stmt_to_compound (inits, init);
2729     }
2730
2731   *initp = inits;
2732 }
2733
2734 /* Like stabilize_expr, but for an initialization.
2735
2736    If the initialization is for an object of class type, this function
2737    takes care not to introduce additional temporaries.
2738
2739    Returns TRUE iff the expression was successfully pre-evaluated,
2740    i.e., if INIT is now side-effect free, except for, possible, a
2741    single call to a constructor.  */
2742
2743 bool
2744 stabilize_init (tree init, tree *initp)
2745 {
2746   tree t = init;
2747
2748   *initp = NULL_TREE;
2749
2750   if (t == error_mark_node || processing_template_decl)
2751     return true;
2752
2753   if (TREE_CODE (t) == INIT_EXPR
2754       && TREE_CODE (TREE_OPERAND (t, 1)) != TARGET_EXPR
2755       && TREE_CODE (TREE_OPERAND (t, 1)) != AGGR_INIT_EXPR)
2756     {
2757       TREE_OPERAND (t, 1) = stabilize_expr (TREE_OPERAND (t, 1), initp);
2758       return true;
2759     }
2760
2761   if (TREE_CODE (t) == INIT_EXPR)
2762     t = TREE_OPERAND (t, 1);
2763   if (TREE_CODE (t) == TARGET_EXPR)
2764     t = TARGET_EXPR_INITIAL (t);
2765   if (TREE_CODE (t) == COMPOUND_EXPR)
2766     t = expr_last (t);
2767   if (TREE_CODE (t) == CONSTRUCTOR
2768       && EMPTY_CONSTRUCTOR_P (t))
2769     /* Default-initialization.  */
2770     return true;
2771
2772   /* If the initializer is a COND_EXPR, we can't preevaluate
2773      anything.  */
2774   if (TREE_CODE (t) == COND_EXPR)
2775     return false;
2776
2777   if (TREE_CODE (t) == CALL_EXPR)
2778     {
2779       stabilize_call (t, initp);
2780       return true;
2781     }
2782
2783   if (TREE_CODE (t) == AGGR_INIT_EXPR)
2784     {
2785       stabilize_aggr_init (t, initp);
2786       return true;
2787     }
2788
2789   /* The initialization is being performed via a bitwise copy -- and
2790      the item copied may have side effects.  */
2791   return TREE_SIDE_EFFECTS (init);
2792 }
2793
2794 /* Like "fold", but should be used whenever we might be processing the
2795    body of a template.  */
2796
2797 tree
2798 fold_if_not_in_template (tree expr)
2799 {
2800   /* In the body of a template, there is never any need to call
2801      "fold".  We will call fold later when actually instantiating the
2802      template.  Integral constant expressions in templates will be
2803      evaluated via fold_non_dependent_expr, as necessary.  */
2804   if (processing_template_decl)
2805     return expr;
2806
2807   /* Fold C++ front-end specific tree codes.  */
2808   if (TREE_CODE (expr) == UNARY_PLUS_EXPR)
2809     return fold_convert (TREE_TYPE (expr), TREE_OPERAND (expr, 0));
2810
2811   return fold (expr);
2812 }
2813
2814 /* Returns true if a cast to TYPE may appear in an integral constant
2815    expression.  */
2816
2817 bool
2818 cast_valid_in_integral_constant_expression_p (tree type)
2819 {
2820   return (INTEGRAL_OR_ENUMERATION_TYPE_P (type)
2821           || dependent_type_p (type)
2822           || type == error_mark_node);
2823 }
2824
2825 \f
2826 #if defined ENABLE_TREE_CHECKING && (GCC_VERSION >= 2007)
2827 /* Complain that some language-specific thing hanging off a tree
2828    node has been accessed improperly.  */
2829
2830 void
2831 lang_check_failed (const char* file, int line, const char* function)
2832 {
2833   internal_error ("lang_* check: failed in %s, at %s:%d",
2834                   function, trim_filename (file), line);
2835 }
2836 #endif /* ENABLE_TREE_CHECKING */
2837
2838 #include "gt-cp-tree.h"