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