contrib/gcc-3.4/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, 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, type, fn, TREE_OPERAND (init, 1), slot);
 306       TREE_SIDE_EFFECTS (rval) = 1;
 307       AGGR_INIT_VIA_CTOR_P (rval) = is_ctor;
 308     }
 309   else
 310     rval = init;
 311
 312   rval = build_target_expr (slot, rval);
 313
 314   return rval;
 315 }
 316
 317 /* Build a TARGET_EXPR using INIT to initialize a new temporary of the
 318    indicated TYPE.  */
 319
 320 tree
 321 build_target_expr_with_type (tree init, tree type)
 322 {
 323   tree slot;
 324
 325   if (TREE_CODE (init) == TARGET_EXPR)
 326     return init;
 327   else if (CLASS_TYPE_P (type) && !TYPE_HAS_TRIVIAL_INIT_REF (type)
 328            && TREE_CODE (init) != COND_EXPR
 329            && TREE_CODE (init) != CONSTRUCTOR
 330            && TREE_CODE (init) != VA_ARG_EXPR)
 331     /* We need to build up a copy constructor call.  COND_EXPR is a special
 332        case because we already have copies on the arms and we don't want
 333        another one here.  A CONSTRUCTOR is aggregate initialization, which
 334        is handled separately.  A VA_ARG_EXPR is magic creation of an
 335        aggregate; there's no additional work to be done.  */
 336     return force_rvalue (init);
 337
 338   slot = build_local_temp (type);
 339   return build_target_expr (slot, init);
 340 }
 341
 342 /* Like the above function, but without the checking.  This function should
 343    only be used by code which is deliberately trying to subvert the type
 344    system, such as call_builtin_trap.  */
 345
 346 tree
 347 force_target_expr (tree type, tree init)
 348 {
 349   tree slot = build_local_temp (type);
 350   return build_target_expr (slot, init);
 351 }
 352
 353 /* Like build_target_expr_with_type, but use the type of INIT.  */
 354
 355 tree
 356 get_target_expr (tree init)
 357 {
 358   return build_target_expr_with_type (init, TREE_TYPE (init));
 359 }
 360
 361 \f
 362 static tree
 363 build_cplus_array_type_1 (tree elt_type, tree index_type)
 364 {
 365   tree t;
 366
 367   if (elt_type == error_mark_node || index_type == error_mark_node)
 368     return error_mark_node;
 369
 370   if (dependent_type_p (elt_type)
 371       || (index_type
 372           && value_dependent_expression_p (TYPE_MAX_VALUE (index_type))))
 373     {
 374       t = make_node (ARRAY_TYPE);
 375       TREE_TYPE (t) = elt_type;
 376       TYPE_DOMAIN (t) = index_type;
 377     }
 378   else
 379     t = build_array_type (elt_type, index_type);
 380
 381   /* Push these needs up so that initialization takes place
 382      more easily.  */
 383   TYPE_NEEDS_CONSTRUCTING (t)
 384     = TYPE_NEEDS_CONSTRUCTING (TYPE_MAIN_VARIANT (elt_type));
 385   TYPE_HAS_NONTRIVIAL_DESTRUCTOR (t)
 386     = TYPE_HAS_NONTRIVIAL_DESTRUCTOR (TYPE_MAIN_VARIANT (elt_type));
 387   return t;
 388 }
 389
 390 tree
 391 build_cplus_array_type (tree elt_type, tree index_type)
 392 {
 393   tree t;
 394   int type_quals = cp_type_quals (elt_type);
 395
 396   if (type_quals != TYPE_UNQUALIFIED)
 397     elt_type = cp_build_qualified_type (elt_type, TYPE_UNQUALIFIED);
 398
 399   t = build_cplus_array_type_1 (elt_type, index_type);
 400
 401   if (type_quals != TYPE_UNQUALIFIED)
 402     t = cp_build_qualified_type (t, type_quals);
 403
 404   return t;
 405 }
 406 \f
 407 /* Make a variant of TYPE, qualified with the TYPE_QUALS.  Handles
 408    arrays correctly.  In particular, if TYPE is an array of T's, and
 409    TYPE_QUALS is non-empty, returns an array of qualified T's.
 410
 411    FLAGS determines how to deal with illformed qualifications. If
 412    tf_ignore_bad_quals is set, then bad qualifications are dropped
 413    (this is permitted if TYPE was introduced via a typedef or template
 414    type parameter). If bad qualifications are dropped and tf_warning
 415    is set, then a warning is issued for non-const qualifications.  If
 416    tf_ignore_bad_quals is not set and tf_error is not set, we
 417    return error_mark_node. Otherwise, we issue an error, and ignore
 418    the qualifications.
 419
 420    Qualification of a reference type is valid when the reference came
 421    via a typedef or template type argument. [dcl.ref] No such
 422    dispensation is provided for qualifying a function type.  [dcl.fct]
 423    DR 295 queries this and the proposed resolution brings it into line
 424    with qualifying a reference.  We implement the DR.  We also behave
 425    in a similar manner for restricting non-pointer types.  */
 426
 427 tree
 428 cp_build_qualified_type_real (tree type,
 429                               int type_quals,
 430                               tsubst_flags_t complain)
 431 {
 432   tree result;
 433   int bad_quals = TYPE_UNQUALIFIED;
 434
 435   if (type == error_mark_node)
 436     return type;
 437
 438   if (type_quals == cp_type_quals (type))
 439     return type;
 440
 441   if (TREE_CODE (type) == ARRAY_TYPE)
 442     {
 443       /* In C++, the qualification really applies to the array element
 444          type.  Obtain the appropriately qualified element type.  */
 445       tree t;
 446       tree element_type
 447         = cp_build_qualified_type_real (TREE_TYPE (type),
 448                                         type_quals,
 449                                         complain);
 450
 451       if (element_type == error_mark_node)
 452         return error_mark_node;
 453
 454       /* See if we already have an identically qualified type.  */
 455       for (t = TYPE_MAIN_VARIANT (type); t; t = TYPE_NEXT_VARIANT (t))
 456         if (cp_type_quals (t) == type_quals
 457             && TYPE_NAME (t) == TYPE_NAME (type)
 458             && TYPE_CONTEXT (t) == TYPE_CONTEXT (type))
 459           break;
 460
 461       if (!t)
 462         {
 463           /* Make a new array type, just like the old one, but with the
 464              appropriately qualified element type.  */
 465           t = build_type_copy (type);
 466           TREE_TYPE (t) = element_type;
 467         }
 468
 469       /* Even if we already had this variant, we update
 470          TYPE_NEEDS_CONSTRUCTING and TYPE_HAS_NONTRIVIAL_DESTRUCTOR in case
 471          they changed since the variant was originally created.
 472
 473          This seems hokey; if there is some way to use a previous
 474          variant *without* coming through here,
 475          TYPE_NEEDS_CONSTRUCTING will never be updated.  */
 476       TYPE_NEEDS_CONSTRUCTING (t)
 477         = TYPE_NEEDS_CONSTRUCTING (TYPE_MAIN_VARIANT (element_type));
 478       TYPE_HAS_NONTRIVIAL_DESTRUCTOR (t)
 479         = TYPE_HAS_NONTRIVIAL_DESTRUCTOR (TYPE_MAIN_VARIANT (element_type));
 480       return t;
 481     }
 482   else if (TYPE_PTRMEMFUNC_P (type))
 483     {
 484       /* For a pointer-to-member type, we can't just return a
 485          cv-qualified version of the RECORD_TYPE.  If we do, we
 486          haven't changed the field that contains the actual pointer to
 487          a method, and so TYPE_PTRMEMFUNC_FN_TYPE will be wrong.  */
 488       tree t;
 489
 490       t = TYPE_PTRMEMFUNC_FN_TYPE (type);
 491       t = cp_build_qualified_type_real (t, type_quals, complain);
 492       return build_ptrmemfunc_type (t);
 493     }
 494
 495   /* A reference, function or method type shall not be cv qualified.
 496      [dcl.ref], [dct.fct]  */
 497   if (type_quals & (TYPE_QUAL_CONST | TYPE_QUAL_VOLATILE)
 498       && (TREE_CODE (type) == REFERENCE_TYPE
 499           || TREE_CODE (type) == FUNCTION_TYPE
 500           || TREE_CODE (type) == METHOD_TYPE))
 501     {
 502       bad_quals |= type_quals & (TYPE_QUAL_CONST | TYPE_QUAL_VOLATILE);
 503       type_quals &= ~(TYPE_QUAL_CONST | TYPE_QUAL_VOLATILE);
 504     }
 505
 506   /* A restrict-qualified type must be a pointer (or reference)
 507      to object or incomplete type.  */
 508   if ((type_quals & TYPE_QUAL_RESTRICT)
 509       && TREE_CODE (type) != TEMPLATE_TYPE_PARM
 510       && TREE_CODE (type) != TYPENAME_TYPE
 511       && !POINTER_TYPE_P (type))
 512     {
 513       bad_quals |= TYPE_QUAL_RESTRICT;
 514       type_quals &= ~TYPE_QUAL_RESTRICT;
 515     }
 516
 517   if (bad_quals == TYPE_UNQUALIFIED)
 518     /*OK*/;
 519   else if (!(complain & (tf_error | tf_ignore_bad_quals)))
 520     return error_mark_node;
 521   else
 522     {
 523       if (complain & tf_ignore_bad_quals)
 524         /* We're not going to warn about constifying things that can't
 525            be constified.  */
 526         bad_quals &= ~TYPE_QUAL_CONST;
 527       if (bad_quals)
 528         {
 529           tree bad_type = build_qualified_type (ptr_type_node, bad_quals);
 530
 531           if (!(complain & tf_ignore_bad_quals))
 532             error ("`%V' qualifiers cannot be applied to `%T'",
 533                    bad_type, type);
 534         }
 535     }
 536
 537   /* Retrieve (or create) the appropriately qualified variant.  */
 538   result = build_qualified_type (type, type_quals);
 539
 540   /* If this was a pointer-to-method type, and we just made a copy,
 541      then we need to unshare the record that holds the cached
 542      pointer-to-member-function type, because these will be distinct
 543      between the unqualified and qualified types.  */
 544   if (result != type
 545       && TREE_CODE (type) == POINTER_TYPE
 546       && TREE_CODE (TREE_TYPE (type)) == METHOD_TYPE)
 547     TYPE_LANG_SPECIFIC (result) = NULL;
 548
 549   return result;
 550 }
 551
 552 /* Returns the canonical version of TYPE.  In other words, if TYPE is
 553    a typedef, returns the underlying type.  The cv-qualification of
 554    the type returned matches the type input; they will always be
 555    compatible types.  */
 556
 557 tree
 558 canonical_type_variant (tree t)
 559 {
 560   return cp_build_qualified_type (TYPE_MAIN_VARIANT (t), cp_type_quals (t));
 561 }
 562 \f
 563 /* Makes new binfos for the indirect bases under BINFO. T is the most
 564    derived TYPE. PREV is the previous binfo, whose TREE_CHAIN we make
 565    point to this binfo. We return the last BINFO created.
 566
 567    The CLASSTYPE_VBASECLASSES list of T is constructed in reverse
 568    order (pre-order, depth-first, right-to-left). You must nreverse it.
 569
 570    The BINFO_INHERITANCE of a virtual base class points to the binfo
 571    og the most derived type.
 572
 573    The binfo's TREE_CHAIN is set to inheritance graph order, but bases
 574    for non-class types are not included (i.e. those which are
 575    dependent bases in non-instantiated templates).  */
 576
 577 tree
 578 copy_base_binfos (tree binfo, tree t, tree prev)
 579 {
 580   tree binfos = BINFO_BASETYPES (binfo);
 581   int n, ix;
 582
 583   if (prev)
 584     TREE_CHAIN (prev) = binfo;
 585   prev = binfo;
 586
 587   if (binfos == NULL_TREE)
 588     return prev;
 589
 590   n = TREE_VEC_LENGTH (binfos);
 591
 592   /* Now copy the structure beneath BINFO.  */
 593   for (ix = 0; ix != n; ix++)
 594     {
 595       tree base_binfo = TREE_VEC_ELT (binfos, ix);
 596       tree new_binfo = NULL_TREE;
 597
 598       if (!CLASS_TYPE_P (BINFO_TYPE (base_binfo)))
 599         {
 600           my_friendly_assert (binfo == TYPE_BINFO (t), 20030204);
 601
 602           new_binfo = base_binfo;
 603           TREE_CHAIN (prev) = new_binfo;
 604           prev = new_binfo;
 605           BINFO_INHERITANCE_CHAIN (new_binfo) = binfo;
 606           BINFO_DEPENDENT_BASE_P (new_binfo) = 1;
 607         }
 608       else if (TREE_VIA_VIRTUAL (base_binfo))
 609         {
 610           new_binfo = purpose_member (BINFO_TYPE (base_binfo),
 611                                       CLASSTYPE_VBASECLASSES (t));
 612           if (new_binfo)
 613             new_binfo = TREE_VALUE (new_binfo);
 614         }
 615
 616       if (!new_binfo)
 617         {
 618           new_binfo = make_binfo (BINFO_OFFSET (base_binfo),
 619                                   base_binfo, NULL_TREE,
 620                                   BINFO_VIRTUALS (base_binfo));
 621           prev = copy_base_binfos (new_binfo, t, prev);
 622           if (TREE_VIA_VIRTUAL (base_binfo))
 623             {
 624               CLASSTYPE_VBASECLASSES (t)
 625                 = tree_cons (BINFO_TYPE (new_binfo), new_binfo,
 626                              CLASSTYPE_VBASECLASSES (t));
 627               TREE_VIA_VIRTUAL (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 += TYPE_HASH (chain);
 683
 684   if (value)
 685     hashcode += TYPE_HASH (value);
 686   else
 687     hashcode += 1007;
 688   if (purpose)
 689     hashcode += TYPE_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_vec (BINFO_LANG_ELTS);
 775   tree type;
 776
 777   if (TREE_CODE (binfo) == TREE_VEC)
 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_BASETYPES (binfo) != NULL_TREE)
 796     {
 797       BINFO_BASETYPES (new_binfo) = copy_node (BINFO_BASETYPES (binfo));
 798       /* We do not need to copy the accesses, as they are read only.  */
 799       BINFO_BASEACCESSES (new_binfo) = BINFO_BASEACCESSES (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 (TYPE_QUALS (v) == type_quals
 981         && comp_except_specs (raises, TYPE_RAISES_EXCEPTIONS (v), 1)
 982         && (*targetm.comp_type_attributes) (type, v))
 983       return v;
 984
 985   /* Need to build a new variant.  */
 986   v = build_type_copy (type);
 987   TYPE_RAISES_EXCEPTIONS (v) = raises;
 988   return v;
 989 }
 990
 991 /* Given a TEMPLATE_TEMPLATE_PARM node T, create a new
 992    BOUND_TEMPLATE_TEMPLATE_PARM bound with NEWARGS as its template
 993    arguments.  */
 994
 995 tree
 996 bind_template_template_parm (tree t, tree newargs)
 997 {
 998   tree decl = TYPE_NAME (t);
 999   tree t2;
1000
1001   t2 = make_aggr_type (BOUND_TEMPLATE_TEMPLATE_PARM);
1002   decl = build_decl (TYPE_DECL, DECL_NAME (decl), NULL_TREE);
1003
1004   /* These nodes have to be created to reflect new TYPE_DECL and template
1005      arguments.  */
1006   TEMPLATE_TYPE_PARM_INDEX (t2) = copy_node (TEMPLATE_TYPE_PARM_INDEX (t));
1007   TEMPLATE_PARM_DECL (TEMPLATE_TYPE_PARM_INDEX (t2)) = decl;
1008   TEMPLATE_TEMPLATE_PARM_TEMPLATE_INFO (t2)
1009     = tree_cons (TEMPLATE_TEMPLATE_PARM_TEMPLATE_DECL (t),
1010                  newargs, NULL_TREE);
1011
1012   TREE_TYPE (decl) = t2;
1013   TYPE_NAME (t2) = decl;
1014   TYPE_STUB_DECL (t2) = decl;
1015   TYPE_SIZE (t2) = 0;
1016
1017   return t2;
1018 }
1019
1020 /* Called from count_trees via walk_tree.  */
1021
1022 static tree
1023 count_trees_r (tree* tp ATTRIBUTE_UNUSED ,
1024                int* walk_subtrees ATTRIBUTE_UNUSED ,
1025                void* data)
1026 {
1027   ++ *((int*) data);
1028   return NULL_TREE;
1029 }
1030
1031 /* Debugging function for measuring the rough complexity of a tree
1032    representation.  */
1033
1034 int
1035 count_trees (tree t)
1036 {
1037   int n_trees = 0;
1038   walk_tree_without_duplicates (&t, count_trees_r, &n_trees);
1039   return n_trees;
1040 }
1041
1042 /* Called from verify_stmt_tree via walk_tree.  */
1043
1044 static tree
1045 verify_stmt_tree_r (tree* tp,
1046                     int* walk_subtrees ATTRIBUTE_UNUSED ,
1047                     void* data)
1048 {
1049   tree t = *tp;
1050   htab_t *statements = (htab_t *) data;
1051   void **slot;
1052
1053   if (!STATEMENT_CODE_P (TREE_CODE (t)))
1054     return NULL_TREE;
1055
1056   /* If this statement is already present in the hash table, then
1057      there is a circularity in the statement tree.  */
1058   if (htab_find (*statements, t))
1059     abort ();
1060
1061   slot = htab_find_slot (*statements, t, INSERT);
1062   *slot = t;
1063
1064   return NULL_TREE;
1065 }
1066
1067 /* Debugging function to check that the statement T has not been
1068    corrupted.  For now, this function simply checks that T contains no
1069    circularities.  */
1070
1071 void
1072 verify_stmt_tree (tree t)
1073 {
1074   htab_t statements;
1075   statements = htab_create (37, htab_hash_pointer, htab_eq_pointer, NULL);
1076   walk_tree (&t, verify_stmt_tree_r, &statements, NULL);
1077   htab_delete (statements);
1078 }
1079
1080 /* Called from find_tree via walk_tree.  */
1081
1082 static tree
1083 find_tree_r (tree* tp,
1084              int* walk_subtrees ATTRIBUTE_UNUSED ,
1085              void* data)
1086 {
1087   if (*tp == (tree) data)
1088     return (tree) data;
1089
1090   return NULL_TREE;
1091 }
1092
1093 /* Returns X if X appears in the tree structure rooted at T.  */
1094
1095 tree
1096 find_tree (tree t, tree x)
1097 {
1098   return walk_tree_without_duplicates (&t, find_tree_r, x);
1099 }
1100
1101 /* Passed to walk_tree.  Checks for the use of types with no linkage.  */
1102
1103 static tree
1104 no_linkage_helper (tree* tp,
1105                    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   return NULL_TREE;
1116 }
1117
1118 /* Check if the type T depends on a type with no linkage and if so, return
1119    it.  */
1120
1121 tree
1122 no_linkage_check (tree t)
1123 {
1124   /* There's no point in checking linkage on template functions; we
1125      can't know their complete types.  */
1126   if (processing_template_decl)
1127     return NULL_TREE;
1128
1129   t = walk_tree_without_duplicates (&t, no_linkage_helper, NULL);
1130   if (t != error_mark_node)
1131     return t;
1132   return NULL_TREE;
1133 }
1134
1135 #ifdef GATHER_STATISTICS
1136 extern int depth_reached;
1137 #endif
1138
1139 void
1140 cxx_print_statistics (void)
1141 {
1142   print_search_statistics ();
1143   print_class_statistics ();
1144 #ifdef GATHER_STATISTICS
1145   fprintf (stderr, "maximum template instantiation depth reached: %d\n",
1146            depth_reached);
1147 #endif
1148 }
1149
1150 /* Return, as an INTEGER_CST node, the number of elements for TYPE
1151    (which is an ARRAY_TYPE).  This counts only elements of the top
1152    array.  */
1153
1154 tree
1155 array_type_nelts_top (tree type)
1156 {
1157   return fold (build (PLUS_EXPR, sizetype,
1158                       array_type_nelts (type),
1159                       integer_one_node));
1160 }
1161
1162 /* Return, as an INTEGER_CST node, the number of elements for TYPE
1163    (which is an ARRAY_TYPE).  This one is a recursive count of all
1164    ARRAY_TYPEs that are clumped together.  */
1165
1166 tree
1167 array_type_nelts_total (tree type)
1168 {
1169   tree sz = array_type_nelts_top (type);
1170   type = TREE_TYPE (type);
1171   while (TREE_CODE (type) == ARRAY_TYPE)
1172     {
1173       tree n = array_type_nelts_top (type);
1174       sz = fold (build (MULT_EXPR, sizetype, sz, n));
1175       type = TREE_TYPE (type);
1176     }
1177   return sz;
1178 }
1179
1180 /* Called from break_out_target_exprs via mapcar.  */
1181
1182 static tree
1183 bot_manip (tree* tp, int* walk_subtrees, void* data)
1184 {
1185   splay_tree target_remap = ((splay_tree) data);
1186   tree t = *tp;
1187
1188   if (TREE_CONSTANT (t))
1189     {
1190       /* There can't be any TARGET_EXPRs or their slot variables below
1191          this point.  We used to check !TREE_SIDE_EFFECTS, but then we
1192          failed to copy an ADDR_EXPR of the slot VAR_DECL.  */
1193       *walk_subtrees = 0;
1194       return NULL_TREE;
1195     }
1196   if (TREE_CODE (t) == TARGET_EXPR)
1197     {
1198       tree u;
1199
1200       if (TREE_CODE (TREE_OPERAND (t, 1)) == AGGR_INIT_EXPR)
1201         {
1202           mark_used (TREE_OPERAND (TREE_OPERAND (TREE_OPERAND (t, 1), 0), 0));
1203           u = build_cplus_new
1204             (TREE_TYPE (t), break_out_target_exprs (TREE_OPERAND (t, 1)));
1205         }
1206       else
1207         {
1208           u = build_target_expr_with_type
1209             (break_out_target_exprs (TREE_OPERAND (t, 1)), TREE_TYPE (t));
1210         }
1211
1212       /* Map the old variable to the new one.  */
1213       splay_tree_insert (target_remap,
1214                          (splay_tree_key) TREE_OPERAND (t, 0),
1215                          (splay_tree_value) TREE_OPERAND (u, 0));
1216
1217       /* Replace the old expression with the new version.  */
1218       *tp = u;
1219       /* We don't have to go below this point; the recursive call to
1220          break_out_target_exprs will have handled anything below this
1221          point.  */
1222       *walk_subtrees = 0;
1223       return NULL_TREE;
1224     }
1225   else if (TREE_CODE (t) == CALL_EXPR)
1226     mark_used (TREE_OPERAND (TREE_OPERAND (t, 0), 0));
1227
1228   /* Make a copy of this node.  */
1229   return copy_tree_r (tp, walk_subtrees, NULL);
1230 }
1231
1232 /* Replace all remapped VAR_DECLs in T with their new equivalents.
1233    DATA is really a splay-tree mapping old variables to new
1234    variables.  */
1235
1236 static tree
1237 bot_replace (tree* t,
1238              int* walk_subtrees ATTRIBUTE_UNUSED ,
1239              void* data)
1240 {
1241   splay_tree target_remap = ((splay_tree) data);
1242
1243   if (TREE_CODE (*t) == VAR_DECL)
1244     {
1245       splay_tree_node n = splay_tree_lookup (target_remap,
1246                                              (splay_tree_key) *t);
1247       if (n)
1248         *t = (tree) n->value;
1249     }
1250
1251   return NULL_TREE;
1252 }
1253
1254 /* When we parse a default argument expression, we may create
1255    temporary variables via TARGET_EXPRs.  When we actually use the
1256    default-argument expression, we make a copy of the expression, but
1257    we must replace the temporaries with appropriate local versions.  */
1258
1259 tree
1260 break_out_target_exprs (tree t)
1261 {
1262   static int target_remap_count;
1263   static splay_tree target_remap;
1264
1265   if (!target_remap_count++)
1266     target_remap = splay_tree_new (splay_tree_compare_pointers,
1267                                    /*splay_tree_delete_key_fn=*/NULL,
1268                                    /*splay_tree_delete_value_fn=*/NULL);
1269   walk_tree (&t, bot_manip, target_remap, NULL);
1270   walk_tree (&t, bot_replace, target_remap, NULL);
1271
1272   if (!--target_remap_count)
1273     {
1274       splay_tree_delete (target_remap);
1275       target_remap = NULL;
1276     }
1277
1278   return t;
1279 }
1280
1281 /* Similar to `build_nt', but for template definitions of dependent
1282    expressions  */
1283
1284 tree
1285 build_min_nt (enum tree_code code, ...)
1286 {
1287   tree t;
1288   int length;
1289   int i;
1290   va_list p;
1291
1292   va_start (p, code);
1293
1294   t = make_node (code);
1295   length = TREE_CODE_LENGTH (code);
1296   TREE_COMPLEXITY (t) = input_line;
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   TREE_COMPLEXITY (t) = input_line;
1324
1325   for (i = 0; i < length; i++)
1326     {
1327       tree x = va_arg (p, tree);
1328       TREE_OPERAND (t, i) = x;
1329       if (x && TREE_SIDE_EFFECTS (x))
1330         TREE_SIDE_EFFECTS (t) = 1;
1331     }
1332
1333   va_end (p);
1334   return t;
1335 }
1336
1337 /* Similar to `build', but for template definitions of non-dependent
1338    expressions. NON_DEP is the non-dependent expression that has been
1339    built.  */
1340
1341 tree
1342 build_min_non_dep (enum tree_code code, tree non_dep, ...)
1343 {
1344   tree t;
1345   int length;
1346   int i;
1347   va_list p;
1348
1349   va_start (p, non_dep);
1350
1351   t = make_node (code);
1352   length = TREE_CODE_LENGTH (code);
1353   TREE_TYPE (t) = TREE_TYPE (non_dep);
1354   TREE_COMPLEXITY (t) = input_line;
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 /* Returns an INTEGER_CST (of type `int') corresponding to I.
1373    Multiple calls with the same value of I may or may not yield the
1374    same node; therefore, callers should never modify the node
1375    returned.  */
1376
1377 static GTY(()) tree shared_int_cache[256];
1378
1379 tree
1380 build_shared_int_cst (int i)
1381 {
1382   if (i >= 256)
1383     return build_int_2 (i, 0);
1384
1385   if (!shared_int_cache[i])
1386     shared_int_cache[i] = build_int_2 (i, 0);
1387
1388   return shared_int_cache[i];
1389 }
1390
1391 tree
1392 get_type_decl (tree t)
1393 {
1394   if (TREE_CODE (t) == TYPE_DECL)
1395     return t;
1396   if (TYPE_P (t))
1397     return TYPE_STUB_DECL (t);
1398   if (t == error_mark_node)
1399     return t;
1400
1401   abort ();
1402
1403   /* Stop compiler from complaining control reaches end of non-void function.  */
1404   return 0;
1405 }
1406
1407 /* Return first vector element whose BINFO_TYPE is ELEM.
1408    Return 0 if ELEM is not in VEC.  VEC may be NULL_TREE.  */
1409
1410 tree
1411 vec_binfo_member (tree elem, tree vec)
1412 {
1413   int i;
1414
1415   if (vec)
1416     for (i = 0; i < TREE_VEC_LENGTH (vec); ++i)
1417       if (same_type_p (elem, BINFO_TYPE (TREE_VEC_ELT (vec, i))))
1418         return TREE_VEC_ELT (vec, i);
1419
1420   return NULL_TREE;
1421 }
1422
1423 /* Returns the namespace that contains DECL, whether directly or
1424    indirectly.  */
1425
1426 tree
1427 decl_namespace_context (tree decl)
1428 {
1429   while (1)
1430     {
1431       if (TREE_CODE (decl) == NAMESPACE_DECL)
1432         return decl;
1433       else if (TYPE_P (decl))
1434         decl = CP_DECL_CONTEXT (TYPE_MAIN_DECL (decl));
1435       else
1436         decl = CP_DECL_CONTEXT (decl);
1437     }
1438 }
1439
1440 /* Return truthvalue of whether T1 is the same tree structure as T2.
1441    Return 1 if they are the same. Return 0 if they are different.  */
1442
1443 bool
1444 cp_tree_equal (tree t1, tree t2)
1445 {
1446   enum tree_code code1, code2;
1447
1448   if (t1 == t2)
1449     return true;
1450   if (!t1 || !t2)
1451     return false;
1452
1453   for (code1 = TREE_CODE (t1);
1454        code1 == NOP_EXPR || code1 == CONVERT_EXPR
1455          || code1 == NON_LVALUE_EXPR;
1456        code1 = TREE_CODE (t1))
1457     t1 = TREE_OPERAND (t1, 0);
1458   for (code2 = TREE_CODE (t2);
1459        code2 == NOP_EXPR || code2 == CONVERT_EXPR
1460          || code1 == NON_LVALUE_EXPR;
1461        code2 = TREE_CODE (t2))
1462     t2 = TREE_OPERAND (t2, 0);
1463
1464   /* They might have become equal now.  */
1465   if (t1 == t2)
1466     return true;
1467
1468   if (code1 != code2)
1469     return false;
1470
1471   switch (code1)
1472     {
1473     case INTEGER_CST:
1474       return TREE_INT_CST_LOW (t1) == TREE_INT_CST_LOW (t2)
1475         && TREE_INT_CST_HIGH (t1) == TREE_INT_CST_HIGH (t2);
1476
1477     case REAL_CST:
1478       return REAL_VALUES_EQUAL (TREE_REAL_CST (t1), TREE_REAL_CST (t2));
1479
1480     case STRING_CST:
1481       return TREE_STRING_LENGTH (t1) == TREE_STRING_LENGTH (t2)
1482         && !memcmp (TREE_STRING_POINTER (t1), TREE_STRING_POINTER (t2),
1483                     TREE_STRING_LENGTH (t1));
1484
1485     case CONSTRUCTOR:
1486       /* We need to do this when determining whether or not two
1487          non-type pointer to member function template arguments
1488          are the same.  */
1489       if (!(same_type_p (TREE_TYPE (t1), TREE_TYPE (t2))
1490             /* The first operand is RTL.  */
1491             && TREE_OPERAND (t1, 0) == TREE_OPERAND (t2, 0)))
1492         return false;
1493       return cp_tree_equal (TREE_OPERAND (t1, 1), TREE_OPERAND (t2, 1));
1494
1495     case TREE_LIST:
1496       if (!cp_tree_equal (TREE_PURPOSE (t1), TREE_PURPOSE (t2)))
1497         return false;
1498       if (!cp_tree_equal (TREE_VALUE (t1), TREE_VALUE (t2)))
1499         return false;
1500       return cp_tree_equal (TREE_CHAIN (t1), TREE_CHAIN (t2));
1501
1502     case SAVE_EXPR:
1503       return cp_tree_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
1504
1505     case CALL_EXPR:
1506       if (!cp_tree_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0)))
1507         return false;
1508       return cp_tree_equal (TREE_OPERAND (t1, 1), TREE_OPERAND (t2, 1));
1509
1510     case TARGET_EXPR:
1511       {
1512         tree o1 = TREE_OPERAND (t1, 0);
1513         tree o2 = TREE_OPERAND (t2, 0);
1514
1515         /* Special case: if either target is an unallocated VAR_DECL,
1516            it means that it's going to be unified with whatever the
1517            TARGET_EXPR is really supposed to initialize, so treat it
1518            as being equivalent to anything.  */
1519         if (TREE_CODE (o1) == VAR_DECL && DECL_NAME (o1) == NULL_TREE
1520             && !DECL_RTL_SET_P (o1))
1521           /*Nop*/;
1522         else if (TREE_CODE (o2) == VAR_DECL && DECL_NAME (o2) == NULL_TREE
1523                  && !DECL_RTL_SET_P (o2))
1524           /*Nop*/;
1525         else if (!cp_tree_equal (o1, o2))
1526           return false;
1527
1528         return cp_tree_equal (TREE_OPERAND (t1, 1), TREE_OPERAND (t2, 1));
1529       }
1530
1531     case WITH_CLEANUP_EXPR:
1532       if (!cp_tree_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0)))
1533         return false;
1534       return cp_tree_equal (TREE_OPERAND (t1, 1), TREE_OPERAND (t1, 1));
1535
1536     case COMPONENT_REF:
1537       if (TREE_OPERAND (t1, 1) != TREE_OPERAND (t2, 1))
1538         return false;
1539       return cp_tree_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
1540
1541     case VAR_DECL:
1542     case PARM_DECL:
1543     case CONST_DECL:
1544     case FUNCTION_DECL:
1545     case TEMPLATE_DECL:
1546     case IDENTIFIER_NODE:
1547       return false;
1548
1549     case BASELINK:
1550       return (BASELINK_BINFO (t1) == BASELINK_BINFO (t2)
1551               && BASELINK_ACCESS_BINFO (t1) == BASELINK_ACCESS_BINFO (t2)
1552               && cp_tree_equal (BASELINK_FUNCTIONS (t1),
1553                                 BASELINK_FUNCTIONS (t2)));
1554
1555     case TEMPLATE_PARM_INDEX:
1556       return (TEMPLATE_PARM_IDX (t1) == TEMPLATE_PARM_IDX (t2)
1557               && TEMPLATE_PARM_LEVEL (t1) == TEMPLATE_PARM_LEVEL (t2)
1558               && same_type_p (TREE_TYPE (TEMPLATE_PARM_DECL (t1)),
1559                               TREE_TYPE (TEMPLATE_PARM_DECL (t2))));
1560
1561     case TEMPLATE_ID_EXPR:
1562       {
1563         unsigned ix;
1564         tree vec1, vec2;
1565
1566         if (!cp_tree_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0)))
1567           return false;
1568         vec1 = TREE_OPERAND (t1, 1);
1569         vec2 = TREE_OPERAND (t2, 1);
1570
1571         if (!vec1 || !vec2)
1572           return !vec1 && !vec2;
1573
1574         if (TREE_VEC_LENGTH (vec1) != TREE_VEC_LENGTH (vec2))
1575           return false;
1576
1577         for (ix = TREE_VEC_LENGTH (vec1); ix--;)
1578           if (!cp_tree_equal (TREE_VEC_ELT (vec1, ix),
1579                               TREE_VEC_ELT (vec2, ix)))
1580             return false;
1581
1582         return true;
1583       }
1584
1585     case SIZEOF_EXPR:
1586     case ALIGNOF_EXPR:
1587       {
1588         tree o1 = TREE_OPERAND (t1, 0);
1589         tree o2 = TREE_OPERAND (t2, 0);
1590
1591         if (TREE_CODE (o1) != TREE_CODE (o2))
1592           return false;
1593         if (TYPE_P (o1))
1594           return same_type_p (o1, o2);
1595         else
1596           return cp_tree_equal (o1, o2);
1597       }
1598
1599     case PTRMEM_CST:
1600       /* Two pointer-to-members are the same if they point to the same
1601          field or function in the same class.  */
1602       if (PTRMEM_CST_MEMBER (t1) != PTRMEM_CST_MEMBER (t2))
1603         return false;
1604
1605       return same_type_p (PTRMEM_CST_CLASS (t1), PTRMEM_CST_CLASS (t2));
1606
1607     case OVERLOAD:
1608       if (OVL_FUNCTION (t1) != OVL_FUNCTION (t2))
1609         return false;
1610       return cp_tree_equal (OVL_CHAIN (t1), OVL_CHAIN (t2));
1611
1612     default:
1613       break;
1614     }
1615
1616   switch (TREE_CODE_CLASS (code1))
1617     {
1618     case '1':
1619     case '2':
1620     case '<':
1621     case 'e':
1622     case 'r':
1623     case 's':
1624       {
1625         int i;
1626
1627         for (i = 0; i < TREE_CODE_LENGTH (code1); ++i)
1628           if (!cp_tree_equal (TREE_OPERAND (t1, i), TREE_OPERAND (t2, i)))
1629             return false;
1630
1631         return true;
1632       }
1633
1634     case 't':
1635       return same_type_p (t1, t2);
1636     }
1637
1638   my_friendly_assert (0, 20030617);
1639   return false;
1640 }
1641
1642 /* Build a wrapper around a 'struct z_candidate' so we can use it as a
1643    tree.  */
1644
1645 tree
1646 build_zc_wrapper (struct z_candidate* ptr)
1647 {
1648   tree t = make_node (WRAPPER);
1649   WRAPPER_ZC (t) = ptr;
1650   return t;
1651 }
1652
1653 /* The type of ARG when used as an lvalue.  */
1654
1655 tree
1656 lvalue_type (tree arg)
1657 {
1658   tree type = TREE_TYPE (arg);
1659   return type;
1660 }
1661
1662 /* The type of ARG for printing error messages; denote lvalues with
1663    reference types.  */
1664
1665 tree
1666 error_type (tree arg)
1667 {
1668   tree type = TREE_TYPE (arg);
1669
1670   if (TREE_CODE (type) == ARRAY_TYPE)
1671     ;
1672   else if (TREE_CODE (type) == ERROR_MARK)
1673     ;
1674   else if (real_lvalue_p (arg))
1675     type = build_reference_type (lvalue_type (arg));
1676   else if (IS_AGGR_TYPE (type))
1677     type = lvalue_type (arg);
1678
1679   return type;
1680 }
1681
1682 /* Does FUNCTION use a variable-length argument list?  */
1683
1684 int
1685 varargs_function_p (tree function)
1686 {
1687   tree parm = TYPE_ARG_TYPES (TREE_TYPE (function));
1688   for (; parm; parm = TREE_CHAIN (parm))
1689     if (TREE_VALUE (parm) == void_type_node)
1690       return 0;
1691   return 1;
1692 }
1693
1694 /* Returns 1 if decl is a member of a class.  */
1695
1696 int
1697 member_p (tree decl)
1698 {
1699   const tree ctx = DECL_CONTEXT (decl);
1700   return (ctx && TYPE_P (ctx));
1701 }
1702
1703 /* Create a placeholder for member access where we don't actually have an
1704    object that the access is against.  */
1705
1706 tree
1707 build_dummy_object (tree type)
1708 {
1709   tree decl = build1 (NOP_EXPR, build_pointer_type (type), void_zero_node);
1710   return build_indirect_ref (decl, NULL);
1711 }
1712
1713 /* We've gotten a reference to a member of TYPE.  Return *this if appropriate,
1714    or a dummy object otherwise.  If BINFOP is non-0, it is filled with the
1715    binfo path from current_class_type to TYPE, or 0.  */
1716
1717 tree
1718 maybe_dummy_object (tree type, tree* binfop)
1719 {
1720   tree decl, context;
1721   tree binfo;
1722
1723   if (current_class_type
1724       && (binfo = lookup_base (current_class_type, type,
1725                                ba_ignore | ba_quiet, NULL)))
1726     context = current_class_type;
1727   else
1728     {
1729       /* Reference from a nested class member function.  */
1730       context = type;
1731       binfo = TYPE_BINFO (type);
1732     }
1733
1734   if (binfop)
1735     *binfop = binfo;
1736
1737   if (current_class_ref && context == current_class_type
1738       /* Kludge: Make sure that current_class_type is actually
1739          correct.  It might not be if we're in the middle of
1740          tsubst_default_argument.  */
1741       && same_type_p (TYPE_MAIN_VARIANT (TREE_TYPE (current_class_ref)),
1742                       current_class_type))
1743     decl = current_class_ref;
1744   else
1745     decl = build_dummy_object (context);
1746
1747   return decl;
1748 }
1749
1750 /* Returns 1 if OB is a placeholder object, or a pointer to one.  */
1751
1752 int
1753 is_dummy_object (tree ob)
1754 {
1755   if (TREE_CODE (ob) == INDIRECT_REF)
1756     ob = TREE_OPERAND (ob, 0);
1757   return (TREE_CODE (ob) == NOP_EXPR
1758           && TREE_OPERAND (ob, 0) == void_zero_node);
1759 }
1760
1761 /* Returns 1 iff type T is a POD type, as defined in [basic.types].  */
1762
1763 int
1764 pod_type_p (tree t)
1765 {
1766   t = strip_array_types (t);
1767
1768   if (t == error_mark_node)
1769     return 1;
1770   if (INTEGRAL_TYPE_P (t))
1771     return 1;  /* integral, character or enumeral type */
1772   if (FLOAT_TYPE_P (t))
1773     return 1;
1774   if (TYPE_PTR_P (t))
1775     return 1; /* pointer to non-member */
1776   if (TYPE_PTR_TO_MEMBER_P (t))
1777     return 1; /* pointer to member */
1778   if (TREE_CODE (t) == VECTOR_TYPE)
1779     return 1; /* vectors are (small) arrays of scalars */
1780
1781   if (! CLASS_TYPE_P (t))
1782     return 0; /* other non-class type (reference or function) */
1783   if (CLASSTYPE_NON_POD_P (t))
1784     return 0;
1785   return 1;
1786 }
1787
1788 /* Returns 1 iff zero initialization of type T means actually storing
1789    zeros in it.  */
1790
1791 int
1792 zero_init_p (tree t)
1793 {
1794   t = strip_array_types (t);
1795
1796   if (t == error_mark_node)
1797     return 1;
1798
1799   /* NULL pointers to data members are initialized with -1.  */
1800   if (TYPE_PTRMEM_P (t))
1801     return 0;
1802
1803   /* Classes that contain types that can't be zero-initialized, cannot
1804      be zero-initialized themselves.  */
1805   if (CLASS_TYPE_P (t) && CLASSTYPE_NON_ZERO_INIT_P (t))
1806     return 0;
1807
1808   return 1;
1809 }
1810
1811 /* Table of valid C++ attributes.  */
1812 const struct attribute_spec cxx_attribute_table[] =
1813 {
1814   /* { name, min_len, max_len, decl_req, type_req, fn_type_req, handler } */
1815   { "java_interface", 0, 0, false, false, false, handle_java_interface_attribute },
1816   { "com_interface",  0, 0, false, false, false, handle_com_interface_attribute },
1817   { "init_priority",  1, 1, true,  false, false, handle_init_priority_attribute },
1818   { NULL,             0, 0, false, false, false, NULL }
1819 };
1820
1821 /* Handle a "java_interface" attribute; arguments as in
1822    struct attribute_spec.handler.  */
1823 static tree
1824 handle_java_interface_attribute (tree* node,
1825                                  tree name,
1826                                  tree args ATTRIBUTE_UNUSED ,
1827                                  int flags,
1828                                  bool* no_add_attrs)
1829 {
1830   if (DECL_P (*node)
1831       || !CLASS_TYPE_P (*node)
1832       || !TYPE_FOR_JAVA (*node))
1833     {
1834       error ("`%s' attribute can only be applied to Java class definitions",
1835              IDENTIFIER_POINTER (name));
1836       *no_add_attrs = true;
1837       return NULL_TREE;
1838     }
1839   if (!(flags & (int) ATTR_FLAG_TYPE_IN_PLACE))
1840     *node = build_type_copy (*node);
1841   TYPE_JAVA_INTERFACE (*node) = 1;
1842
1843   return NULL_TREE;
1844 }
1845
1846 /* Handle a "com_interface" attribute; arguments as in
1847    struct attribute_spec.handler.  */
1848 static tree
1849 handle_com_interface_attribute (tree* node,
1850                                 tree name,
1851                                 tree args ATTRIBUTE_UNUSED ,
1852                                 int flags ATTRIBUTE_UNUSED ,
1853                                 bool* no_add_attrs)
1854 {
1855   static int warned;
1856
1857   *no_add_attrs = true;
1858
1859   if (DECL_P (*node)
1860       || !CLASS_TYPE_P (*node)
1861       || *node != TYPE_MAIN_VARIANT (*node))
1862     {
1863       warning ("`%s' attribute can only be applied to class definitions",
1864                IDENTIFIER_POINTER (name));
1865       return NULL_TREE;
1866     }
1867
1868   if (!warned++)
1869     warning ("`%s' is obsolete; g++ vtables are now COM-compatible by default",
1870              IDENTIFIER_POINTER (name));
1871
1872   return NULL_TREE;
1873 }
1874
1875 /* Handle an "init_priority" attribute; arguments as in
1876    struct attribute_spec.handler.  */
1877 static tree
1878 handle_init_priority_attribute (tree* node,
1879                                 tree name,
1880                                 tree args,
1881                                 int flags ATTRIBUTE_UNUSED ,
1882                                 bool* no_add_attrs)
1883 {
1884   tree initp_expr = TREE_VALUE (args);
1885   tree decl = *node;
1886   tree type = TREE_TYPE (decl);
1887   int pri;
1888
1889   STRIP_NOPS (initp_expr);
1890
1891   if (!initp_expr || TREE_CODE (initp_expr) != INTEGER_CST)
1892     {
1893       error ("requested init_priority is not an integer constant");
1894       *no_add_attrs = true;
1895       return NULL_TREE;
1896     }
1897
1898   pri = TREE_INT_CST_LOW (initp_expr);
1899
1900   type = strip_array_types (type);
1901
1902   if (decl == NULL_TREE
1903       || TREE_CODE (decl) != VAR_DECL
1904       || !TREE_STATIC (decl)
1905       || DECL_EXTERNAL (decl)
1906       || (TREE_CODE (type) != RECORD_TYPE
1907           && TREE_CODE (type) != UNION_TYPE)
1908       /* Static objects in functions are initialized the
1909          first time control passes through that
1910          function. This is not precise enough to pin down an
1911          init_priority value, so don't allow it.  */
1912       || current_function_decl)
1913     {
1914       error ("can only use `%s' attribute on file-scope definitions of objects of class type",
1915              IDENTIFIER_POINTER (name));
1916       *no_add_attrs = true;
1917       return NULL_TREE;
1918     }
1919
1920   if (pri > MAX_INIT_PRIORITY || pri <= 0)
1921     {
1922       error ("requested init_priority is out of range");
1923       *no_add_attrs = true;
1924       return NULL_TREE;
1925     }
1926
1927   /* Check for init_priorities that are reserved for
1928      language and runtime support implementations.*/
1929   if (pri <= MAX_RESERVED_INIT_PRIORITY)
1930     {
1931       warning
1932         ("requested init_priority is reserved for internal use");
1933     }
1934
1935   if (SUPPORTS_INIT_PRIORITY)
1936     {
1937       DECL_INIT_PRIORITY (decl) = pri;
1938       return NULL_TREE;
1939     }
1940   else
1941     {
1942       error ("`%s' attribute is not supported on this platform",
1943              IDENTIFIER_POINTER (name));
1944       *no_add_attrs = true;
1945       return NULL_TREE;
1946     }
1947 }
1948
1949 /* Return a new PTRMEM_CST of the indicated TYPE.  The MEMBER is the
1950    thing pointed to by the constant.  */
1951
1952 tree
1953 make_ptrmem_cst (tree type, tree member)
1954 {
1955   tree ptrmem_cst = make_node (PTRMEM_CST);
1956   /* If would seem a great convenience if make_node would set
1957      TREE_CONSTANT for things of class `c', but it does not.  */
1958   TREE_CONSTANT (ptrmem_cst) = 1;
1959   TREE_TYPE (ptrmem_cst) = type;
1960   PTRMEM_CST_MEMBER (ptrmem_cst) = member;
1961   return ptrmem_cst;
1962 }
1963
1964 /* Build a variant of TYPE that has the indicated ATTRIBUTES.  May
1965    return an existing type of an appropriate type already exists.  */
1966
1967 tree
1968 cp_build_type_attribute_variant (tree type, tree attributes)
1969 {
1970   tree new_type;
1971
1972   new_type = build_type_attribute_variant (type, attributes);
1973   if (TREE_CODE (new_type) == FUNCTION_TYPE
1974       && (TYPE_RAISES_EXCEPTIONS (new_type)
1975           != TYPE_RAISES_EXCEPTIONS (type)))
1976     new_type = build_exception_variant (new_type,
1977                                         TYPE_RAISES_EXCEPTIONS (type));
1978   return new_type;
1979 }
1980
1981 /* Apply FUNC to all language-specific sub-trees of TP in a pre-order
1982    traversal.  Called from walk_tree().  */
1983
1984 tree
1985 cp_walk_subtrees (tree* tp,
1986                   int* walk_subtrees_p,
1987                   walk_tree_fn func,
1988                   void* data,
1989                   void* htab)
1990 {
1991   enum tree_code code = TREE_CODE (*tp);
1992   tree result;
1993
1994 #define WALK_SUBTREE(NODE)                              \
1995   do                                                    \
1996     {                                                   \
1997       result = walk_tree (&(NODE), func, data, htab);   \
1998       if (result)                                       \
1999         return result;                                  \
2000     }                                                   \
2001   while (0)
2002
2003   /* Not one of the easy cases.  We must explicitly go through the
2004      children.  */
2005   switch (code)
2006     {
2007     case DEFAULT_ARG:
2008     case TEMPLATE_TEMPLATE_PARM:
2009     case BOUND_TEMPLATE_TEMPLATE_PARM:
2010     case UNBOUND_CLASS_TEMPLATE:
2011     case TEMPLATE_PARM_INDEX:
2012     case TEMPLATE_TYPE_PARM:
2013     case TYPENAME_TYPE:
2014     case TYPEOF_TYPE:
2015     case BASELINK:
2016       /* None of these have subtrees other than those already walked
2017          above.  */
2018       *walk_subtrees_p = 0;
2019       break;
2020
2021     case PTRMEM_CST:
2022       WALK_SUBTREE (TREE_TYPE (*tp));
2023       *walk_subtrees_p = 0;
2024       break;
2025
2026     case TREE_LIST:
2027       WALK_SUBTREE (TREE_PURPOSE (*tp));
2028       break;
2029
2030     case OVERLOAD:
2031       WALK_SUBTREE (OVL_FUNCTION (*tp));
2032       WALK_SUBTREE (OVL_CHAIN (*tp));
2033       *walk_subtrees_p = 0;
2034       break;
2035
2036     case RECORD_TYPE:
2037       if (TYPE_PTRMEMFUNC_P (*tp))
2038         WALK_SUBTREE (TYPE_PTRMEMFUNC_FN_TYPE (*tp));
2039       break;
2040
2041     default:
2042       break;
2043     }
2044
2045   /* We didn't find what we were looking for.  */
2046   return NULL_TREE;
2047
2048 #undef WALK_SUBTREE
2049 }
2050
2051 /* Decide whether there are language-specific reasons to not inline a
2052    function as a tree.  */
2053
2054 int
2055 cp_cannot_inline_tree_fn (tree* fnp)
2056 {
2057   tree fn = *fnp;
2058
2059   /* We can inline a template instantiation only if it's fully
2060      instantiated.  */
2061   if (DECL_TEMPLATE_INFO (fn)
2062       && TI_PENDING_TEMPLATE_FLAG (DECL_TEMPLATE_INFO (fn)))
2063     {
2064       /* Don't instantiate functions that are not going to be
2065          inlined.  */
2066       if (!DECL_INLINE (DECL_TEMPLATE_RESULT
2067                         (template_for_substitution (fn))))
2068         return 1;
2069
2070       fn = *fnp = instantiate_decl (fn, /*defer_ok=*/0);
2071
2072       if (TI_PENDING_TEMPLATE_FLAG (DECL_TEMPLATE_INFO (fn)))
2073         return 1;
2074     }
2075
2076   if (flag_really_no_inline
2077       && lookup_attribute ("always_inline", DECL_ATTRIBUTES (fn)) == NULL)
2078     return 1;
2079
2080   /* Don't auto-inline anything that might not be bound within
2081      this unit of translation.  */
2082   if (!DECL_DECLARED_INLINE_P (fn) && !(*targetm.binds_local_p) (fn))
2083     {
2084       DECL_UNINLINABLE (fn) = 1;
2085       return 1;
2086     }
2087
2088   if (varargs_function_p (fn))
2089     {
2090       DECL_UNINLINABLE (fn) = 1;
2091       return 1;
2092     }
2093
2094   if (! function_attribute_inlinable_p (fn))
2095     {
2096       DECL_UNINLINABLE (fn) = 1;
2097       return 1;
2098     }
2099
2100   return 0;
2101 }
2102
2103 /* Add any pending functions other than the current function (already
2104    handled by the caller), that thus cannot be inlined, to FNS_P, then
2105    return the latest function added to the array, PREV_FN.  */
2106
2107 tree
2108 cp_add_pending_fn_decls (void* fns_p, tree prev_fn)
2109 {
2110   varray_type *fnsp = (varray_type *)fns_p;
2111   struct saved_scope *s;
2112
2113   for (s = scope_chain; s; s = s->prev)
2114     if (s->function_decl && s->function_decl != prev_fn)
2115       {
2116         VARRAY_PUSH_TREE (*fnsp, s->function_decl);
2117         prev_fn = s->function_decl;
2118       }
2119
2120   return prev_fn;
2121 }
2122
2123 /* Determine whether a tree node is an OVERLOAD node.  Used to decide
2124    whether to copy a node or to preserve its chain when inlining a
2125    function.  */
2126
2127 int
2128 cp_is_overload_p (tree t)
2129 {
2130   return TREE_CODE (t) == OVERLOAD;
2131 }
2132
2133 /* Determine whether VAR is a declaration of an automatic variable in
2134    function FN.  */
2135
2136 int
2137 cp_auto_var_in_fn_p (tree var, tree fn)
2138 {
2139   return (DECL_P (var) && DECL_CONTEXT (var) == fn
2140           && nonstatic_local_decl_p (var));
2141 }
2142
2143 /* Tell whether a declaration is needed for the RESULT of a function
2144    FN being inlined into CALLER or if the top node of target_exprs is
2145    to be used.  */
2146
2147 tree
2148 cp_copy_res_decl_for_inlining (tree result,
2149                                tree fn,
2150                                tree caller,
2151                                void* decl_map_,
2152                                int* need_decl,
2153                                tree return_slot_addr)
2154 {
2155   splay_tree decl_map = (splay_tree)decl_map_;
2156   tree var;
2157
2158   /* If FN returns an aggregate then the caller will always pass the
2159      address of the return slot explicitly.  If we were just to
2160      create a new VAR_DECL here, then the result of this function
2161      would be copied (bitwise) into the variable initialized by the
2162      TARGET_EXPR.  That's incorrect, so we must transform any
2163      references to the RESULT into references to the target.  */
2164
2165   /* We should have an explicit return slot iff the return type is
2166      TREE_ADDRESSABLE.  See simplify_aggr_init_expr.  */
2167   if (TREE_ADDRESSABLE (TREE_TYPE (result))
2168       != (return_slot_addr != NULL_TREE))
2169     abort ();
2170
2171   *need_decl = !return_slot_addr;
2172   if (return_slot_addr)
2173     {
2174       var = build_indirect_ref (return_slot_addr, "");
2175       if (! same_type_ignoring_top_level_qualifiers_p (TREE_TYPE (var),
2176                                                        TREE_TYPE (result)))
2177         abort ();
2178     }
2179   /* Otherwise, make an appropriate copy.  */
2180   else
2181     var = copy_decl_for_inlining (result, fn, caller);
2182
2183   if (DECL_SAVED_FUNCTION_DATA (fn))
2184     {
2185       tree nrv = DECL_SAVED_FUNCTION_DATA (fn)->x_return_value;
2186       if (nrv)
2187         {
2188           /* We have a named return value; copy the name and source
2189              position so we can get reasonable debugging information, and
2190              register the return variable as its equivalent.  */
2191           if (TREE_CODE (var) == VAR_DECL
2192               /* But not if we're initializing a variable from the
2193                  enclosing function which already has its own name.  */
2194               && DECL_NAME (var) == NULL_TREE)
2195             {
2196               DECL_NAME (var) = DECL_NAME (nrv);
2197               DECL_SOURCE_LOCATION (var) = DECL_SOURCE_LOCATION (nrv);
2198               DECL_ABSTRACT_ORIGIN (var) = DECL_ORIGIN (nrv);
2199               /* Don't lose initialization info.  */
2200               DECL_INITIAL (var) = DECL_INITIAL (nrv);
2201               /* Don't forget that it needs to go in the stack.  */
2202               TREE_ADDRESSABLE (var) = TREE_ADDRESSABLE (nrv);
2203             }
2204
2205           splay_tree_insert (decl_map,
2206                              (splay_tree_key) nrv,
2207                              (splay_tree_value) var);
2208         }
2209     }
2210
2211   return var;
2212 }
2213
2214 /* Initialize tree.c.  */
2215
2216 void
2217 init_tree (void)
2218 {
2219   list_hash_table = htab_create_ggc (31, list_hash, list_hash_eq, NULL);
2220 }
2221
2222 /* Called via walk_tree.  If *TP points to a DECL_STMT for a local
2223    declaration, copies the declaration and enters it in the splay_tree
2224    pointed to by DATA (which is really a `splay_tree *').  */
2225
2226 static tree
2227 mark_local_for_remap_r (tree* tp,
2228                         int* walk_subtrees ATTRIBUTE_UNUSED ,
2229                         void* data)
2230 {
2231   tree t = *tp;
2232   splay_tree st = (splay_tree) data;
2233   tree decl;
2234
2235
2236   if (TREE_CODE (t) == DECL_STMT
2237       && nonstatic_local_decl_p (DECL_STMT_DECL (t)))
2238     decl = DECL_STMT_DECL (t);
2239   else if (TREE_CODE (t) == LABEL_STMT)
2240     decl = LABEL_STMT_LABEL (t);
2241   else if (TREE_CODE (t) == TARGET_EXPR
2242            && nonstatic_local_decl_p (TREE_OPERAND (t, 0)))
2243     decl = TREE_OPERAND (t, 0);
2244   else if (TREE_CODE (t) == CASE_LABEL)
2245     decl = CASE_LABEL_DECL (t);
2246   else
2247     decl = NULL_TREE;
2248
2249   if (decl)
2250     {
2251       tree copy;
2252
2253       /* Make a copy.  */
2254       copy = copy_decl_for_inlining (decl,
2255                                      DECL_CONTEXT (decl),
2256                                      DECL_CONTEXT (decl));
2257
2258       /* Remember the copy.  */
2259       splay_tree_insert (st,
2260                          (splay_tree_key) decl,
2261                          (splay_tree_value) copy);
2262     }
2263
2264   return NULL_TREE;
2265 }
2266
2267 /* Called via walk_tree when an expression is unsaved.  Using the
2268    splay_tree pointed to by ST (which is really a `splay_tree'),
2269    remaps all local declarations to appropriate replacements.  */
2270
2271 static tree
2272 cp_unsave_r (tree* tp,
2273              int* walk_subtrees,
2274              void* data)
2275 {
2276   splay_tree st = (splay_tree) data;
2277   splay_tree_node n;
2278
2279   /* Only a local declaration (variable or label).  */
2280   if (nonstatic_local_decl_p (*tp))
2281     {
2282       /* Lookup the declaration.  */
2283       n = splay_tree_lookup (st, (splay_tree_key) *tp);
2284
2285       /* If it's there, remap it.  */
2286       if (n)
2287         *tp = (tree) n->value;
2288     }
2289   else if (TREE_CODE (*tp) == SAVE_EXPR)
2290     remap_save_expr (tp, st, current_function_decl, walk_subtrees);
2291   else
2292     {
2293       copy_tree_r (tp, walk_subtrees, NULL);
2294
2295       /* Do whatever unsaving is required.  */
2296       unsave_expr_1 (*tp);
2297     }
2298
2299   /* Keep iterating.  */
2300   return NULL_TREE;
2301 }
2302
2303 /* Called whenever an expression needs to be unsaved.  */
2304
2305 tree
2306 cxx_unsave_expr_now (tree tp)
2307 {
2308   splay_tree st;
2309
2310   /* Create a splay-tree to map old local variable declarations to new
2311      ones.  */
2312   st = splay_tree_new (splay_tree_compare_pointers, NULL, NULL);
2313
2314   /* Walk the tree once figuring out what needs to be remapped.  */
2315   walk_tree (&tp, mark_local_for_remap_r, st, NULL);
2316
2317   /* Walk the tree again, copying, remapping, and unsaving.  */
2318   walk_tree (&tp, cp_unsave_r, st, NULL);
2319
2320   /* Clean up.  */
2321   splay_tree_delete (st);
2322
2323   return tp;
2324 }
2325
2326 /* Returns the kind of special function that DECL (a FUNCTION_DECL)
2327    is.  Note that sfk_none is zero, so this function can be used as a
2328    predicate to test whether or not DECL is a special function.  */
2329
2330 special_function_kind
2331 special_function_p (tree decl)
2332 {
2333   /* Rather than doing all this stuff with magic names, we should
2334      probably have a field of type `special_function_kind' in
2335      DECL_LANG_SPECIFIC.  */
2336   if (DECL_COPY_CONSTRUCTOR_P (decl))
2337     return sfk_copy_constructor;
2338   if (DECL_CONSTRUCTOR_P (decl))
2339     return sfk_constructor;
2340   if (DECL_OVERLOADED_OPERATOR_P (decl) == NOP_EXPR)
2341     return sfk_assignment_operator;
2342   if (DECL_MAYBE_IN_CHARGE_DESTRUCTOR_P (decl))
2343     return sfk_destructor;
2344   if (DECL_COMPLETE_DESTRUCTOR_P (decl))
2345     return sfk_complete_destructor;
2346   if (DECL_BASE_DESTRUCTOR_P (decl))
2347     return sfk_base_destructor;
2348   if (DECL_DELETING_DESTRUCTOR_P (decl))
2349     return sfk_deleting_destructor;
2350   if (DECL_CONV_FN_P (decl))
2351     return sfk_conversion;
2352
2353   return sfk_none;
2354 }
2355
2356 /* Returns true if and only if NODE is a name, i.e., a node created
2357    by the parser when processing an id-expression.  */
2358
2359 bool
2360 name_p (tree node)
2361 {
2362   if (TREE_CODE (node) == TEMPLATE_ID_EXPR)
2363     node = TREE_OPERAND (node, 0);
2364   return (/* An ordinary unqualified name.  */
2365           TREE_CODE (node) == IDENTIFIER_NODE
2366           /* A destructor name.  */
2367           || TREE_CODE (node) == BIT_NOT_EXPR
2368           /* A qualified name.  */
2369           || TREE_CODE (node) == SCOPE_REF);
2370 }
2371
2372 /* Returns nonzero if TYPE is a character type, including wchar_t.  */
2373
2374 int
2375 char_type_p (tree type)
2376 {
2377   return (same_type_p (type, char_type_node)
2378           || same_type_p (type, unsigned_char_type_node)
2379           || same_type_p (type, signed_char_type_node)
2380           || same_type_p (type, wchar_type_node));
2381 }
2382
2383 /* Returns the kind of linkage associated with the indicated DECL.  Th
2384    value returned is as specified by the language standard; it is
2385    independent of implementation details regarding template
2386    instantiation, etc.  For example, it is possible that a declaration
2387    to which this function assigns external linkage would not show up
2388    as a global symbol when you run `nm' on the resulting object file.  */
2389
2390 linkage_kind
2391 decl_linkage (tree decl)
2392 {
2393   /* This function doesn't attempt to calculate the linkage from first
2394      principles as given in [basic.link].  Instead, it makes use of
2395      the fact that we have already set TREE_PUBLIC appropriately, and
2396      then handles a few special cases.  Ideally, we would calculate
2397      linkage first, and then transform that into a concrete
2398      implementation.  */
2399
2400   /* Things that don't have names have no linkage.  */
2401   if (!DECL_NAME (decl))
2402     return lk_none;
2403
2404   /* Things that are TREE_PUBLIC have external linkage.  */
2405   if (TREE_PUBLIC (decl))
2406     return lk_external;
2407
2408   /* Some things that are not TREE_PUBLIC have external linkage, too.
2409      For example, on targets that don't have weak symbols, we make all
2410      template instantiations have internal linkage (in the object
2411      file), but the symbols should still be treated as having external
2412      linkage from the point of view of the language.  */
2413   if (DECL_LANG_SPECIFIC (decl) && DECL_COMDAT (decl))
2414     return lk_external;
2415
2416   /* Things in local scope do not have linkage, if they don't have
2417      TREE_PUBLIC set.  */
2418   if (decl_function_context (decl))
2419     return lk_none;
2420
2421   /* Everything else has internal linkage.  */
2422   return lk_internal;
2423 }
2424 \f
2425 /* EXP is an expression that we want to pre-evaluate.  Returns via INITP an
2426    expression to perform the pre-evaluation, and returns directly an
2427    expression to use the precalculated result.  */
2428
2429 tree
2430 stabilize_expr (tree exp, tree* initp)
2431 {
2432   tree init_expr;
2433
2434   if (!TREE_SIDE_EFFECTS (exp))
2435     {
2436       init_expr = NULL_TREE;
2437     }
2438   else if (!real_lvalue_p (exp)
2439            || !TYPE_NEEDS_CONSTRUCTING (TREE_TYPE (exp)))
2440     {
2441       init_expr = get_target_expr (exp);
2442       exp = TARGET_EXPR_SLOT (init_expr);
2443     }
2444   else
2445     {
2446       exp = build_unary_op (ADDR_EXPR, exp, 1);
2447       init_expr = get_target_expr (exp);
2448       exp = TARGET_EXPR_SLOT (init_expr);
2449       exp = build_indirect_ref (exp, 0);
2450     }
2451
2452   *initp = init_expr;
2453   return exp;
2454 }
2455
2456 /* Like stabilize_expr, but for a call whose args we want to
2457    pre-evaluate.  */
2458
2459 void
2460 stabilize_call (tree call, tree *initp)
2461 {
2462   tree inits = NULL_TREE;
2463   tree t;
2464
2465   if (call == error_mark_node)
2466     return;
2467
2468   if (TREE_CODE (call) != CALL_EXPR
2469       && TREE_CODE (call) != AGGR_INIT_EXPR)
2470     abort ();
2471
2472   for (t = TREE_OPERAND (call, 1); t; t = TREE_CHAIN (t))
2473     if (TREE_SIDE_EFFECTS (TREE_VALUE (t)))
2474       {
2475         tree init;
2476         TREE_VALUE (t) = stabilize_expr (TREE_VALUE (t), &init);
2477         if (!init)
2478           /* Nothing.  */;
2479         else if (inits)
2480           inits = build (COMPOUND_EXPR, void_type_node, inits, init);
2481         else
2482           inits = init;
2483       }
2484
2485   *initp = inits;
2486 }
2487
2488 /* Like stabilize_expr, but for an initialization.  If we are initializing
2489    an object of class type, we don't want to introduce an extra temporary,
2490    so we look past the TARGET_EXPR and stabilize the arguments of the call
2491    instead.  */
2492
2493 bool
2494 stabilize_init (tree init, tree *initp)
2495 {
2496   tree t = init;
2497
2498   if (t == error_mark_node)
2499     return true;
2500
2501   if (TREE_CODE (t) == INIT_EXPR
2502       && TREE_CODE (TREE_OPERAND (t, 1)) != TARGET_EXPR)
2503     TREE_OPERAND (t, 1) = stabilize_expr (TREE_OPERAND (t, 1), initp);
2504   else
2505     {
2506       if (TREE_CODE (t) == INIT_EXPR)
2507         t = TREE_OPERAND (t, 1);
2508       if (TREE_CODE (t) == TARGET_EXPR)
2509         t = TARGET_EXPR_INITIAL (t);
2510       if (TREE_CODE (t) == COMPOUND_EXPR)
2511         t = expr_last (t);
2512       if (TREE_CODE (t) == CONSTRUCTOR
2513           && CONSTRUCTOR_ELTS (t) == NULL_TREE)
2514         {
2515           /* Default-initialization.  */
2516           *initp = NULL_TREE;
2517           return true;
2518         }
2519
2520       /* If the initializer is a COND_EXPR, we can't preevaluate
2521          anything.  */
2522       if (TREE_CODE (t) == COND_EXPR)
2523         return false;
2524
2525       /* The TARGET_EXPR might be initializing via bitwise copy from
2526          another variable; leave that alone.  */
2527       if (TREE_SIDE_EFFECTS (t))
2528         stabilize_call (t, initp);
2529     }
2530
2531   return true;
2532 }
2533
2534 /* Like "fold", but should be used whenever we might be processing the
2535    body of a template.  */
2536
2537 tree
2538 fold_if_not_in_template (tree expr)
2539 {
2540   /* In the body of a template, there is never any need to call
2541      "fold".  We will call fold later when actually instantiating the
2542      template.  Integral constant expressions in templates will be
2543      evaluated via fold_non_dependent_expr, as necessary.  */
2544   return (processing_template_decl ? expr : fold (expr));
2545 }
2546
2547 \f
2548 #if defined ENABLE_TREE_CHECKING && (GCC_VERSION >= 2007)
2549 /* Complain that some language-specific thing hanging off a tree
2550    node has been accessed improperly.  */
2551
2552 void
2553 lang_check_failed (const char* file, int line, const char* function)
2554 {
2555   internal_error ("lang_* check: failed in %s, at %s:%d",
2556                   function, trim_filename (file), line);
2557 }
2558 #endif /* ENABLE_TREE_CHECKING */
2559
2560 #include "gt-cp-tree.h"