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 list of T is constructed in reverse
 575    order (pre-order, depth-first, right-to-left). You must nreverse it.
 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_BASETYPES (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 (TREE_VIA_VIRTUAL (base_binfo))
 616         {
 617           new_binfo = purpose_member (BINFO_TYPE (base_binfo),
 618                                       CLASSTYPE_VBASECLASSES (t));
 619           if (new_binfo)
 620             new_binfo = TREE_VALUE (new_binfo);
 621         }
 622
 623       if (!new_binfo)
 624         {
 625           new_binfo = make_binfo (BINFO_OFFSET (base_binfo),
 626                                   base_binfo, NULL_TREE,
 627                                   BINFO_VIRTUALS (base_binfo));
 628           prev = copy_base_binfos (new_binfo, t, prev);
 629           if (TREE_VIA_VIRTUAL (base_binfo))
 630             {
 631               CLASSTYPE_VBASECLASSES (t)
 632                 = tree_cons (BINFO_TYPE (new_binfo), new_binfo,
 633                              CLASSTYPE_VBASECLASSES (t));
 634               TREE_VIA_VIRTUAL (new_binfo) = 1;
 635               BINFO_INHERITANCE_CHAIN (new_binfo) = TYPE_BINFO (t);
 636             }
 637           else
 638             BINFO_INHERITANCE_CHAIN (new_binfo) = binfo;
 639         }
 640       TREE_VEC_ELT (binfos, ix) = new_binfo;
 641     }
 642
 643   return prev;
 644 }
 645
 646 \f
 647 /* Hashing of lists so that we don't make duplicates.
 648    The entry point is `list_hash_canon'.  */
 649
 650 /* Now here is the hash table.  When recording a list, it is added
 651    to the slot whose index is the hash code mod the table size.
 652    Note that the hash table is used for several kinds of lists.
 653    While all these live in the same table, they are completely independent,
 654    and the hash code is computed differently for each of these.  */
 655
 656 static GTY ((param_is (union tree_node))) htab_t list_hash_table;
 657
 658 struct list_proxy
 659 {
 660   tree purpose;
 661   tree value;
 662   tree chain;
 663 };
 664
 665 /* Compare ENTRY (an entry in the hash table) with DATA (a list_proxy
 666    for a node we are thinking about adding).  */
 667
 668 static int
 669 list_hash_eq (const void* entry, const void* data)
 670 {
 671   tree t = (tree) entry;
 672   struct list_proxy *proxy = (struct list_proxy *) data;
 673
 674   return (TREE_VALUE (t) == proxy->value
 675           && TREE_PURPOSE (t) == proxy->purpose
 676           && TREE_CHAIN (t) == proxy->chain);
 677 }
 678
 679 /* Compute a hash code for a list (chain of TREE_LIST nodes
 680    with goodies in the TREE_PURPOSE, TREE_VALUE, and bits of the
 681    TREE_COMMON slots), by adding the hash codes of the individual entries.  */
 682
 683 static hashval_t
 684 list_hash_pieces (tree purpose, tree value, tree chain)
 685 {
 686   hashval_t hashcode = 0;
 687
 688   if (chain)
 689     hashcode += TREE_HASH (chain);
 690
 691   if (value)
 692     hashcode += TREE_HASH (value);
 693   else
 694     hashcode += 1007;
 695   if (purpose)
 696     hashcode += TREE_HASH (purpose);
 697   else
 698     hashcode += 1009;
 699   return hashcode;
 700 }
 701
 702 /* Hash an already existing TREE_LIST.  */
 703
 704 static hashval_t
 705 list_hash (const void* p)
 706 {
 707   tree t = (tree) p;
 708   return list_hash_pieces (TREE_PURPOSE (t),
 709                            TREE_VALUE (t),
 710                            TREE_CHAIN (t));
 711 }
 712
 713 /* Given list components PURPOSE, VALUE, AND CHAIN, return the canonical
 714    object for an identical list if one already exists.  Otherwise, build a
 715    new one, and record it as the canonical object.  */
 716
 717 tree
 718 hash_tree_cons (tree purpose, tree value, tree chain)
 719 {
 720   int hashcode = 0;
 721   void **slot;
 722   struct list_proxy proxy;
 723
 724   /* Hash the list node.  */
 725   hashcode = list_hash_pieces (purpose, value, chain);
 726   /* Create a proxy for the TREE_LIST we would like to create.  We
 727      don't actually create it so as to avoid creating garbage.  */
 728   proxy.purpose = purpose;
 729   proxy.value = value;
 730   proxy.chain = chain;
 731   /* See if it is already in the table.  */
 732   slot = htab_find_slot_with_hash (list_hash_table, &proxy, hashcode,
 733                                    INSERT);
 734   /* If not, create a new node.  */
 735   if (!*slot)
 736     *slot = tree_cons (purpose, value, chain);
 737   return *slot;
 738 }
 739
 740 /* Constructor for hashed lists.  */
 741
 742 tree
 743 hash_tree_chain (tree value, tree chain)
 744 {
 745   return hash_tree_cons (NULL_TREE, value, chain);
 746 }
 747
 748 /* Similar, but used for concatenating two lists.  */
 749
 750 tree
 751 hash_chainon (tree list1, tree list2)
 752 {
 753   if (list2 == 0)
 754     return list1;
 755   if (list1 == 0)
 756     return list2;
 757   if (TREE_CHAIN (list1) == NULL_TREE)
 758     return hash_tree_chain (TREE_VALUE (list1), list2);
 759   return hash_tree_chain (TREE_VALUE (list1),
 760                           hash_chainon (TREE_CHAIN (list1), list2));
 761 }
 762 \f
 763 /* Build an association between TYPE and some parameters:
 764
 765    OFFSET is the offset added to `this' to convert it to a pointer
 766    of type `TYPE *'
 767
 768    BINFO is the base binfo to use, if we are deriving from one.  This
 769    is necessary, as we want specialized parent binfos from base
 770    classes, so that the VTABLE_NAMEs of bases are for the most derived
 771    type, instead of the simple type.
 772
 773    VTABLE is the virtual function table with which to initialize
 774    sub-objects of type TYPE.
 775
 776    VIRTUALS are the virtual functions sitting in VTABLE.  */
 777
 778 tree
 779 make_binfo (tree offset, tree binfo, tree vtable, tree virtuals)
 780 {
 781   tree new_binfo = make_tree_vec (BINFO_LANG_ELTS);
 782   tree type;
 783
 784   if (TREE_CODE (binfo) == TREE_VEC)
 785     {
 786       type = BINFO_TYPE (binfo);
 787       BINFO_DEPENDENT_BASE_P (new_binfo) = BINFO_DEPENDENT_BASE_P (binfo);
 788     }
 789   else
 790     {
 791       type = binfo;
 792       binfo = NULL_TREE;
 793       BINFO_DEPENDENT_BASE_P (new_binfo) = 1;
 794     }
 795
 796   TREE_TYPE (new_binfo) = TYPE_MAIN_VARIANT (type);
 797   BINFO_OFFSET (new_binfo) = offset;
 798   BINFO_VTABLE (new_binfo) = vtable;
 799   BINFO_VIRTUALS (new_binfo) = virtuals;
 800
 801   if (binfo && !BINFO_DEPENDENT_BASE_P (binfo)
 802       && BINFO_BASETYPES (binfo) != NULL_TREE)
 803     {
 804       BINFO_BASETYPES (new_binfo) = copy_node (BINFO_BASETYPES (binfo));
 805       /* We do not need to copy the accesses, as they are read only.  */
 806       BINFO_BASEACCESSES (new_binfo) = BINFO_BASEACCESSES (binfo);
 807     }
 808   return new_binfo;
 809 }
 810
 811 void
 812 debug_binfo (tree elem)
 813 {
 814   HOST_WIDE_INT n;
 815   tree virtuals;
 816
 817   fprintf (stderr, "type \"%s\", offset = " HOST_WIDE_INT_PRINT_DEC
 818            "\nvtable type:\n",
 819            TYPE_NAME_STRING (BINFO_TYPE (elem)),
 820            TREE_INT_CST_LOW (BINFO_OFFSET (elem)));
 821   debug_tree (BINFO_TYPE (elem));
 822   if (BINFO_VTABLE (elem))
 823     fprintf (stderr, "vtable decl \"%s\"\n",
 824              IDENTIFIER_POINTER (DECL_NAME (get_vtbl_decl_for_binfo (elem))));
 825   else
 826     fprintf (stderr, "no vtable decl yet\n");
 827   fprintf (stderr, "virtuals:\n");
 828   virtuals = BINFO_VIRTUALS (elem);
 829   n = 0;
 830
 831   while (virtuals)
 832     {
 833       tree fndecl = TREE_VALUE (virtuals);
 834       fprintf (stderr, "%s [%ld =? %ld]\n",
 835                IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (fndecl)),
 836                (long) n, (long) TREE_INT_CST_LOW (DECL_VINDEX (fndecl)));
 837       ++n;
 838       virtuals = TREE_CHAIN (virtuals);
 839     }
 840 }
 841
 842 int
 843 count_functions (tree t)
 844 {
 845   int i;
 846   if (TREE_CODE (t) == FUNCTION_DECL)
 847     return 1;
 848   else if (TREE_CODE (t) == OVERLOAD)
 849     {
 850       for (i = 0; t; t = OVL_CHAIN (t))
 851         i++;
 852       return i;
 853     }
 854
 855   abort ();
 856   return 0;
 857 }
 858
 859 int
 860 is_overloaded_fn (tree x)
 861 {
 862   /* A baselink is also considered an overloaded function.  */
 863   if (TREE_CODE (x) == OFFSET_REF)
 864     x = TREE_OPERAND (x, 1);
 865   if (BASELINK_P (x))
 866     x = BASELINK_FUNCTIONS (x);
 867   return (TREE_CODE (x) == FUNCTION_DECL
 868           || TREE_CODE (x) == TEMPLATE_ID_EXPR
 869           || DECL_FUNCTION_TEMPLATE_P (x)
 870           || TREE_CODE (x) == OVERLOAD);
 871 }
 872
 873 int
 874 really_overloaded_fn (tree x)
 875 {
 876   /* A baselink is also considered an overloaded function.  */
 877   if (TREE_CODE (x) == OFFSET_REF)
 878     x = TREE_OPERAND (x, 1);
 879   if (BASELINK_P (x))
 880     x = BASELINK_FUNCTIONS (x);
 881
 882   return ((TREE_CODE (x) == OVERLOAD && OVL_CHAIN (x))
 883           || DECL_FUNCTION_TEMPLATE_P (OVL_CURRENT (x))
 884           || TREE_CODE (x) == TEMPLATE_ID_EXPR);
 885 }
 886
 887 tree
 888 get_first_fn (tree from)
 889 {
 890   my_friendly_assert (is_overloaded_fn (from), 9);
 891   /* A baselink is also considered an overloaded function.  */
 892   if (BASELINK_P (from))
 893     from = BASELINK_FUNCTIONS (from);
 894   return OVL_CURRENT (from);
 895 }
 896
 897 /* Returns nonzero if T is a ->* or .* expression that refers to a
 898    member function.  */
 899
 900 int
 901 bound_pmf_p (tree t)
 902 {
 903   return (TREE_CODE (t) == OFFSET_REF
 904           && TYPE_PTRMEMFUNC_P (TREE_TYPE (TREE_OPERAND (t, 1))));
 905 }
 906
 907 /* Return a new OVL node, concatenating it with the old one.  */
 908
 909 tree
 910 ovl_cons (tree decl, tree chain)
 911 {
 912   tree result = make_node (OVERLOAD);
 913   TREE_TYPE (result) = unknown_type_node;
 914   OVL_FUNCTION (result) = decl;
 915   TREE_CHAIN (result) = chain;
 916
 917   return result;
 918 }
 919
 920 /* Build a new overloaded function. If this is the first one,
 921    just return it; otherwise, ovl_cons the _DECLs */
 922
 923 tree
 924 build_overload (tree decl, tree chain)
 925 {
 926   if (! chain && TREE_CODE (decl) != TEMPLATE_DECL)
 927     return decl;
 928   if (chain && TREE_CODE (chain) != OVERLOAD)
 929     chain = ovl_cons (chain, NULL_TREE);
 930   return ovl_cons (decl, chain);
 931 }
 932
 933 \f
 934 #define PRINT_RING_SIZE 4
 935
 936 const char *
 937 cxx_printable_name (tree decl, int v)
 938 {
 939   static tree decl_ring[PRINT_RING_SIZE];
 940   static char *print_ring[PRINT_RING_SIZE];
 941   static int ring_counter;
 942   int i;
 943
 944   /* Only cache functions.  */
 945   if (v < 2
 946       || TREE_CODE (decl) != FUNCTION_DECL
 947       || DECL_LANG_SPECIFIC (decl) == 0)
 948     return lang_decl_name (decl, v);
 949
 950   /* See if this print name is lying around.  */
 951   for (i = 0; i < PRINT_RING_SIZE; i++)
 952     if (decl_ring[i] == decl)
 953       /* yes, so return it.  */
 954       return print_ring[i];
 955
 956   if (++ring_counter == PRINT_RING_SIZE)
 957     ring_counter = 0;
 958
 959   if (current_function_decl != NULL_TREE)
 960     {
 961       if (decl_ring[ring_counter] == current_function_decl)
 962         ring_counter += 1;
 963       if (ring_counter == PRINT_RING_SIZE)
 964         ring_counter = 0;
 965       if (decl_ring[ring_counter] == current_function_decl)
 966         abort ();
 967     }
 968
 969   if (print_ring[ring_counter])
 970     free (print_ring[ring_counter]);
 971
 972   print_ring[ring_counter] = xstrdup (lang_decl_name (decl, v));
 973   decl_ring[ring_counter] = decl;
 974   return print_ring[ring_counter];
 975 }
 976 \f
 977 /* Build the FUNCTION_TYPE or METHOD_TYPE which may throw exceptions
 978    listed in RAISES.  */
 979
 980 tree
 981 build_exception_variant (tree type, tree raises)
 982 {
 983   tree v = TYPE_MAIN_VARIANT (type);
 984   int type_quals = TYPE_QUALS (type);
 985
 986   for (; v; v = TYPE_NEXT_VARIANT (v))
 987     if (check_qualified_type (v, type, type_quals)
 988         && comp_except_specs (raises, TYPE_RAISES_EXCEPTIONS (v), 1))
 989       return v;
 990
 991   /* Need to build a new variant.  */
 992   v = build_type_copy (type);
 993   TYPE_RAISES_EXCEPTIONS (v) = raises;
 994   return v;
 995 }
 996
 997 /* Given a TEMPLATE_TEMPLATE_PARM node T, create a new
 998    BOUND_TEMPLATE_TEMPLATE_PARM bound with NEWARGS as its template
 999    arguments.  */
1000
1001 tree
1002 bind_template_template_parm (tree t, tree newargs)
1003 {
1004   tree decl = TYPE_NAME (t);
1005   tree t2;
1006
1007   t2 = make_aggr_type (BOUND_TEMPLATE_TEMPLATE_PARM);
1008   decl = build_decl (TYPE_DECL, DECL_NAME (decl), NULL_TREE);
1009
1010   /* These nodes have to be created to reflect new TYPE_DECL and template
1011      arguments.  */
1012   TEMPLATE_TYPE_PARM_INDEX (t2) = copy_node (TEMPLATE_TYPE_PARM_INDEX (t));
1013   TEMPLATE_PARM_DECL (TEMPLATE_TYPE_PARM_INDEX (t2)) = decl;
1014   TEMPLATE_TEMPLATE_PARM_TEMPLATE_INFO (t2)
1015     = tree_cons (TEMPLATE_TEMPLATE_PARM_TEMPLATE_DECL (t),
1016                  newargs, NULL_TREE);
1017
1018   TREE_TYPE (decl) = t2;
1019   TYPE_NAME (t2) = decl;
1020   TYPE_STUB_DECL (t2) = decl;
1021   TYPE_SIZE (t2) = 0;
1022
1023   return t2;
1024 }
1025
1026 /* Called from count_trees via walk_tree.  */
1027
1028 static tree
1029 count_trees_r (tree *tp, int *walk_subtrees, void *data)
1030 {
1031   ++*((int *) data);
1032
1033   if (TYPE_P (*tp))
1034     *walk_subtrees = 0;
1035
1036   return NULL_TREE;
1037 }
1038
1039 /* Debugging function for measuring the rough complexity of a tree
1040    representation.  */
1041
1042 int
1043 count_trees (tree t)
1044 {
1045   int n_trees = 0;
1046   walk_tree_without_duplicates (&t, count_trees_r, &n_trees);
1047   return n_trees;
1048 }
1049
1050 /* Called from verify_stmt_tree via walk_tree.  */
1051
1052 static tree
1053 verify_stmt_tree_r (tree* tp,
1054                     int* walk_subtrees ATTRIBUTE_UNUSED ,
1055                     void* data)
1056 {
1057   tree t = *tp;
1058   htab_t *statements = (htab_t *) data;
1059   void **slot;
1060
1061   if (!STATEMENT_CODE_P (TREE_CODE (t)))
1062     return NULL_TREE;
1063
1064   /* If this statement is already present in the hash table, then
1065      there is a circularity in the statement tree.  */
1066   if (htab_find (*statements, t))
1067     abort ();
1068
1069   slot = htab_find_slot (*statements, t, INSERT);
1070   *slot = t;
1071
1072   return NULL_TREE;
1073 }
1074
1075 /* Debugging function to check that the statement T has not been
1076    corrupted.  For now, this function simply checks that T contains no
1077    circularities.  */
1078
1079 void
1080 verify_stmt_tree (tree t)
1081 {
1082   htab_t statements;
1083   statements = htab_create (37, htab_hash_pointer, htab_eq_pointer, NULL);
1084   walk_tree (&t, verify_stmt_tree_r, &statements, NULL);
1085   htab_delete (statements);
1086 }
1087
1088 /* Called from find_tree via walk_tree.  */
1089
1090 static tree
1091 find_tree_r (tree* tp,
1092              int* walk_subtrees ATTRIBUTE_UNUSED ,
1093              void* data)
1094 {
1095   if (*tp == (tree) data)
1096     return (tree) data;
1097
1098   return NULL_TREE;
1099 }
1100
1101 /* Returns X if X appears in the tree structure rooted at T.  */
1102
1103 tree
1104 find_tree (tree t, tree x)
1105 {
1106   return walk_tree_without_duplicates (&t, find_tree_r, x);
1107 }
1108
1109 /* Passed to walk_tree.  Checks for the use of types with no linkage.  */
1110
1111 static tree
1112 no_linkage_helper (tree *tp, int *walk_subtrees ATTRIBUTE_UNUSED,
1113                    void *data ATTRIBUTE_UNUSED)
1114 {
1115   tree t = *tp;
1116
1117   if (TYPE_P (t)
1118       && (CLASS_TYPE_P (t) || TREE_CODE (t) == ENUMERAL_TYPE)
1119       && (decl_function_context (TYPE_MAIN_DECL (t))
1120           || TYPE_ANONYMOUS_P (t)))
1121     return t;
1122
1123   return NULL_TREE;
1124 }
1125
1126 /* Check if the type T depends on a type with no linkage and if so, return
1127    it.  */
1128
1129 tree
1130 no_linkage_check (tree t)
1131 {
1132   /* There's no point in checking linkage on template functions; we
1133      can't know their complete types.  */
1134   if (processing_template_decl)
1135     return NULL_TREE;
1136
1137   t = walk_tree_without_duplicates (&t, no_linkage_helper, NULL);
1138   if (t != error_mark_node)
1139     return t;
1140   return NULL_TREE;
1141 }
1142
1143 #ifdef GATHER_STATISTICS
1144 extern int depth_reached;
1145 #endif
1146
1147 void
1148 cxx_print_statistics (void)
1149 {
1150   print_search_statistics ();
1151   print_class_statistics ();
1152 #ifdef GATHER_STATISTICS
1153   fprintf (stderr, "maximum template instantiation depth reached: %d\n",
1154            depth_reached);
1155 #endif
1156 }
1157
1158 /* Return, as an INTEGER_CST node, the number of elements for TYPE
1159    (which is an ARRAY_TYPE).  This counts only elements of the top
1160    array.  */
1161
1162 tree
1163 array_type_nelts_top (tree type)
1164 {
1165   return fold (build (PLUS_EXPR, sizetype,
1166                       array_type_nelts (type),
1167                       integer_one_node));
1168 }
1169
1170 /* Return, as an INTEGER_CST node, the number of elements for TYPE
1171    (which is an ARRAY_TYPE).  This one is a recursive count of all
1172    ARRAY_TYPEs that are clumped together.  */
1173
1174 tree
1175 array_type_nelts_total (tree type)
1176 {
1177   tree sz = array_type_nelts_top (type);
1178   type = TREE_TYPE (type);
1179   while (TREE_CODE (type) == ARRAY_TYPE)
1180     {
1181       tree n = array_type_nelts_top (type);
1182       sz = fold (build (MULT_EXPR, sizetype, sz, n));
1183       type = TREE_TYPE (type);
1184     }
1185   return sz;
1186 }
1187
1188 /* Called from break_out_target_exprs via mapcar.  */
1189
1190 static tree
1191 bot_manip (tree* tp, int* walk_subtrees, void* data)
1192 {
1193   splay_tree target_remap = ((splay_tree) data);
1194   tree t = *tp;
1195
1196   if (!TYPE_P (t) && TREE_CONSTANT (t))
1197     {
1198       /* There can't be any TARGET_EXPRs or their slot variables below
1199          this point.  We used to check !TREE_SIDE_EFFECTS, but then we
1200          failed to copy an ADDR_EXPR of the slot VAR_DECL.  */
1201       *walk_subtrees = 0;
1202       return NULL_TREE;
1203     }
1204   if (TREE_CODE (t) == TARGET_EXPR)
1205     {
1206       tree u;
1207
1208       if (TREE_CODE (TREE_OPERAND (t, 1)) == AGGR_INIT_EXPR)
1209         {
1210           mark_used (TREE_OPERAND (TREE_OPERAND (TREE_OPERAND (t, 1), 0), 0));
1211           u = build_cplus_new
1212             (TREE_TYPE (t), break_out_target_exprs (TREE_OPERAND (t, 1)));
1213         }
1214       else
1215         {
1216           u = build_target_expr_with_type
1217             (break_out_target_exprs (TREE_OPERAND (t, 1)), TREE_TYPE (t));
1218         }
1219
1220       /* Map the old variable to the new one.  */
1221       splay_tree_insert (target_remap,
1222                          (splay_tree_key) TREE_OPERAND (t, 0),
1223                          (splay_tree_value) TREE_OPERAND (u, 0));
1224
1225       /* Replace the old expression with the new version.  */
1226       *tp = u;
1227       /* We don't have to go below this point; the recursive call to
1228          break_out_target_exprs will have handled anything below this
1229          point.  */
1230       *walk_subtrees = 0;
1231       return NULL_TREE;
1232     }
1233   else if (TREE_CODE (t) == CALL_EXPR)
1234     mark_used (TREE_OPERAND (TREE_OPERAND (t, 0), 0));
1235
1236   /* Make a copy of this node.  */
1237   return copy_tree_r (tp, walk_subtrees, NULL);
1238 }
1239
1240 /* Replace all remapped VAR_DECLs in T with their new equivalents.
1241    DATA is really a splay-tree mapping old variables to new
1242    variables.  */
1243
1244 static tree
1245 bot_replace (tree* t,
1246              int* walk_subtrees ATTRIBUTE_UNUSED ,
1247              void* data)
1248 {
1249   splay_tree target_remap = ((splay_tree) data);
1250
1251   if (TREE_CODE (*t) == VAR_DECL)
1252     {
1253       splay_tree_node n = splay_tree_lookup (target_remap,
1254                                              (splay_tree_key) *t);
1255       if (n)
1256         *t = (tree) n->value;
1257     }
1258
1259   return NULL_TREE;
1260 }
1261
1262 /* When we parse a default argument expression, we may create
1263    temporary variables via TARGET_EXPRs.  When we actually use the
1264    default-argument expression, we make a copy of the expression, but
1265    we must replace the temporaries with appropriate local versions.  */
1266
1267 tree
1268 break_out_target_exprs (tree t)
1269 {
1270   static int target_remap_count;
1271   static splay_tree target_remap;
1272
1273   if (!target_remap_count++)
1274     target_remap = splay_tree_new (splay_tree_compare_pointers,
1275                                    /*splay_tree_delete_key_fn=*/NULL,
1276                                    /*splay_tree_delete_value_fn=*/NULL);
1277   walk_tree (&t, bot_manip, target_remap, NULL);
1278   walk_tree (&t, bot_replace, target_remap, NULL);
1279
1280   if (!--target_remap_count)
1281     {
1282       splay_tree_delete (target_remap);
1283       target_remap = NULL;
1284     }
1285
1286   return t;
1287 }
1288
1289 /* Similar to `build_nt', but for template definitions of dependent
1290    expressions  */
1291
1292 tree
1293 build_min_nt (enum tree_code code, ...)
1294 {
1295   tree t;
1296   int length;
1297   int i;
1298   va_list p;
1299
1300   va_start (p, code);
1301
1302   t = make_node (code);
1303   length = TREE_CODE_LENGTH (code);
1304   TREE_COMPLEXITY (t) = input_line;
1305
1306   for (i = 0; i < length; i++)
1307     {
1308       tree x = va_arg (p, tree);
1309       TREE_OPERAND (t, i) = x;
1310     }
1311
1312   va_end (p);
1313   return t;
1314 }
1315
1316 /* Similar to `build', but for template definitions.  */
1317
1318 tree
1319 build_min (enum tree_code code, tree tt, ...)
1320 {
1321   tree t;
1322   int length;
1323   int i;
1324   va_list p;
1325
1326   va_start (p, tt);
1327
1328   t = make_node (code);
1329   length = TREE_CODE_LENGTH (code);
1330   TREE_TYPE (t) = tt;
1331   TREE_COMPLEXITY (t) = input_line;
1332
1333   for (i = 0; i < length; i++)
1334     {
1335       tree x = va_arg (p, tree);
1336       TREE_OPERAND (t, i) = x;
1337       if (x && !TYPE_P (x) && TREE_SIDE_EFFECTS (x))
1338         TREE_SIDE_EFFECTS (t) = 1;
1339     }
1340
1341   va_end (p);
1342   return t;
1343 }
1344
1345 /* Similar to `build', but for template definitions of non-dependent
1346    expressions. NON_DEP is the non-dependent expression that has been
1347    built.  */
1348
1349 tree
1350 build_min_non_dep (enum tree_code code, tree non_dep, ...)
1351 {
1352   tree t;
1353   int length;
1354   int i;
1355   va_list p;
1356
1357   va_start (p, non_dep);
1358
1359   t = make_node (code);
1360   length = TREE_CODE_LENGTH (code);
1361   TREE_TYPE (t) = TREE_TYPE (non_dep);
1362   TREE_COMPLEXITY (t) = input_line;
1363   TREE_SIDE_EFFECTS (t) = TREE_SIDE_EFFECTS (non_dep);
1364
1365   for (i = 0; i < length; i++)
1366     {
1367       tree x = va_arg (p, tree);
1368       TREE_OPERAND (t, i) = x;
1369     }
1370
1371   if (code == COMPOUND_EXPR && TREE_CODE (non_dep) != COMPOUND_EXPR)
1372     /* This should not be considered a COMPOUND_EXPR, because it
1373        resolves to an overload.  */
1374     COMPOUND_EXPR_OVERLOADED (t) = 1;
1375
1376   va_end (p);
1377   return t;
1378 }
1379
1380 /* Returns an INTEGER_CST (of type `int') corresponding to I.
1381    Multiple calls with the same value of I may or may not yield the
1382    same node; therefore, callers should never modify the node
1383    returned.  */
1384
1385 static GTY(()) tree shared_int_cache[256];
1386
1387 tree
1388 build_shared_int_cst (int i)
1389 {
1390   if (i >= 256)
1391     return build_int_2 (i, 0);
1392
1393   if (!shared_int_cache[i])
1394     shared_int_cache[i] = build_int_2 (i, 0);
1395
1396   return shared_int_cache[i];
1397 }
1398
1399 tree
1400 get_type_decl (tree t)
1401 {
1402   if (TREE_CODE (t) == TYPE_DECL)
1403     return t;
1404   if (TYPE_P (t))
1405     return TYPE_STUB_DECL (t);
1406   if (t == error_mark_node)
1407     return t;
1408
1409   abort ();
1410
1411   /* Stop compiler from complaining control reaches end of non-void function.  */
1412   return 0;
1413 }
1414
1415 /* Return first vector element whose BINFO_TYPE is ELEM.
1416    Return 0 if ELEM is not in VEC.  VEC may be NULL_TREE.  */
1417
1418 tree
1419 vec_binfo_member (tree elem, tree vec)
1420 {
1421   int i;
1422
1423   if (vec)
1424     for (i = 0; i < TREE_VEC_LENGTH (vec); ++i)
1425       if (same_type_p (elem, BINFO_TYPE (TREE_VEC_ELT (vec, i))))
1426         return TREE_VEC_ELT (vec, i);
1427
1428   return NULL_TREE;
1429 }
1430
1431 /* Returns the namespace that contains DECL, whether directly or
1432    indirectly.  */
1433
1434 tree
1435 decl_namespace_context (tree decl)
1436 {
1437   while (1)
1438     {
1439       if (TREE_CODE (decl) == NAMESPACE_DECL)
1440         return decl;
1441       else if (TYPE_P (decl))
1442         decl = CP_DECL_CONTEXT (TYPE_MAIN_DECL (decl));
1443       else
1444         decl = CP_DECL_CONTEXT (decl);
1445     }
1446 }
1447
1448 /* Return truthvalue of whether T1 is the same tree structure as T2.
1449    Return 1 if they are the same. Return 0 if they are different.  */
1450
1451 bool
1452 cp_tree_equal (tree t1, tree t2)
1453 {
1454   enum tree_code code1, code2;
1455
1456   if (t1 == t2)
1457     return true;
1458   if (!t1 || !t2)
1459     return false;
1460
1461   for (code1 = TREE_CODE (t1);
1462        code1 == NOP_EXPR || code1 == CONVERT_EXPR
1463          || code1 == NON_LVALUE_EXPR;
1464        code1 = TREE_CODE (t1))
1465     t1 = TREE_OPERAND (t1, 0);
1466   for (code2 = TREE_CODE (t2);
1467        code2 == NOP_EXPR || code2 == CONVERT_EXPR
1468          || code1 == NON_LVALUE_EXPR;
1469        code2 = TREE_CODE (t2))
1470     t2 = TREE_OPERAND (t2, 0);
1471
1472   /* They might have become equal now.  */
1473   if (t1 == t2)
1474     return true;
1475
1476   if (code1 != code2)
1477     return false;
1478
1479   switch (code1)
1480     {
1481     case INTEGER_CST:
1482       return TREE_INT_CST_LOW (t1) == TREE_INT_CST_LOW (t2)
1483         && TREE_INT_CST_HIGH (t1) == TREE_INT_CST_HIGH (t2);
1484
1485     case REAL_CST:
1486       return REAL_VALUES_EQUAL (TREE_REAL_CST (t1), TREE_REAL_CST (t2));
1487
1488     case STRING_CST:
1489       return TREE_STRING_LENGTH (t1) == TREE_STRING_LENGTH (t2)
1490         && !memcmp (TREE_STRING_POINTER (t1), TREE_STRING_POINTER (t2),
1491                     TREE_STRING_LENGTH (t1));
1492
1493     case CONSTRUCTOR:
1494       /* We need to do this when determining whether or not two
1495          non-type pointer to member function template arguments
1496          are the same.  */
1497       if (!(same_type_p (TREE_TYPE (t1), TREE_TYPE (t2))
1498             /* The first operand is RTL.  */
1499             && TREE_OPERAND (t1, 0) == TREE_OPERAND (t2, 0)))
1500         return false;
1501       return cp_tree_equal (TREE_OPERAND (t1, 1), TREE_OPERAND (t2, 1));
1502
1503     case TREE_LIST:
1504       if (!cp_tree_equal (TREE_PURPOSE (t1), TREE_PURPOSE (t2)))
1505         return false;
1506       if (!cp_tree_equal (TREE_VALUE (t1), TREE_VALUE (t2)))
1507         return false;
1508       return cp_tree_equal (TREE_CHAIN (t1), TREE_CHAIN (t2));
1509
1510     case SAVE_EXPR:
1511       return cp_tree_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
1512
1513     case CALL_EXPR:
1514       if (!cp_tree_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0)))
1515         return false;
1516       return cp_tree_equal (TREE_OPERAND (t1, 1), TREE_OPERAND (t2, 1));
1517
1518     case TARGET_EXPR:
1519       {
1520         tree o1 = TREE_OPERAND (t1, 0);
1521         tree o2 = TREE_OPERAND (t2, 0);
1522
1523         /* Special case: if either target is an unallocated VAR_DECL,
1524            it means that it's going to be unified with whatever the
1525            TARGET_EXPR is really supposed to initialize, so treat it
1526            as being equivalent to anything.  */
1527         if (TREE_CODE (o1) == VAR_DECL && DECL_NAME (o1) == NULL_TREE
1528             && !DECL_RTL_SET_P (o1))
1529           /*Nop*/;
1530         else if (TREE_CODE (o2) == VAR_DECL && DECL_NAME (o2) == NULL_TREE
1531                  && !DECL_RTL_SET_P (o2))
1532           /*Nop*/;
1533         else if (!cp_tree_equal (o1, o2))
1534           return false;
1535
1536         return cp_tree_equal (TREE_OPERAND (t1, 1), TREE_OPERAND (t2, 1));
1537       }
1538
1539     case WITH_CLEANUP_EXPR:
1540       if (!cp_tree_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0)))
1541         return false;
1542       return cp_tree_equal (TREE_OPERAND (t1, 1), TREE_OPERAND (t1, 1));
1543
1544     case COMPONENT_REF:
1545       if (TREE_OPERAND (t1, 1) != TREE_OPERAND (t2, 1))
1546         return false;
1547       return cp_tree_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
1548
1549     case VAR_DECL:
1550     case PARM_DECL:
1551     case CONST_DECL:
1552     case FUNCTION_DECL:
1553     case TEMPLATE_DECL:
1554     case IDENTIFIER_NODE:
1555       return false;
1556
1557     case TEMPLATE_PARM_INDEX:
1558       return (TEMPLATE_PARM_IDX (t1) == TEMPLATE_PARM_IDX (t2)
1559               && TEMPLATE_PARM_LEVEL (t1) == TEMPLATE_PARM_LEVEL (t2)
1560               && same_type_p (TREE_TYPE (TEMPLATE_PARM_DECL (t1)),
1561                               TREE_TYPE (TEMPLATE_PARM_DECL (t2))));
1562
1563     case TEMPLATE_ID_EXPR:
1564       {
1565         unsigned ix;
1566         tree vec1, vec2;
1567
1568         if (!cp_tree_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0)))
1569           return false;
1570         vec1 = TREE_OPERAND (t1, 1);
1571         vec2 = TREE_OPERAND (t2, 1);
1572
1573         if (!vec1 || !vec2)
1574           return !vec1 && !vec2;
1575
1576         if (TREE_VEC_LENGTH (vec1) != TREE_VEC_LENGTH (vec2))
1577           return false;
1578
1579         for (ix = TREE_VEC_LENGTH (vec1); ix--;)
1580           if (!cp_tree_equal (TREE_VEC_ELT (vec1, ix),
1581                               TREE_VEC_ELT (vec2, ix)))
1582             return false;
1583
1584         return true;
1585       }
1586
1587     case SIZEOF_EXPR:
1588     case ALIGNOF_EXPR:
1589       {
1590         tree o1 = TREE_OPERAND (t1, 0);
1591         tree o2 = TREE_OPERAND (t2, 0);
1592
1593         if (TREE_CODE (o1) != TREE_CODE (o2))
1594           return false;
1595         if (TYPE_P (o1))
1596           return same_type_p (o1, o2);
1597         else
1598           return cp_tree_equal (o1, o2);
1599       }
1600
1601     case PTRMEM_CST:
1602       /* Two pointer-to-members are the same if they point to the same
1603          field or function in the same class.  */
1604       if (PTRMEM_CST_MEMBER (t1) != PTRMEM_CST_MEMBER (t2))
1605         return false;
1606
1607       return same_type_p (PTRMEM_CST_CLASS (t1), PTRMEM_CST_CLASS (t2));
1608
1609     default:
1610       break;
1611     }
1612
1613   switch (TREE_CODE_CLASS (code1))
1614     {
1615     case '1':
1616     case '2':
1617     case '<':
1618     case 'e':
1619     case 'r':
1620     case 's':
1621       {
1622         int i;
1623
1624         for (i = 0; i < TREE_CODE_LENGTH (code1); ++i)
1625           if (!cp_tree_equal (TREE_OPERAND (t1, i), TREE_OPERAND (t2, i)))
1626             return false;
1627
1628         return true;
1629       }
1630
1631     case 't':
1632       return same_type_p (t1, t2);
1633     }
1634
1635   my_friendly_assert (0, 20030617);
1636   return false;
1637 }
1638
1639 /* The type of ARG when used as an lvalue.  */
1640
1641 tree
1642 lvalue_type (tree arg)
1643 {
1644   tree type = TREE_TYPE (arg);
1645   return type;
1646 }
1647
1648 /* The type of ARG for printing error messages; denote lvalues with
1649    reference types.  */
1650
1651 tree
1652 error_type (tree arg)
1653 {
1654   tree type = TREE_TYPE (arg);
1655
1656   if (TREE_CODE (type) == ARRAY_TYPE)
1657     ;
1658   else if (TREE_CODE (type) == ERROR_MARK)
1659     ;
1660   else if (real_lvalue_p (arg))
1661     type = build_reference_type (lvalue_type (arg));
1662   else if (IS_AGGR_TYPE (type))
1663     type = lvalue_type (arg);
1664
1665   return type;
1666 }
1667
1668 /* Does FUNCTION use a variable-length argument list?  */
1669
1670 int
1671 varargs_function_p (tree function)
1672 {
1673   tree parm = TYPE_ARG_TYPES (TREE_TYPE (function));
1674   for (; parm; parm = TREE_CHAIN (parm))
1675     if (TREE_VALUE (parm) == void_type_node)
1676       return 0;
1677   return 1;
1678 }
1679
1680 /* Returns 1 if decl is a member of a class.  */
1681
1682 int
1683 member_p (tree decl)
1684 {
1685   const tree ctx = DECL_CONTEXT (decl);
1686   return (ctx && TYPE_P (ctx));
1687 }
1688
1689 /* Create a placeholder for member access where we don't actually have an
1690    object that the access is against.  */
1691
1692 tree
1693 build_dummy_object (tree type)
1694 {
1695   tree decl = build1 (NOP_EXPR, build_pointer_type (type), void_zero_node);
1696   return build_indirect_ref (decl, NULL);
1697 }
1698
1699 /* We've gotten a reference to a member of TYPE.  Return *this if appropriate,
1700    or a dummy object otherwise.  If BINFOP is non-0, it is filled with the
1701    binfo path from current_class_type to TYPE, or 0.  */
1702
1703 tree
1704 maybe_dummy_object (tree type, tree* binfop)
1705 {
1706   tree decl, context;
1707   tree binfo;
1708
1709   if (current_class_type
1710       && (binfo = lookup_base (current_class_type, type,
1711                                ba_ignore | ba_quiet, NULL)))
1712     context = current_class_type;
1713   else
1714     {
1715       /* Reference from a nested class member function.  */
1716       context = type;
1717       binfo = TYPE_BINFO (type);
1718     }
1719
1720   if (binfop)
1721     *binfop = binfo;
1722
1723   if (current_class_ref && context == current_class_type
1724       /* Kludge: Make sure that current_class_type is actually
1725          correct.  It might not be if we're in the middle of
1726          tsubst_default_argument.  */
1727       && same_type_p (TYPE_MAIN_VARIANT (TREE_TYPE (current_class_ref)),
1728                       current_class_type))
1729     decl = current_class_ref;
1730   else
1731     decl = build_dummy_object (context);
1732
1733   return decl;
1734 }
1735
1736 /* Returns 1 if OB is a placeholder object, or a pointer to one.  */
1737
1738 int
1739 is_dummy_object (tree ob)
1740 {
1741   if (TREE_CODE (ob) == INDIRECT_REF)
1742     ob = TREE_OPERAND (ob, 0);
1743   return (TREE_CODE (ob) == NOP_EXPR
1744           && TREE_OPERAND (ob, 0) == void_zero_node);
1745 }
1746
1747 /* Returns 1 iff type T is a POD type, as defined in [basic.types].  */
1748
1749 int
1750 pod_type_p (tree t)
1751 {
1752   t = strip_array_types (t);
1753
1754   if (t == error_mark_node)
1755     return 1;
1756   if (INTEGRAL_TYPE_P (t))
1757     return 1;  /* integral, character or enumeral type */
1758   if (FLOAT_TYPE_P (t))
1759     return 1;
1760   if (TYPE_PTR_P (t))
1761     return 1; /* pointer to non-member */
1762   if (TYPE_PTR_TO_MEMBER_P (t))
1763     return 1; /* pointer to member */
1764
1765   if (TREE_CODE (t) == VECTOR_TYPE)
1766     return 1; /* vectors are (small) arrays if scalars */
1767
1768   if (! CLASS_TYPE_P (t))
1769     return 0; /* other non-class type (reference or function) */
1770   if (CLASSTYPE_NON_POD_P (t))
1771     return 0;
1772   return 1;
1773 }
1774
1775 /* Returns 1 iff zero initialization of type T means actually storing
1776    zeros in it.  */
1777
1778 int
1779 zero_init_p (tree t)
1780 {
1781   t = strip_array_types (t);
1782
1783   if (t == error_mark_node)
1784     return 1;
1785
1786   /* NULL pointers to data members are initialized with -1.  */
1787   if (TYPE_PTRMEM_P (t))
1788     return 0;
1789
1790   /* Classes that contain types that can't be zero-initialized, cannot
1791      be zero-initialized themselves.  */
1792   if (CLASS_TYPE_P (t) && CLASSTYPE_NON_ZERO_INIT_P (t))
1793     return 0;
1794
1795   return 1;
1796 }
1797
1798 /* Table of valid C++ attributes.  */
1799 const struct attribute_spec cxx_attribute_table[] =
1800 {
1801   /* { name, min_len, max_len, decl_req, type_req, fn_type_req, handler } */
1802   { "java_interface", 0, 0, false, false, false, handle_java_interface_attribute },
1803   { "com_interface",  0, 0, false, false, false, handle_com_interface_attribute },
1804   { "init_priority",  1, 1, true,  false, false, handle_init_priority_attribute },
1805   { NULL,             0, 0, false, false, false, NULL }
1806 };
1807
1808 /* Handle a "java_interface" attribute; arguments as in
1809    struct attribute_spec.handler.  */
1810 static tree
1811 handle_java_interface_attribute (tree* node,
1812                                  tree name,
1813                                  tree args ATTRIBUTE_UNUSED ,
1814                                  int flags,
1815                                  bool* no_add_attrs)
1816 {
1817   if (DECL_P (*node)
1818       || !CLASS_TYPE_P (*node)
1819       || !TYPE_FOR_JAVA (*node))
1820     {
1821       error ("`%E' attribute can only be applied to Java class definitions",
1822              name);
1823       *no_add_attrs = true;
1824       return NULL_TREE;
1825     }
1826   if (!(flags & (int) ATTR_FLAG_TYPE_IN_PLACE))
1827     *node = build_type_copy (*node);
1828   TYPE_JAVA_INTERFACE (*node) = 1;
1829
1830   return NULL_TREE;
1831 }
1832
1833 /* Handle a "com_interface" attribute; arguments as in
1834    struct attribute_spec.handler.  */
1835 static tree
1836 handle_com_interface_attribute (tree* node,
1837                                 tree name,
1838                                 tree args ATTRIBUTE_UNUSED ,
1839                                 int flags ATTRIBUTE_UNUSED ,
1840                                 bool* no_add_attrs)
1841 {
1842   static int warned;
1843
1844   *no_add_attrs = true;
1845
1846   if (DECL_P (*node)
1847       || !CLASS_TYPE_P (*node)
1848       || *node != TYPE_MAIN_VARIANT (*node))
1849     {
1850       warning ("`%E' attribute can only be applied to class definitions",
1851                name);
1852       return NULL_TREE;
1853     }
1854
1855   if (!warned++)
1856     warning ("`%E' is obsolete; g++ vtables are now COM-compatible by default",
1857              name);
1858
1859   return NULL_TREE;
1860 }
1861
1862 /* Handle an "init_priority" attribute; arguments as in
1863    struct attribute_spec.handler.  */
1864 static tree
1865 handle_init_priority_attribute (tree* node,
1866                                 tree name,
1867                                 tree args,
1868                                 int flags ATTRIBUTE_UNUSED ,
1869                                 bool* no_add_attrs)
1870 {
1871   tree initp_expr = TREE_VALUE (args);
1872   tree decl = *node;
1873   tree type = TREE_TYPE (decl);
1874   int pri;
1875
1876   STRIP_NOPS (initp_expr);
1877
1878   if (!initp_expr || TREE_CODE (initp_expr) != INTEGER_CST)
1879     {
1880       error ("requested init_priority is not an integer constant");
1881       *no_add_attrs = true;
1882       return NULL_TREE;
1883     }
1884
1885   pri = TREE_INT_CST_LOW (initp_expr);
1886
1887   type = strip_array_types (type);
1888
1889   if (decl == NULL_TREE
1890       || TREE_CODE (decl) != VAR_DECL
1891       || !TREE_STATIC (decl)
1892       || DECL_EXTERNAL (decl)
1893       || (TREE_CODE (type) != RECORD_TYPE
1894           && TREE_CODE (type) != UNION_TYPE)
1895       /* Static objects in functions are initialized the
1896          first time control passes through that
1897          function. This is not precise enough to pin down an
1898          init_priority value, so don't allow it.  */
1899       || current_function_decl)
1900     {
1901       error ("can only use `%E' attribute on file-scope definitions "
1902              "of objects of class type", name);
1903       *no_add_attrs = true;
1904       return NULL_TREE;
1905     }
1906
1907   if (pri > MAX_INIT_PRIORITY || pri <= 0)
1908     {
1909       error ("requested init_priority is out of range");
1910       *no_add_attrs = true;
1911       return NULL_TREE;
1912     }
1913
1914   /* Check for init_priorities that are reserved for
1915      language and runtime support implementations.*/
1916   if (pri <= MAX_RESERVED_INIT_PRIORITY)
1917     {
1918       warning
1919         ("requested init_priority is reserved for internal use");
1920     }
1921
1922   if (SUPPORTS_INIT_PRIORITY)
1923     {
1924       DECL_INIT_PRIORITY (decl) = pri;
1925       return NULL_TREE;
1926     }
1927   else
1928     {
1929       error ("`%E' attribute is not supported on this platform", name);
1930       *no_add_attrs = true;
1931       return NULL_TREE;
1932     }
1933 }
1934
1935 /* Return a new PTRMEM_CST of the indicated TYPE.  The MEMBER is the
1936    thing pointed to by the constant.  */
1937
1938 tree
1939 make_ptrmem_cst (tree type, tree member)
1940 {
1941   tree ptrmem_cst = make_node (PTRMEM_CST);
1942   TREE_TYPE (ptrmem_cst) = type;
1943   PTRMEM_CST_MEMBER (ptrmem_cst) = member;
1944   return ptrmem_cst;
1945 }
1946
1947 /* Build a variant of TYPE that has the indicated ATTRIBUTES.  May
1948    return an existing type of an appropriate type already exists.  */
1949
1950 tree
1951 cp_build_type_attribute_variant (tree type, tree attributes)
1952 {
1953   tree new_type;
1954
1955   new_type = build_type_attribute_variant (type, attributes);
1956   if (TREE_CODE (new_type) == FUNCTION_TYPE
1957       && (TYPE_RAISES_EXCEPTIONS (new_type)
1958           != TYPE_RAISES_EXCEPTIONS (type)))
1959     new_type = build_exception_variant (new_type,
1960                                         TYPE_RAISES_EXCEPTIONS (type));
1961   return new_type;
1962 }
1963
1964 /* Apply FUNC to all language-specific sub-trees of TP in a pre-order
1965    traversal.  Called from walk_tree().  */
1966
1967 tree
1968 cp_walk_subtrees (tree* tp,
1969                   int* walk_subtrees_p,
1970                   walk_tree_fn func,
1971                   void* data,
1972                   void* htab)
1973 {
1974   enum tree_code code = TREE_CODE (*tp);
1975   location_t save_locus;
1976   tree result;
1977
1978 #define WALK_SUBTREE(NODE)                              \
1979   do                                                    \
1980     {                                                   \
1981       result = walk_tree (&(NODE), func, data, htab);   \
1982       if (result) goto out;                             \
1983     }                                                   \
1984   while (0)
1985
1986   /* Set input_location here so we get the right instantiation context
1987      if we call instantiate_decl from inlinable_function_p.  */
1988   save_locus = input_location;
1989   if (EXPR_LOCUS (*tp))
1990     input_location = *EXPR_LOCUS (*tp);
1991
1992   /* Not one of the easy cases.  We must explicitly go through the
1993      children.  */
1994   result = NULL_TREE;
1995   switch (code)
1996     {
1997     case DEFAULT_ARG:
1998     case TEMPLATE_TEMPLATE_PARM:
1999     case BOUND_TEMPLATE_TEMPLATE_PARM:
2000     case UNBOUND_CLASS_TEMPLATE:
2001     case TEMPLATE_PARM_INDEX:
2002     case TEMPLATE_TYPE_PARM:
2003     case TYPENAME_TYPE:
2004     case TYPEOF_TYPE:
2005     case BASELINK:
2006       /* None of these have subtrees other than those already walked
2007          above.  */
2008       *walk_subtrees_p = 0;
2009       break;
2010
2011     case PTRMEM_CST:
2012       WALK_SUBTREE (TREE_TYPE (*tp));
2013       *walk_subtrees_p = 0;
2014       break;
2015
2016     case TREE_LIST:
2017       WALK_SUBTREE (TREE_PURPOSE (*tp));
2018       break;
2019
2020     case OVERLOAD:
2021       WALK_SUBTREE (OVL_FUNCTION (*tp));
2022       WALK_SUBTREE (OVL_CHAIN (*tp));
2023       *walk_subtrees_p = 0;
2024       break;
2025
2026     case RECORD_TYPE:
2027       if (TYPE_PTRMEMFUNC_P (*tp))
2028         WALK_SUBTREE (TYPE_PTRMEMFUNC_FN_TYPE (*tp));
2029       break;
2030
2031     default:
2032       input_location = save_locus;
2033       return c_walk_subtrees (tp, walk_subtrees_p, func, data, htab);
2034     }
2035
2036   /* We didn't find what we were looking for.  */
2037  out:
2038   input_location = save_locus;
2039   return result;
2040
2041 #undef WALK_SUBTREE
2042 }
2043
2044 /* Decide whether there are language-specific reasons to not inline a
2045    function as a tree.  */
2046
2047 int
2048 cp_cannot_inline_tree_fn (tree* fnp)
2049 {
2050   tree fn = *fnp;
2051
2052   /* We can inline a template instantiation only if it's fully
2053      instantiated.  */
2054   if (DECL_TEMPLATE_INFO (fn)
2055       && TI_PENDING_TEMPLATE_FLAG (DECL_TEMPLATE_INFO (fn)))
2056     {
2057       /* Don't instantiate functions that are not going to be
2058          inlined.  */
2059       if (!DECL_INLINE (DECL_TEMPLATE_RESULT
2060                         (template_for_substitution (fn))))
2061         return 1;
2062
2063       fn = *fnp = instantiate_decl (fn, /*defer_ok=*/0, /*undefined_ok=*/0);
2064
2065       if (TI_PENDING_TEMPLATE_FLAG (DECL_TEMPLATE_INFO (fn)))
2066         return 1;
2067     }
2068
2069   if (flag_really_no_inline
2070       && lookup_attribute ("always_inline", DECL_ATTRIBUTES (fn)) == NULL)
2071     return 1;
2072
2073   /* Don't auto-inline anything that might not be bound within
2074      this unit of translation.
2075      Exclude comdat functions from this rule.  While they can be bound
2076      to the other unit, they all must be the same.  This is especially
2077      important so templates can inline.  */
2078   if (!DECL_DECLARED_INLINE_P (fn) && !(*targetm.binds_local_p) (fn)
2079       && !DECL_COMDAT (fn))
2080     {
2081       DECL_UNINLINABLE (fn) = 1;
2082       return 1;
2083     }
2084
2085   if (varargs_function_p (fn))
2086     {
2087       DECL_UNINLINABLE (fn) = 1;
2088       return 1;
2089     }
2090
2091   if (! function_attribute_inlinable_p (fn))
2092     {
2093       DECL_UNINLINABLE (fn) = 1;
2094       return 1;
2095     }
2096
2097   return 0;
2098 }
2099
2100 /* Add any pending functions other than the current function (already
2101    handled by the caller), that thus cannot be inlined, to FNS_P, then
2102    return the latest function added to the array, PREV_FN.  */
2103
2104 tree
2105 cp_add_pending_fn_decls (void* fns_p, tree prev_fn)
2106 {
2107   varray_type *fnsp = (varray_type *)fns_p;
2108   struct saved_scope *s;
2109
2110   for (s = scope_chain; s; s = s->prev)
2111     if (s->function_decl && s->function_decl != prev_fn)
2112       {
2113         VARRAY_PUSH_TREE (*fnsp, s->function_decl);
2114         prev_fn = s->function_decl;
2115       }
2116
2117   return prev_fn;
2118 }
2119
2120 /* Determine whether a tree node is an OVERLOAD node.  Used to decide
2121    whether to copy a node or to preserve its chain when inlining a
2122    function.  */
2123
2124 int
2125 cp_is_overload_p (tree t)
2126 {
2127   return TREE_CODE (t) == OVERLOAD;
2128 }
2129
2130 /* Determine whether VAR is a declaration of an automatic variable in
2131    function FN.  */
2132
2133 int
2134 cp_auto_var_in_fn_p (tree var, tree fn)
2135 {
2136   return (DECL_P (var) && DECL_CONTEXT (var) == fn
2137           && nonstatic_local_decl_p (var));
2138 }
2139
2140 /* Tell whether a declaration is needed for the RESULT of a function
2141    FN being inlined into CALLER or if the top node of target_exprs is
2142    to be used.  */
2143
2144 tree
2145 cp_copy_res_decl_for_inlining (tree result,
2146                                tree fn,
2147                                tree caller,
2148                                void* decl_map_ ATTRIBUTE_UNUSED,
2149                                int* need_decl,
2150                                tree return_slot_addr)
2151 {
2152   tree var;
2153
2154   /* If FN returns an aggregate then the caller will always pass the
2155      address of the return slot explicitly.  If we were just to
2156      create a new VAR_DECL here, then the result of this function
2157      would be copied (bitwise) into the variable initialized by the
2158      TARGET_EXPR.  That's incorrect, so we must transform any
2159      references to the RESULT into references to the target.  */
2160
2161   /* We should have an explicit return slot iff the return type is
2162      TREE_ADDRESSABLE.  See gimplify_aggr_init_expr.  */
2163   if (TREE_ADDRESSABLE (TREE_TYPE (result))
2164       != (return_slot_addr != NULL_TREE))
2165     abort ();
2166
2167   *need_decl = !return_slot_addr;
2168   if (return_slot_addr)
2169     {
2170       var = build_indirect_ref (return_slot_addr, "");
2171       if (! same_type_ignoring_top_level_qualifiers_p (TREE_TYPE (var),
2172                                                        TREE_TYPE (result)))
2173         abort ();
2174     }
2175   /* Otherwise, make an appropriate copy.  */
2176   else
2177     var = copy_decl_for_inlining (result, fn, caller);
2178
2179   return var;
2180 }
2181
2182 /* FN body has been duplicated.  Update language specific fields.  */
2183
2184 void
2185 cp_update_decl_after_saving (tree fn,
2186                              void* decl_map_)
2187 {
2188   splay_tree decl_map = (splay_tree)decl_map_;
2189   tree nrv = DECL_SAVED_FUNCTION_DATA (fn)->x_return_value;
2190   if (nrv)
2191     {
2192       DECL_SAVED_FUNCTION_DATA (fn)->x_return_value
2193         = (tree) splay_tree_lookup (decl_map, (splay_tree_key) nrv)->value;
2194     }
2195 }
2196 /* Initialize tree.c.  */
2197
2198 void
2199 init_tree (void)
2200 {
2201   list_hash_table = htab_create_ggc (31, list_hash, list_hash_eq, NULL);
2202 }
2203
2204 /* Called via walk_tree.  If *TP points to a DECL_STMT for a local
2205    declaration, copies the declaration and enters it in the splay_tree
2206    pointed to by DATA (which is really a `splay_tree *').  */
2207
2208 static tree
2209 mark_local_for_remap_r (tree* tp,
2210                         int* walk_subtrees ATTRIBUTE_UNUSED ,
2211                         void* data)
2212 {
2213   tree t = *tp;
2214   splay_tree st = (splay_tree) data;
2215   tree decl;
2216
2217
2218   if (TREE_CODE (t) == DECL_STMT
2219       && nonstatic_local_decl_p (DECL_STMT_DECL (t)))
2220     decl = DECL_STMT_DECL (t);
2221   else if (TREE_CODE (t) == LABEL_EXPR)
2222     decl = LABEL_EXPR_LABEL (t);
2223   else if (TREE_CODE (t) == TARGET_EXPR
2224            && nonstatic_local_decl_p (TREE_OPERAND (t, 0)))
2225     decl = TREE_OPERAND (t, 0);
2226   else if (TREE_CODE (t) == CASE_LABEL_EXPR)
2227     decl = CASE_LABEL (t);
2228   else
2229     decl = NULL_TREE;
2230
2231   if (decl)
2232     {
2233       tree copy;
2234
2235       /* Make a copy.  */
2236       copy = copy_decl_for_inlining (decl,
2237                                      DECL_CONTEXT (decl),
2238                                      DECL_CONTEXT (decl));
2239
2240       /* Remember the copy.  */
2241       splay_tree_insert (st,
2242                          (splay_tree_key) decl,
2243                          (splay_tree_value) copy);
2244     }
2245
2246   return NULL_TREE;
2247 }
2248
2249 /* Called via walk_tree when an expression is unsaved.  Using the
2250    splay_tree pointed to by ST (which is really a `splay_tree'),
2251    remaps all local declarations to appropriate replacements.  */
2252
2253 static tree
2254 cp_unsave_r (tree* tp,
2255              int* walk_subtrees,
2256              void* data)
2257 {
2258   splay_tree st = (splay_tree) data;
2259   splay_tree_node n;
2260
2261   /* Only a local declaration (variable or label).  */
2262   if (nonstatic_local_decl_p (*tp))
2263     {
2264       /* Lookup the declaration.  */
2265       n = splay_tree_lookup (st, (splay_tree_key) *tp);
2266
2267       /* If it's there, remap it.  */
2268       if (n)
2269         *tp = (tree) n->value;
2270     }
2271   else if (TREE_CODE (*tp) == SAVE_EXPR)
2272     remap_save_expr (tp, st, current_function_decl, walk_subtrees);
2273   else
2274     {
2275       copy_tree_r (tp, walk_subtrees, NULL);
2276
2277       /* Do whatever unsaving is required.  */
2278       unsave_expr_1 (*tp);
2279     }
2280
2281   /* Keep iterating.  */
2282   return NULL_TREE;
2283 }
2284
2285 /* Called whenever an expression needs to be unsaved.  */
2286
2287 tree
2288 cxx_unsave_expr_now (tree tp)
2289 {
2290   splay_tree st;
2291
2292   /* Create a splay-tree to map old local variable declarations to new
2293      ones.  */
2294   st = splay_tree_new (splay_tree_compare_pointers, NULL, NULL);
2295
2296   /* Walk the tree once figuring out what needs to be remapped.  */
2297   walk_tree (&tp, mark_local_for_remap_r, st, NULL);
2298
2299   /* Walk the tree again, copying, remapping, and unsaving.  */
2300   walk_tree (&tp, cp_unsave_r, st, NULL);
2301
2302   /* Clean up.  */
2303   splay_tree_delete (st);
2304
2305   return tp;
2306 }
2307
2308 /* Returns the kind of special function that DECL (a FUNCTION_DECL)
2309    is.  Note that sfk_none is zero, so this function can be used as a
2310    predicate to test whether or not DECL is a special function.  */
2311
2312 special_function_kind
2313 special_function_p (tree decl)
2314 {
2315   /* Rather than doing all this stuff with magic names, we should
2316      probably have a field of type `special_function_kind' in
2317      DECL_LANG_SPECIFIC.  */
2318   if (DECL_COPY_CONSTRUCTOR_P (decl))
2319     return sfk_copy_constructor;
2320   if (DECL_CONSTRUCTOR_P (decl))
2321     return sfk_constructor;
2322   if (DECL_OVERLOADED_OPERATOR_P (decl) == NOP_EXPR)
2323     return sfk_assignment_operator;
2324   if (DECL_MAYBE_IN_CHARGE_DESTRUCTOR_P (decl))
2325     return sfk_destructor;
2326   if (DECL_COMPLETE_DESTRUCTOR_P (decl))
2327     return sfk_complete_destructor;
2328   if (DECL_BASE_DESTRUCTOR_P (decl))
2329     return sfk_base_destructor;
2330   if (DECL_DELETING_DESTRUCTOR_P (decl))
2331     return sfk_deleting_destructor;
2332   if (DECL_CONV_FN_P (decl))
2333     return sfk_conversion;
2334
2335   return sfk_none;
2336 }
2337
2338 /* Returns true if and only if NODE is a name, i.e., a node created
2339    by the parser when processing an id-expression.  */
2340
2341 bool
2342 name_p (tree node)
2343 {
2344   if (TREE_CODE (node) == TEMPLATE_ID_EXPR)
2345     node = TREE_OPERAND (node, 0);
2346   return (/* An ordinary unqualified name.  */
2347           TREE_CODE (node) == IDENTIFIER_NODE
2348           /* A destructor name.  */
2349           || TREE_CODE (node) == BIT_NOT_EXPR
2350           /* A qualified name.  */
2351           || TREE_CODE (node) == SCOPE_REF);
2352 }
2353
2354 /* Returns nonzero if TYPE is a character type, including wchar_t.  */
2355
2356 int
2357 char_type_p (tree type)
2358 {
2359   return (same_type_p (type, char_type_node)
2360           || same_type_p (type, unsigned_char_type_node)
2361           || same_type_p (type, signed_char_type_node)
2362           || same_type_p (type, wchar_type_node));
2363 }
2364
2365 /* Returns the kind of linkage associated with the indicated DECL.  Th
2366    value returned is as specified by the language standard; it is
2367    independent of implementation details regarding template
2368    instantiation, etc.  For example, it is possible that a declaration
2369    to which this function assigns external linkage would not show up
2370    as a global symbol when you run `nm' on the resulting object file.  */
2371
2372 linkage_kind
2373 decl_linkage (tree decl)
2374 {
2375   /* This function doesn't attempt to calculate the linkage from first
2376      principles as given in [basic.link].  Instead, it makes use of
2377      the fact that we have already set TREE_PUBLIC appropriately, and
2378      then handles a few special cases.  Ideally, we would calculate
2379      linkage first, and then transform that into a concrete
2380      implementation.  */
2381
2382   /* Things that don't have names have no linkage.  */
2383   if (!DECL_NAME (decl))
2384     return lk_none;
2385
2386   /* Things that are TREE_PUBLIC have external linkage.  */
2387   if (TREE_PUBLIC (decl))
2388     return lk_external;
2389
2390   /* Some things that are not TREE_PUBLIC have external linkage, too.
2391      For example, on targets that don't have weak symbols, we make all
2392      template instantiations have internal linkage (in the object
2393      file), but the symbols should still be treated as having external
2394      linkage from the point of view of the language.  */
2395   if (DECL_LANG_SPECIFIC (decl) && DECL_COMDAT (decl))
2396     return lk_external;
2397
2398   /* Things in local scope do not have linkage, if they don't have
2399      TREE_PUBLIC set.  */
2400   if (decl_function_context (decl))
2401     return lk_none;
2402
2403   /* Everything else has internal linkage.  */
2404   return lk_internal;
2405 }
2406 \f
2407 /* EXP is an expression that we want to pre-evaluate.  Returns via INITP an
2408    expression to perform the pre-evaluation, and returns directly an
2409    expression to use the precalculated result.  */
2410
2411 tree
2412 stabilize_expr (tree exp, tree* initp)
2413 {
2414   tree init_expr;
2415
2416   if (!TREE_SIDE_EFFECTS (exp))
2417     {
2418       init_expr = NULL_TREE;
2419     }
2420   else if (!real_lvalue_p (exp)
2421            || !TYPE_NEEDS_CONSTRUCTING (TREE_TYPE (exp)))
2422     {
2423       init_expr = get_target_expr (exp);
2424       exp = TARGET_EXPR_SLOT (init_expr);
2425     }
2426   else
2427     {
2428       exp = build_unary_op (ADDR_EXPR, exp, 1);
2429       init_expr = get_target_expr (exp);
2430       exp = TARGET_EXPR_SLOT (init_expr);
2431       exp = build_indirect_ref (exp, 0);
2432     }
2433
2434   *initp = init_expr;
2435   return exp;
2436 }
2437
2438 /* Like stabilize_expr, but for a call whose args we want to
2439    pre-evaluate.  */
2440
2441 void
2442 stabilize_call (tree call, tree *initp)
2443 {
2444   tree inits = NULL_TREE;
2445   tree t;
2446
2447   if (call == error_mark_node)
2448     return;
2449
2450   if (TREE_CODE (call) != CALL_EXPR
2451       && TREE_CODE (call) != AGGR_INIT_EXPR)
2452     abort ();
2453
2454   for (t = TREE_OPERAND (call, 1); t; t = TREE_CHAIN (t))
2455     if (TREE_SIDE_EFFECTS (TREE_VALUE (t)))
2456       {
2457         tree init;
2458         TREE_VALUE (t) = stabilize_expr (TREE_VALUE (t), &init);
2459         if (!init)
2460           /* Nothing.  */;
2461         else if (inits)
2462           inits = build (COMPOUND_EXPR, void_type_node, inits, init);
2463         else
2464           inits = init;
2465       }
2466
2467   *initp = inits;
2468 }
2469
2470 /* Like stabilize_expr, but for an initialization.  If we are initializing
2471    an object of class type, we don't want to introduce an extra temporary,
2472    so we look past the TARGET_EXPR and stabilize the arguments of the call
2473    instead.  */
2474
2475 bool
2476 stabilize_init (tree init, tree *initp)
2477 {
2478   tree t = init;
2479
2480   if (t == error_mark_node)
2481     return true;
2482
2483   if (TREE_CODE (t) == INIT_EXPR
2484       && TREE_CODE (TREE_OPERAND (t, 1)) != TARGET_EXPR)
2485     TREE_OPERAND (t, 1) = stabilize_expr (TREE_OPERAND (t, 1), initp);
2486   else
2487     {
2488       if (TREE_CODE (t) == INIT_EXPR)
2489         t = TREE_OPERAND (t, 1);
2490       if (TREE_CODE (t) == TARGET_EXPR)
2491         t = TARGET_EXPR_INITIAL (t);
2492       if (TREE_CODE (t) == CONSTRUCTOR
2493           && CONSTRUCTOR_ELTS (t) == NULL_TREE)
2494         {
2495           /* Default-initialization.  */
2496           *initp = NULL_TREE;
2497           return true;
2498         }
2499
2500       /* If the initializer is a COND_EXPR, we can't preevaluate
2501          anything.  */
2502       if (TREE_CODE (t) == COND_EXPR)
2503         return false;
2504
2505       stabilize_call (t, initp);
2506     }
2507
2508   return true;
2509 }
2510
2511 \f
2512 #if defined ENABLE_TREE_CHECKING && (GCC_VERSION >= 2007)
2513 /* Complain that some language-specific thing hanging off a tree
2514    node has been accessed improperly.  */
2515
2516 void
2517 lang_check_failed (const char* file, int line, const char* function)
2518 {
2519   internal_error ("lang_* check: failed in %s, at %s:%d",
2520                   function, trim_filename (file), line);
2521 }
2522 #endif /* ENABLE_TREE_CHECKING */
2523
2524 #include "gt-cp-tree.h"