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