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