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       if (!op1_lvalue_kind
  94           /* The "field" can be a FUNCTION_DECL or an OVERLOAD in some
  95              situations.  */
  96           || TREE_CODE (TREE_OPERAND (ref, 1)) != FIELD_DECL)
  97         ;
  98       else if (DECL_C_BIT_FIELD (TREE_OPERAND (ref, 1)))
  99         {
 100           /* Clear the ordinary bit.  If this object was a class
 101              rvalue we want to preserve that information.  */
 102           op1_lvalue_kind &= ~clk_ordinary;
 103           /* The lvalue is for a bitfield.  */
 104           op1_lvalue_kind |= clk_bitfield;
 105         }
 106       else if (DECL_PACKED (TREE_OPERAND (ref, 1)))
 107         op1_lvalue_kind |= clk_packed;
 108
 109       return op1_lvalue_kind;
 110
 111     case STRING_CST:
 112       return clk_ordinary;
 113
 114     case VAR_DECL:
 115       if (TREE_READONLY (ref) && ! TREE_STATIC (ref)
 116           && DECL_LANG_SPECIFIC (ref)
 117           && DECL_IN_AGGR_P (ref))
 118         return clk_none;
 119     case INDIRECT_REF:
 120     case ARRAY_REF:
 121     case PARM_DECL:
 122     case RESULT_DECL:
 123       if (TREE_CODE (TREE_TYPE (ref)) != METHOD_TYPE)
 124         return clk_ordinary;
 125       break;
 126
 127       /* A currently unresolved scope ref.  */
 128     case SCOPE_REF:
 129       abort ();
 130     case MAX_EXPR:
 131     case MIN_EXPR:
 132       op1_lvalue_kind = lvalue_p_1 (TREE_OPERAND (ref, 0),
 133                                     treat_class_rvalues_as_lvalues);
 134       op2_lvalue_kind = lvalue_p_1 (TREE_OPERAND (ref, 1),
 135                                     treat_class_rvalues_as_lvalues);
 136       break;
 137
 138     case COND_EXPR:
 139       op1_lvalue_kind = lvalue_p_1 (TREE_OPERAND (ref, 1),
 140                                     treat_class_rvalues_as_lvalues);
 141       op2_lvalue_kind = lvalue_p_1 (TREE_OPERAND (ref, 2),
 142                                     treat_class_rvalues_as_lvalues);
 143       break;
 144
 145     case MODIFY_EXPR:
 146       return clk_ordinary;
 147
 148     case COMPOUND_EXPR:
 149       return lvalue_p_1 (TREE_OPERAND (ref, 1),
 150                          treat_class_rvalues_as_lvalues);
 151
 152     case TARGET_EXPR:
 153       return treat_class_rvalues_as_lvalues ? clk_class : clk_none;
 154
 155     case CALL_EXPR:
 156     case VA_ARG_EXPR:
 157       /* Any class-valued call would be wrapped in a TARGET_EXPR.  */
 158       return clk_none;
 159
 160     case FUNCTION_DECL:
 161       /* All functions (except non-static-member functions) are
 162          lvalues.  */
 163       return (DECL_NONSTATIC_MEMBER_FUNCTION_P (ref)
 164               ? clk_none : clk_ordinary);
 165
 166     case NON_DEPENDENT_EXPR:
 167       /* We must consider NON_DEPENDENT_EXPRs to be lvalues so that
 168          things like "&E" where "E" is an expression with a
 169          non-dependent type work. It is safe to be lenient because an
 170          error will be issued when the template is instantiated if "E"
 171          is not an lvalue.  */
 172       return clk_ordinary;
 173
 174     default:
 175       break;
 176     }
 177
 178   /* If one operand is not an lvalue at all, then this expression is
 179      not an lvalue.  */
 180   if (!op1_lvalue_kind || !op2_lvalue_kind)
 181     return clk_none;
 182
 183   /* Otherwise, it's an lvalue, and it has all the odd properties
 184      contributed by either operand.  */
 185   op1_lvalue_kind = op1_lvalue_kind | op2_lvalue_kind;
 186   /* It's not an ordinary lvalue if it involves either a bit-field or
 187      a class rvalue.  */
 188   if ((op1_lvalue_kind & ~clk_ordinary) != clk_none)
 189     op1_lvalue_kind &= ~clk_ordinary;
 190   return op1_lvalue_kind;
 191 }
 192
 193 /* Returns the kind of lvalue that REF is, in the sense of
 194    [basic.lval].  This function should really be named lvalue_p; it
 195    computes the C++ definition of lvalue.  */
 196
 197 cp_lvalue_kind
 198 real_lvalue_p (tree ref)
 199 {
 200   return lvalue_p_1 (ref,
 201                      /*treat_class_rvalues_as_lvalues=*/0);
 202 }
 203
 204 /* This differs from real_lvalue_p in that class rvalues are
 205    considered lvalues.  */
 206
 207 int
 208 lvalue_p (tree ref)
 209 {
 210   return
 211     (lvalue_p_1 (ref, /*class rvalue ok*/ 1) != clk_none);
 212 }
 213
 214 /* Return nonzero if REF is an lvalue valid for this language;
 215    otherwise, print an error message and return zero.  */
 216
 217 int
 218 lvalue_or_else (tree ref, const char* string)
 219 {
 220   if (!lvalue_p (ref))
 221     {
 222       error ("non-lvalue in %s", string);
 223       return 0;
 224     }
 225   return 1;
 226 }
 227
 228 /* Build a TARGET_EXPR, initializing the DECL with the VALUE.  */
 229
 230 static tree
 231 build_target_expr (tree decl, tree value)
 232 {
 233   tree t;
 234
 235   t = build (TARGET_EXPR, TREE_TYPE (decl), decl, value,
 236              cxx_maybe_build_cleanup (decl), NULL_TREE);
 237   /* We always set TREE_SIDE_EFFECTS so that expand_expr does not
 238      ignore the TARGET_EXPR.  If there really turn out to be no
 239      side-effects, then the optimizer should be able to get rid of
 240      whatever code is generated anyhow.  */
 241   TREE_SIDE_EFFECTS (t) = 1;
 242
 243   return t;
 244 }
 245
 246 /* Return an undeclared local temporary of type TYPE for use in building a
 247    TARGET_EXPR.  */
 248
 249 static tree
 250 build_local_temp (tree type)
 251 {
 252   tree slot = build_decl (VAR_DECL, NULL_TREE, type);
 253   DECL_ARTIFICIAL (slot) = 1;
 254   DECL_CONTEXT (slot) = current_function_decl;
 255   layout_decl (slot, 0);
 256   return slot;
 257 }
 258
 259 /* INIT is a CALL_EXPR which needs info about its target.
 260    TYPE is the type that this initialization should appear to have.
 261
 262    Build an encapsulation of the initialization to perform
 263    and return it so that it can be processed by language-independent
 264    and language-specific expression expanders.  */
 265
 266 tree
 267 build_cplus_new (tree type, tree init)
 268 {
 269   tree fn;
 270   tree slot;
 271   tree rval;
 272   int is_ctor;
 273
 274   /* Make sure that we're not trying to create an instance of an
 275      abstract class.  */
 276   abstract_virtuals_error (NULL_TREE, type);
 277
 278   if (TREE_CODE (init) != CALL_EXPR && TREE_CODE (init) != AGGR_INIT_EXPR)
 279     return convert (type, init);
 280
 281   fn = TREE_OPERAND (init, 0);
 282   is_ctor = (TREE_CODE (fn) == ADDR_EXPR
 283              && TREE_CODE (TREE_OPERAND (fn, 0)) == FUNCTION_DECL
 284              && DECL_CONSTRUCTOR_P (TREE_OPERAND (fn, 0)));
 285
 286   slot = build_local_temp (type);
 287
 288   /* We split the CALL_EXPR into its function and its arguments here.
 289      Then, in expand_expr, we put them back together.  The reason for
 290      this is that this expression might be a default argument
 291      expression.  In that case, we need a new temporary every time the
 292      expression is used.  That's what break_out_target_exprs does; it
 293      replaces every AGGR_INIT_EXPR with a copy that uses a fresh
 294      temporary slot.  Then, expand_expr builds up a call-expression
 295      using the new slot.  */
 296
 297   /* If we don't need to use a constructor to create an object of this
 298      type, don't mess with AGGR_INIT_EXPR.  */
 299   if (is_ctor || TREE_ADDRESSABLE (type))
 300     {
 301       rval = build (AGGR_INIT_EXPR, type, fn, TREE_OPERAND (init, 1), slot);
 302       TREE_SIDE_EFFECTS (rval) = 1;
 303       AGGR_INIT_VIA_CTOR_P (rval) = is_ctor;
 304     }
 305   else
 306     rval = init;
 307
 308   rval = build_target_expr (slot, rval);
 309
 310   return rval;
 311 }
 312
 313 /* Build a TARGET_EXPR using INIT to initialize a new temporary of the
 314    indicated TYPE.  */
 315
 316 tree
 317 build_target_expr_with_type (tree init, tree type)
 318 {
 319   tree slot;
 320
 321   if (TREE_CODE (init) == TARGET_EXPR)
 322     return init;
 323   else if (CLASS_TYPE_P (type) && !TYPE_HAS_TRIVIAL_INIT_REF (type)
 324            && TREE_CODE (init) != COND_EXPR
 325            && TREE_CODE (init) != CONSTRUCTOR
 326            && TREE_CODE (init) != VA_ARG_EXPR)
 327     /* We need to build up a copy constructor call.  COND_EXPR is a special
 328        case because we already have copies on the arms and we don't want
 329        another one here.  A CONSTRUCTOR is aggregate initialization, which
 330        is handled separately.  A VA_ARG_EXPR is magic creation of an
 331        aggregate; there's no additional work to be done.  */
 332     return force_rvalue (init);
 333
 334   slot = build_local_temp (type);
 335   return build_target_expr (slot, init);
 336 }
 337
 338 /* Like the above function, but without the checking.  This function should
 339    only be used by code which is deliberately trying to subvert the type
 340    system, such as call_builtin_trap.  */
 341
 342 tree
 343 force_target_expr (tree type, tree init)
 344 {
 345   tree slot = build_local_temp (type);
 346   return build_target_expr (slot, init);
 347 }
 348
 349 /* Like build_target_expr_with_type, but use the type of INIT.  */
 350
 351 tree
 352 get_target_expr (tree init)
 353 {
 354   return build_target_expr_with_type (init, TREE_TYPE (init));
 355 }
 356
 357 \f
 358 static tree
 359 build_cplus_array_type_1 (tree elt_type, tree index_type)
 360 {
 361   tree t;
 362
 363   if (elt_type == error_mark_node || index_type == error_mark_node)
 364     return error_mark_node;
 365
 366   if (dependent_type_p (elt_type)
 367       || (index_type
 368           && value_dependent_expression_p (TYPE_MAX_VALUE (index_type))))
 369     {
 370       t = make_node (ARRAY_TYPE);
 371       TREE_TYPE (t) = elt_type;
 372       TYPE_DOMAIN (t) = index_type;
 373     }
 374   else
 375     t = build_array_type (elt_type, index_type);
 376
 377   /* Push these needs up so that initialization takes place
 378      more easily.  */
 379   TYPE_NEEDS_CONSTRUCTING (t)
 380     = TYPE_NEEDS_CONSTRUCTING (TYPE_MAIN_VARIANT (elt_type));
 381   TYPE_HAS_NONTRIVIAL_DESTRUCTOR (t)
 382     = TYPE_HAS_NONTRIVIAL_DESTRUCTOR (TYPE_MAIN_VARIANT (elt_type));
 383   return t;
 384 }
 385
 386 tree
 387 build_cplus_array_type (tree elt_type, tree index_type)
 388 {
 389   tree t;
 390   int type_quals = cp_type_quals (elt_type);
 391
 392   if (type_quals != TYPE_UNQUALIFIED)
 393     elt_type = cp_build_qualified_type (elt_type, TYPE_UNQUALIFIED);
 394
 395   t = build_cplus_array_type_1 (elt_type, index_type);
 396
 397   if (type_quals != TYPE_UNQUALIFIED)
 398     t = cp_build_qualified_type (t, type_quals);
 399
 400   return t;
 401 }
 402 \f
 403 /* Make a variant of TYPE, qualified with the TYPE_QUALS.  Handles
 404    arrays correctly.  In particular, if TYPE is an array of T's, and
 405    TYPE_QUALS is non-empty, returns an array of qualified T's.
 406
 407    FLAGS determines how to deal with illformed qualifications. If
 408    tf_ignore_bad_quals is set, then bad qualifications are dropped
 409    (this is permitted if TYPE was introduced via a typedef or template
 410    type parameter). If bad qualifications are dropped and tf_warning
 411    is set, then a warning is issued for non-const qualifications.  If
 412    tf_ignore_bad_quals is not set and tf_error is not set, we
 413    return error_mark_node. Otherwise, we issue an error, and ignore
 414    the qualifications.
 415
 416    Qualification of a reference type is valid when the reference came
 417    via a typedef or template type argument. [dcl.ref] No such
 418    dispensation is provided for qualifying a function type.  [dcl.fct]
 419    DR 295 queries this and the proposed resolution brings it into line
 420    with qualifying a reference.  We implement the DR.  We also behave
 421    in a similar manner for restricting non-pointer types.  */
 422
 423 tree
 424 cp_build_qualified_type_real (tree type,
 425                               int type_quals,
 426                               tsubst_flags_t complain)
 427 {
 428   tree result;
 429   int bad_quals = TYPE_UNQUALIFIED;
 430   /* We keep bad function qualifiers separate, so that we can decide
 431      whether to implement DR 295 or not. DR 295 break existing code,
 432      unfortunately. Remove this variable to implement the defect
 433      report.  */
 434   int bad_func_quals = TYPE_UNQUALIFIED;
 435
 436   if (type == error_mark_node)
 437     return type;
 438
 439   if (type_quals == cp_type_quals (type))
 440     return type;
 441
 442   if (TREE_CODE (type) == ARRAY_TYPE)
 443     {
 444       /* In C++, the qualification really applies to the array element
 445          type.  Obtain the appropriately qualified element type.  */
 446       tree t;
 447       tree element_type
 448         = cp_build_qualified_type_real (TREE_TYPE (type),
 449                                         type_quals,
 450                                         complain);
 451
 452       if (element_type == error_mark_node)
 453         return error_mark_node;
 454
 455       /* See if we already have an identically qualified type.  */
 456       for (t = TYPE_MAIN_VARIANT (type); t; t = TYPE_NEXT_VARIANT (t))
 457         if (cp_type_quals (t) == type_quals
 458             && TYPE_NAME (t) == TYPE_NAME (type)
 459             && TYPE_CONTEXT (t) == TYPE_CONTEXT (type))
 460           break;
 461
 462       if (!t)
 463         {
 464           /* Make a new array type, just like the old one, but with the
 465              appropriately qualified element type.  */
 466           t = build_type_copy (type);
 467           TREE_TYPE (t) = element_type;
 468         }
 469
 470       /* Even if we already had this variant, we update
 471          TYPE_NEEDS_CONSTRUCTING and TYPE_HAS_NONTRIVIAL_DESTRUCTOR in case
 472          they changed since the variant was originally created.
 473
 474          This seems hokey; if there is some way to use a previous
 475          variant *without* coming through here,
 476          TYPE_NEEDS_CONSTRUCTING will never be updated.  */
 477       TYPE_NEEDS_CONSTRUCTING (t)
 478         = TYPE_NEEDS_CONSTRUCTING (TYPE_MAIN_VARIANT (element_type));
 479       TYPE_HAS_NONTRIVIAL_DESTRUCTOR (t)
 480         = TYPE_HAS_NONTRIVIAL_DESTRUCTOR (TYPE_MAIN_VARIANT (element_type));
 481       return t;
 482     }
 483   else if (TYPE_PTRMEMFUNC_P (type))
 484     {
 485       /* For a pointer-to-member type, we can't just return a
 486          cv-qualified version of the RECORD_TYPE.  If we do, we
 487          haven't changed the field that contains the actual pointer to
 488          a method, and so TYPE_PTRMEMFUNC_FN_TYPE will be wrong.  */
 489       tree t;
 490
 491       t = TYPE_PTRMEMFUNC_FN_TYPE (type);
 492       t = cp_build_qualified_type_real (t, type_quals, complain);
 493       return build_ptrmemfunc_type (t);
 494     }
 495
 496   /* A reference, function or method type shall not be cv qualified.
 497      [dcl.ref], [dct.fct]  */
 498   if (type_quals & (TYPE_QUAL_CONST | TYPE_QUAL_VOLATILE)
 499       && (TREE_CODE (type) == REFERENCE_TYPE
 500           || TREE_CODE (type) == FUNCTION_TYPE
 501           || TREE_CODE (type) == METHOD_TYPE))
 502     {
 503       bad_quals |= type_quals & (TYPE_QUAL_CONST | TYPE_QUAL_VOLATILE);
 504       if (TREE_CODE (type) != REFERENCE_TYPE)
 505         bad_func_quals |= type_quals & (TYPE_QUAL_CONST | TYPE_QUAL_VOLATILE);
 506       type_quals &= ~(TYPE_QUAL_CONST | TYPE_QUAL_VOLATILE);
 507     }
 508
 509   /* A restrict-qualified type must be a pointer (or reference)
 510      to object or incomplete type.  */
 511   if ((type_quals & TYPE_QUAL_RESTRICT)
 512       && TREE_CODE (type) != TEMPLATE_TYPE_PARM
 513       && TREE_CODE (type) != TYPENAME_TYPE
 514       && !POINTER_TYPE_P (type))
 515     {
 516       bad_quals |= TYPE_QUAL_RESTRICT;
 517       type_quals &= ~TYPE_QUAL_RESTRICT;
 518     }
 519
 520   if (bad_quals == TYPE_UNQUALIFIED)
 521     /*OK*/;
 522   else if (!(complain & (tf_error | tf_ignore_bad_quals)))
 523     return error_mark_node;
 524   else if (bad_func_quals && !(complain & tf_error))
 525     return error_mark_node;
 526   else
 527     {
 528       if (complain & tf_ignore_bad_quals)
 529         /* We're not going to warn about constifying things that can't
 530            be constified.  */
 531         bad_quals &= ~TYPE_QUAL_CONST;
 532       bad_quals |= bad_func_quals;
 533       if (bad_quals)
 534         {
 535           tree bad_type = build_qualified_type (ptr_type_node, bad_quals);
 536
 537           if (!(complain & tf_ignore_bad_quals)
 538               || bad_func_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 += TYPE_HASH (chain);
 690
 691   if (value)
 692     hashcode += TYPE_HASH (value);
 693   else
 694     hashcode += 1007;
 695   if (purpose)
 696     hashcode += TYPE_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 (TYPE_QUALS (v) == 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 ATTRIBUTE_UNUSED ,
1030                int* walk_subtrees ATTRIBUTE_UNUSED ,
1031                void* data)
1032 {
1033   ++ *((int*) data);
1034   return NULL_TREE;
1035 }
1036
1037 /* Debugging function for measuring the rough complexity of a tree
1038    representation.  */
1039
1040 int
1041 count_trees (tree t)
1042 {
1043   int n_trees = 0;
1044   walk_tree_without_duplicates (&t, count_trees_r, &n_trees);
1045   return n_trees;
1046 }
1047
1048 /* Called from verify_stmt_tree via walk_tree.  */
1049
1050 static tree
1051 verify_stmt_tree_r (tree* tp,
1052                     int* walk_subtrees ATTRIBUTE_UNUSED ,
1053                     void* data)
1054 {
1055   tree t = *tp;
1056   htab_t *statements = (htab_t *) data;
1057   void **slot;
1058
1059   if (!STATEMENT_CODE_P (TREE_CODE (t)))
1060     return NULL_TREE;
1061
1062   /* If this statement is already present in the hash table, then
1063      there is a circularity in the statement tree.  */
1064   if (htab_find (*statements, t))
1065     abort ();
1066
1067   slot = htab_find_slot (*statements, t, INSERT);
1068   *slot = t;
1069
1070   return NULL_TREE;
1071 }
1072
1073 /* Debugging function to check that the statement T has not been
1074    corrupted.  For now, this function simply checks that T contains no
1075    circularities.  */
1076
1077 void
1078 verify_stmt_tree (tree t)
1079 {
1080   htab_t statements;
1081   statements = htab_create (37, htab_hash_pointer, htab_eq_pointer, NULL);
1082   walk_tree (&t, verify_stmt_tree_r, &statements, NULL);
1083   htab_delete (statements);
1084 }
1085
1086 /* Called from find_tree via walk_tree.  */
1087
1088 static tree
1089 find_tree_r (tree* tp,
1090              int* walk_subtrees ATTRIBUTE_UNUSED ,
1091              void* data)
1092 {
1093   if (*tp == (tree) data)
1094     return (tree) data;
1095
1096   return NULL_TREE;
1097 }
1098
1099 /* Returns X if X appears in the tree structure rooted at T.  */
1100
1101 tree
1102 find_tree (tree t, tree x)
1103 {
1104   return walk_tree_without_duplicates (&t, find_tree_r, x);
1105 }
1106
1107 /* Passed to walk_tree.  Checks for the use of types with no linkage.  */
1108
1109 static tree
1110 no_linkage_helper (tree* tp,
1111                    int* walk_subtrees ATTRIBUTE_UNUSED ,
1112                    void* data ATTRIBUTE_UNUSED )
1113 {
1114   tree t = *tp;
1115
1116   if (TYPE_P (t)
1117       && (CLASS_TYPE_P (t) || TREE_CODE (t) == ENUMERAL_TYPE)
1118       && (decl_function_context (TYPE_MAIN_DECL (t))
1119           || TYPE_ANONYMOUS_P (t)))
1120     return t;
1121   return NULL_TREE;
1122 }
1123
1124 /* Check if the type T depends on a type with no linkage and if so, return
1125    it.  */
1126
1127 tree
1128 no_linkage_check (tree t)
1129 {
1130   /* There's no point in checking linkage on template functions; we
1131      can't know their complete types.  */
1132   if (processing_template_decl)
1133     return NULL_TREE;
1134
1135   t = walk_tree_without_duplicates (&t, no_linkage_helper, NULL);
1136   if (t != error_mark_node)
1137     return t;
1138   return NULL_TREE;
1139 }
1140
1141 #ifdef GATHER_STATISTICS
1142 extern int depth_reached;
1143 #endif
1144
1145 void
1146 cxx_print_statistics (void)
1147 {
1148   print_search_statistics ();
1149   print_class_statistics ();
1150 #ifdef GATHER_STATISTICS
1151   fprintf (stderr, "maximum template instantiation depth reached: %d\n",
1152            depth_reached);
1153 #endif
1154 }
1155
1156 /* Return, as an INTEGER_CST node, the number of elements for TYPE
1157    (which is an ARRAY_TYPE).  This counts only elements of the top
1158    array.  */
1159
1160 tree
1161 array_type_nelts_top (tree type)
1162 {
1163   return fold (build (PLUS_EXPR, sizetype,
1164                       array_type_nelts (type),
1165                       integer_one_node));
1166 }
1167
1168 /* Return, as an INTEGER_CST node, the number of elements for TYPE
1169    (which is an ARRAY_TYPE).  This one is a recursive count of all
1170    ARRAY_TYPEs that are clumped together.  */
1171
1172 tree
1173 array_type_nelts_total (tree type)
1174 {
1175   tree sz = array_type_nelts_top (type);
1176   type = TREE_TYPE (type);
1177   while (TREE_CODE (type) == ARRAY_TYPE)
1178     {
1179       tree n = array_type_nelts_top (type);
1180       sz = fold (build (MULT_EXPR, sizetype, sz, n));
1181       type = TREE_TYPE (type);
1182     }
1183   return sz;
1184 }
1185
1186 /* Called from break_out_target_exprs via mapcar.  */
1187
1188 static tree
1189 bot_manip (tree* tp, int* walk_subtrees, void* data)
1190 {
1191   splay_tree target_remap = ((splay_tree) data);
1192   tree t = *tp;
1193
1194   if (TREE_CONSTANT (t))
1195     {
1196       /* There can't be any TARGET_EXPRs or their slot variables below
1197          this point.  We used to check !TREE_SIDE_EFFECTS, but then we
1198          failed to copy an ADDR_EXPR of the slot VAR_DECL.  */
1199       *walk_subtrees = 0;
1200       return NULL_TREE;
1201     }
1202   if (TREE_CODE (t) == TARGET_EXPR)
1203     {
1204       tree u;
1205
1206       if (TREE_CODE (TREE_OPERAND (t, 1)) == AGGR_INIT_EXPR)
1207         {
1208           mark_used (TREE_OPERAND (TREE_OPERAND (TREE_OPERAND (t, 1), 0), 0));
1209           u = build_cplus_new
1210             (TREE_TYPE (t), break_out_target_exprs (TREE_OPERAND (t, 1)));
1211         }
1212       else
1213         {
1214           u = build_target_expr_with_type
1215             (break_out_target_exprs (TREE_OPERAND (t, 1)), TREE_TYPE (t));
1216         }
1217
1218       /* Map the old variable to the new one.  */
1219       splay_tree_insert (target_remap,
1220                          (splay_tree_key) TREE_OPERAND (t, 0),
1221                          (splay_tree_value) TREE_OPERAND (u, 0));
1222
1223       /* Replace the old expression with the new version.  */
1224       *tp = u;
1225       /* We don't have to go below this point; the recursive call to
1226          break_out_target_exprs will have handled anything below this
1227          point.  */
1228       *walk_subtrees = 0;
1229       return NULL_TREE;
1230     }
1231   else if (TREE_CODE (t) == CALL_EXPR)
1232     mark_used (TREE_OPERAND (TREE_OPERAND (t, 0), 0));
1233
1234   /* Make a copy of this node.  */
1235   return copy_tree_r (tp, walk_subtrees, NULL);
1236 }
1237
1238 /* Replace all remapped VAR_DECLs in T with their new equivalents.
1239    DATA is really a splay-tree mapping old variables to new
1240    variables.  */
1241
1242 static tree
1243 bot_replace (tree* t,
1244              int* walk_subtrees ATTRIBUTE_UNUSED ,
1245              void* data)
1246 {
1247   splay_tree target_remap = ((splay_tree) data);
1248
1249   if (TREE_CODE (*t) == VAR_DECL)
1250     {
1251       splay_tree_node n = splay_tree_lookup (target_remap,
1252                                              (splay_tree_key) *t);
1253       if (n)
1254         *t = (tree) n->value;
1255     }
1256
1257   return NULL_TREE;
1258 }
1259
1260 /* When we parse a default argument expression, we may create
1261    temporary variables via TARGET_EXPRs.  When we actually use the
1262    default-argument expression, we make a copy of the expression, but
1263    we must replace the temporaries with appropriate local versions.  */
1264
1265 tree
1266 break_out_target_exprs (tree t)
1267 {
1268   static int target_remap_count;
1269   static splay_tree target_remap;
1270
1271   if (!target_remap_count++)
1272     target_remap = splay_tree_new (splay_tree_compare_pointers,
1273                                    /*splay_tree_delete_key_fn=*/NULL,
1274                                    /*splay_tree_delete_value_fn=*/NULL);
1275   walk_tree (&t, bot_manip, target_remap, NULL);
1276   walk_tree (&t, bot_replace, target_remap, NULL);
1277
1278   if (!--target_remap_count)
1279     {
1280       splay_tree_delete (target_remap);
1281       target_remap = NULL;
1282     }
1283
1284   return t;
1285 }
1286
1287 /* Similar to `build_nt', but for template definitions of dependent
1288    expressions  */
1289
1290 tree
1291 build_min_nt (enum tree_code code, ...)
1292 {
1293   tree t;
1294   int length;
1295   int i;
1296   va_list p;
1297
1298   va_start (p, code);
1299
1300   t = make_node (code);
1301   length = TREE_CODE_LENGTH (code);
1302   TREE_COMPLEXITY (t) = input_line;
1303
1304   for (i = 0; i < length; i++)
1305     {
1306       tree x = va_arg (p, tree);
1307       TREE_OPERAND (t, i) = x;
1308     }
1309
1310   va_end (p);
1311   return t;
1312 }
1313
1314 /* Similar to `build', but for template definitions.  */
1315
1316 tree
1317 build_min (enum tree_code code, tree tt, ...)
1318 {
1319   tree t;
1320   int length;
1321   int i;
1322   va_list p;
1323
1324   va_start (p, tt);
1325
1326   t = make_node (code);
1327   length = TREE_CODE_LENGTH (code);
1328   TREE_TYPE (t) = tt;
1329   TREE_COMPLEXITY (t) = input_line;
1330
1331   for (i = 0; i < length; i++)
1332     {
1333       tree x = va_arg (p, tree);
1334       TREE_OPERAND (t, i) = x;
1335       if (x && TREE_SIDE_EFFECTS (x))
1336         TREE_SIDE_EFFECTS (t) = 1;
1337     }
1338
1339   va_end (p);
1340   return t;
1341 }
1342
1343 /* Similar to `build', but for template definitions of non-dependent
1344    expressions. NON_DEP is the non-dependent expression that has been
1345    built.  */
1346
1347 tree
1348 build_min_non_dep (enum tree_code code, tree non_dep, ...)
1349 {
1350   tree t;
1351   int length;
1352   int i;
1353   va_list p;
1354
1355   va_start (p, non_dep);
1356
1357   t = make_node (code);
1358   length = TREE_CODE_LENGTH (code);
1359   TREE_TYPE (t) = TREE_TYPE (non_dep);
1360   TREE_COMPLEXITY (t) = input_line;
1361   TREE_SIDE_EFFECTS (t) = TREE_SIDE_EFFECTS (non_dep);
1362
1363   for (i = 0; i < length; i++)
1364     {
1365       tree x = va_arg (p, tree);
1366       TREE_OPERAND (t, i) = x;
1367     }
1368
1369   if (code == COMPOUND_EXPR && TREE_CODE (non_dep) != COMPOUND_EXPR)
1370     /* This should not be considered a COMPOUND_EXPR, because it
1371        resolves to an overload.  */
1372     COMPOUND_EXPR_OVERLOADED (t) = 1;
1373
1374   va_end (p);
1375   return t;
1376 }
1377
1378 /* Returns an INTEGER_CST (of type `int') corresponding to I.
1379    Multiple calls with the same value of I may or may not yield the
1380    same node; therefore, callers should never modify the node
1381    returned.  */
1382
1383 static GTY(()) tree shared_int_cache[256];
1384
1385 tree
1386 build_shared_int_cst (int i)
1387 {
1388   if (i >= 256)
1389     return build_int_2 (i, 0);
1390
1391   if (!shared_int_cache[i])
1392     shared_int_cache[i] = build_int_2 (i, 0);
1393
1394   return shared_int_cache[i];
1395 }
1396
1397 tree
1398 get_type_decl (tree t)
1399 {
1400   if (TREE_CODE (t) == TYPE_DECL)
1401     return t;
1402   if (TYPE_P (t))
1403     return TYPE_STUB_DECL (t);
1404   if (t == error_mark_node)
1405     return t;
1406
1407   abort ();
1408
1409   /* Stop compiler from complaining control reaches end of non-void function.  */
1410   return 0;
1411 }
1412
1413 /* Return first vector element whose BINFO_TYPE is ELEM.
1414    Return 0 if ELEM is not in VEC.  VEC may be NULL_TREE.  */
1415
1416 tree
1417 vec_binfo_member (tree elem, tree vec)
1418 {
1419   int i;
1420
1421   if (vec)
1422     for (i = 0; i < TREE_VEC_LENGTH (vec); ++i)
1423       if (same_type_p (elem, BINFO_TYPE (TREE_VEC_ELT (vec, i))))
1424         return TREE_VEC_ELT (vec, i);
1425
1426   return NULL_TREE;
1427 }
1428
1429 /* Returns the namespace that contains DECL, whether directly or
1430    indirectly.  */
1431
1432 tree
1433 decl_namespace_context (tree decl)
1434 {
1435   while (1)
1436     {
1437       if (TREE_CODE (decl) == NAMESPACE_DECL)
1438         return decl;
1439       else if (TYPE_P (decl))
1440         decl = CP_DECL_CONTEXT (TYPE_MAIN_DECL (decl));
1441       else
1442         decl = CP_DECL_CONTEXT (decl);
1443     }
1444 }
1445
1446 /* Return truthvalue of whether T1 is the same tree structure as T2.
1447    Return 1 if they are the same. Return 0 if they are different.  */
1448
1449 bool
1450 cp_tree_equal (tree t1, tree t2)
1451 {
1452   enum tree_code code1, code2;
1453
1454   if (t1 == t2)
1455     return true;
1456   if (!t1 || !t2)
1457     return false;
1458
1459   for (code1 = TREE_CODE (t1);
1460        code1 == NOP_EXPR || code1 == CONVERT_EXPR
1461          || code1 == NON_LVALUE_EXPR;
1462        code1 = TREE_CODE (t1))
1463     t1 = TREE_OPERAND (t1, 0);
1464   for (code2 = TREE_CODE (t2);
1465        code2 == NOP_EXPR || code2 == CONVERT_EXPR
1466          || code1 == NON_LVALUE_EXPR;
1467        code2 = TREE_CODE (t2))
1468     t2 = TREE_OPERAND (t2, 0);
1469
1470   /* They might have become equal now.  */
1471   if (t1 == t2)
1472     return true;
1473
1474   if (code1 != code2)
1475     return false;
1476
1477   switch (code1)
1478     {
1479     case INTEGER_CST:
1480       return TREE_INT_CST_LOW (t1) == TREE_INT_CST_LOW (t2)
1481         && TREE_INT_CST_HIGH (t1) == TREE_INT_CST_HIGH (t2);
1482
1483     case REAL_CST:
1484       return REAL_VALUES_EQUAL (TREE_REAL_CST (t1), TREE_REAL_CST (t2));
1485
1486     case STRING_CST:
1487       return TREE_STRING_LENGTH (t1) == TREE_STRING_LENGTH (t2)
1488         && !memcmp (TREE_STRING_POINTER (t1), TREE_STRING_POINTER (t2),
1489                     TREE_STRING_LENGTH (t1));
1490
1491     case CONSTRUCTOR:
1492       /* We need to do this when determining whether or not two
1493          non-type pointer to member function template arguments
1494          are the same.  */
1495       if (!(same_type_p (TREE_TYPE (t1), TREE_TYPE (t2))
1496             /* The first operand is RTL.  */
1497             && TREE_OPERAND (t1, 0) == TREE_OPERAND (t2, 0)))
1498         return false;
1499       return cp_tree_equal (TREE_OPERAND (t1, 1), TREE_OPERAND (t2, 1));
1500
1501     case TREE_LIST:
1502       if (!cp_tree_equal (TREE_PURPOSE (t1), TREE_PURPOSE (t2)))
1503         return false;
1504       if (!cp_tree_equal (TREE_VALUE (t1), TREE_VALUE (t2)))
1505         return false;
1506       return cp_tree_equal (TREE_CHAIN (t1), TREE_CHAIN (t2));
1507
1508     case SAVE_EXPR:
1509       return cp_tree_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
1510
1511     case CALL_EXPR:
1512       if (!cp_tree_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0)))
1513         return false;
1514       return cp_tree_equal (TREE_OPERAND (t1, 1), TREE_OPERAND (t2, 1));
1515
1516     case TARGET_EXPR:
1517       {
1518         tree o1 = TREE_OPERAND (t1, 0);
1519         tree o2 = TREE_OPERAND (t2, 0);
1520
1521         /* Special case: if either target is an unallocated VAR_DECL,
1522            it means that it's going to be unified with whatever the
1523            TARGET_EXPR is really supposed to initialize, so treat it
1524            as being equivalent to anything.  */
1525         if (TREE_CODE (o1) == VAR_DECL && DECL_NAME (o1) == NULL_TREE
1526             && !DECL_RTL_SET_P (o1))
1527           /*Nop*/;
1528         else if (TREE_CODE (o2) == VAR_DECL && DECL_NAME (o2) == NULL_TREE
1529                  && !DECL_RTL_SET_P (o2))
1530           /*Nop*/;
1531         else if (!cp_tree_equal (o1, o2))
1532           return false;
1533
1534         return cp_tree_equal (TREE_OPERAND (t1, 1), TREE_OPERAND (t2, 1));
1535       }
1536
1537     case WITH_CLEANUP_EXPR:
1538       if (!cp_tree_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0)))
1539         return false;
1540       return cp_tree_equal (TREE_OPERAND (t1, 1), TREE_OPERAND (t1, 1));
1541
1542     case COMPONENT_REF:
1543       if (TREE_OPERAND (t1, 1) != TREE_OPERAND (t2, 1))
1544         return false;
1545       return cp_tree_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
1546
1547     case VAR_DECL:
1548     case PARM_DECL:
1549     case CONST_DECL:
1550     case FUNCTION_DECL:
1551     case TEMPLATE_DECL:
1552     case IDENTIFIER_NODE:
1553       return false;
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     default:
1608       break;
1609     }
1610
1611   switch (TREE_CODE_CLASS (code1))
1612     {
1613     case '1':
1614     case '2':
1615     case '<':
1616     case 'e':
1617     case 'r':
1618     case 's':
1619       {
1620         int i;
1621
1622         for (i = 0; i < TREE_CODE_LENGTH (code1); ++i)
1623           if (!cp_tree_equal (TREE_OPERAND (t1, i), TREE_OPERAND (t2, i)))
1624             return false;
1625
1626         return true;
1627       }
1628
1629     case 't':
1630       return same_type_p (t1, t2);
1631     }
1632
1633   my_friendly_assert (0, 20030617);
1634   return false;
1635 }
1636
1637 /* Build a wrapper around a 'struct z_candidate' so we can use it as a
1638    tree.  */
1639
1640 tree
1641 build_zc_wrapper (struct z_candidate* ptr)
1642 {
1643   tree t = make_node (WRAPPER);
1644   WRAPPER_ZC (t) = ptr;
1645   return t;
1646 }
1647
1648 /* The type of ARG when used as an lvalue.  */
1649
1650 tree
1651 lvalue_type (tree arg)
1652 {
1653   tree type = TREE_TYPE (arg);
1654   if (TREE_CODE (arg) == OVERLOAD)
1655     type = unknown_type_node;
1656   return type;
1657 }
1658
1659 /* The type of ARG for printing error messages; denote lvalues with
1660    reference types.  */
1661
1662 tree
1663 error_type (tree arg)
1664 {
1665   tree type = TREE_TYPE (arg);
1666
1667   if (TREE_CODE (type) == ARRAY_TYPE)
1668     ;
1669   else if (TREE_CODE (type) == ERROR_MARK)
1670     ;
1671   else if (real_lvalue_p (arg))
1672     type = build_reference_type (lvalue_type (arg));
1673   else if (IS_AGGR_TYPE (type))
1674     type = lvalue_type (arg);
1675
1676   return type;
1677 }
1678
1679 /* Does FUNCTION use a variable-length argument list?  */
1680
1681 int
1682 varargs_function_p (tree function)
1683 {
1684   tree parm = TYPE_ARG_TYPES (TREE_TYPE (function));
1685   for (; parm; parm = TREE_CHAIN (parm))
1686     if (TREE_VALUE (parm) == void_type_node)
1687       return 0;
1688   return 1;
1689 }
1690
1691 /* Returns 1 if decl is a member of a class.  */
1692
1693 int
1694 member_p (tree decl)
1695 {
1696   const tree ctx = DECL_CONTEXT (decl);
1697   return (ctx && TYPE_P (ctx));
1698 }
1699
1700 /* Create a placeholder for member access where we don't actually have an
1701    object that the access is against.  */
1702
1703 tree
1704 build_dummy_object (tree type)
1705 {
1706   tree decl = build1 (NOP_EXPR, build_pointer_type (type), void_zero_node);
1707   return build_indirect_ref (decl, NULL);
1708 }
1709
1710 /* We've gotten a reference to a member of TYPE.  Return *this if appropriate,
1711    or a dummy object otherwise.  If BINFOP is non-0, it is filled with the
1712    binfo path from current_class_type to TYPE, or 0.  */
1713
1714 tree
1715 maybe_dummy_object (tree type, tree* binfop)
1716 {
1717   tree decl, context;
1718   tree binfo;
1719
1720   if (current_class_type
1721       && (binfo = lookup_base (current_class_type, type,
1722                                ba_ignore | ba_quiet, NULL)))
1723     context = current_class_type;
1724   else
1725     {
1726       /* Reference from a nested class member function.  */
1727       context = type;
1728       binfo = TYPE_BINFO (type);
1729     }
1730
1731   if (binfop)
1732     *binfop = binfo;
1733
1734   if (current_class_ref && context == current_class_type
1735       /* Kludge: Make sure that current_class_type is actually
1736          correct.  It might not be if we're in the middle of
1737          tsubst_default_argument.  */
1738       && same_type_p (TYPE_MAIN_VARIANT (TREE_TYPE (current_class_ref)),
1739                       current_class_type))
1740     decl = current_class_ref;
1741   else
1742     decl = build_dummy_object (context);
1743
1744   return decl;
1745 }
1746
1747 /* Returns 1 if OB is a placeholder object, or a pointer to one.  */
1748
1749 int
1750 is_dummy_object (tree ob)
1751 {
1752   if (TREE_CODE (ob) == INDIRECT_REF)
1753     ob = TREE_OPERAND (ob, 0);
1754   return (TREE_CODE (ob) == NOP_EXPR
1755           && TREE_OPERAND (ob, 0) == void_zero_node);
1756 }
1757
1758 /* Returns 1 iff type T is a POD type, as defined in [basic.types].  */
1759
1760 int
1761 pod_type_p (tree t)
1762 {
1763   t = strip_array_types (t);
1764
1765   if (t == error_mark_node)
1766     return 1;
1767   if (INTEGRAL_TYPE_P (t))
1768     return 1;  /* integral, character or enumeral type */
1769   if (FLOAT_TYPE_P (t))
1770     return 1;
1771   if (TYPE_PTR_P (t))
1772     return 1; /* pointer to non-member */
1773   if (TYPE_PTR_TO_MEMBER_P (t))
1774     return 1; /* pointer to member */
1775
1776   if (! CLASS_TYPE_P (t))
1777     return 0; /* other non-class type (reference or function) */
1778   if (CLASSTYPE_NON_POD_P (t))
1779     return 0;
1780   return 1;
1781 }
1782
1783 /* Returns 1 iff zero initialization of type T means actually storing
1784    zeros in it.  */
1785
1786 int
1787 zero_init_p (tree t)
1788 {
1789   t = strip_array_types (t);
1790
1791   if (t == error_mark_node)
1792     return 1;
1793
1794   /* NULL pointers to data members are initialized with -1.  */
1795   if (TYPE_PTRMEM_P (t))
1796     return 0;
1797
1798   /* Classes that contain types that can't be zero-initialized, cannot
1799      be zero-initialized themselves.  */
1800   if (CLASS_TYPE_P (t) && CLASSTYPE_NON_ZERO_INIT_P (t))
1801     return 0;
1802
1803   return 1;
1804 }
1805
1806 /* Table of valid C++ attributes.  */
1807 const struct attribute_spec cxx_attribute_table[] =
1808 {
1809   /* { name, min_len, max_len, decl_req, type_req, fn_type_req, handler } */
1810   { "java_interface", 0, 0, false, false, false, handle_java_interface_attribute },
1811   { "com_interface",  0, 0, false, false, false, handle_com_interface_attribute },
1812   { "init_priority",  1, 1, true,  false, false, handle_init_priority_attribute },
1813   { NULL,             0, 0, false, false, false, NULL }
1814 };
1815
1816 /* Handle a "java_interface" attribute; arguments as in
1817    struct attribute_spec.handler.  */
1818 static tree
1819 handle_java_interface_attribute (tree* node,
1820                                  tree name,
1821                                  tree args ATTRIBUTE_UNUSED ,
1822                                  int flags,
1823                                  bool* no_add_attrs)
1824 {
1825   if (DECL_P (*node)
1826       || !CLASS_TYPE_P (*node)
1827       || !TYPE_FOR_JAVA (*node))
1828     {
1829       error ("`%s' attribute can only be applied to Java class definitions",
1830              IDENTIFIER_POINTER (name));
1831       *no_add_attrs = true;
1832       return NULL_TREE;
1833     }
1834   if (!(flags & (int) ATTR_FLAG_TYPE_IN_PLACE))
1835     *node = build_type_copy (*node);
1836   TYPE_JAVA_INTERFACE (*node) = 1;
1837
1838   return NULL_TREE;
1839 }
1840
1841 /* Handle a "com_interface" attribute; arguments as in
1842    struct attribute_spec.handler.  */
1843 static tree
1844 handle_com_interface_attribute (tree* node,
1845                                 tree name,
1846                                 tree args ATTRIBUTE_UNUSED ,
1847                                 int flags ATTRIBUTE_UNUSED ,
1848                                 bool* no_add_attrs)
1849 {
1850   static int warned;
1851
1852   *no_add_attrs = true;
1853
1854   if (DECL_P (*node)
1855       || !CLASS_TYPE_P (*node)
1856       || *node != TYPE_MAIN_VARIANT (*node))
1857     {
1858       warning ("`%s' attribute can only be applied to class definitions",
1859                IDENTIFIER_POINTER (name));
1860       return NULL_TREE;
1861     }
1862
1863   if (!warned++)
1864     warning ("`%s' is obsolete; g++ vtables are now COM-compatible by default",
1865              IDENTIFIER_POINTER (name));
1866
1867   return NULL_TREE;
1868 }
1869
1870 /* Handle an "init_priority" attribute; arguments as in
1871    struct attribute_spec.handler.  */
1872 static tree
1873 handle_init_priority_attribute (tree* node,
1874                                 tree name,
1875                                 tree args,
1876                                 int flags ATTRIBUTE_UNUSED ,
1877                                 bool* no_add_attrs)
1878 {
1879   tree initp_expr = TREE_VALUE (args);
1880   tree decl = *node;
1881   tree type = TREE_TYPE (decl);
1882   int pri;
1883
1884   STRIP_NOPS (initp_expr);
1885
1886   if (!initp_expr || TREE_CODE (initp_expr) != INTEGER_CST)
1887     {
1888       error ("requested init_priority is not an integer constant");
1889       *no_add_attrs = true;
1890       return NULL_TREE;
1891     }
1892
1893   pri = TREE_INT_CST_LOW (initp_expr);
1894
1895   type = strip_array_types (type);
1896
1897   if (decl == NULL_TREE
1898       || TREE_CODE (decl) != VAR_DECL
1899       || !TREE_STATIC (decl)
1900       || DECL_EXTERNAL (decl)
1901       || (TREE_CODE (type) != RECORD_TYPE
1902           && TREE_CODE (type) != UNION_TYPE)
1903       /* Static objects in functions are initialized the
1904          first time control passes through that
1905          function. This is not precise enough to pin down an
1906          init_priority value, so don't allow it.  */
1907       || current_function_decl)
1908     {
1909       error ("can only use `%s' attribute on file-scope definitions of objects of class type",
1910              IDENTIFIER_POINTER (name));
1911       *no_add_attrs = true;
1912       return NULL_TREE;
1913     }
1914
1915   if (pri > MAX_INIT_PRIORITY || pri <= 0)
1916     {
1917       error ("requested init_priority is out of range");
1918       *no_add_attrs = true;
1919       return NULL_TREE;
1920     }
1921
1922   /* Check for init_priorities that are reserved for
1923      language and runtime support implementations.*/
1924   if (pri <= MAX_RESERVED_INIT_PRIORITY)
1925     {
1926       warning
1927         ("requested init_priority is reserved for internal use");
1928     }
1929
1930   if (SUPPORTS_INIT_PRIORITY)
1931     {
1932       DECL_INIT_PRIORITY (decl) = pri;
1933       return NULL_TREE;
1934     }
1935   else
1936     {
1937       error ("`%s' attribute is not supported on this platform",
1938              IDENTIFIER_POINTER (name));
1939       *no_add_attrs = true;
1940       return NULL_TREE;
1941     }
1942 }
1943
1944 /* Return a new PTRMEM_CST of the indicated TYPE.  The MEMBER is the
1945    thing pointed to by the constant.  */
1946
1947 tree
1948 make_ptrmem_cst (tree type, tree member)
1949 {
1950   tree ptrmem_cst = make_node (PTRMEM_CST);
1951   /* If would seem a great convenience if make_node would set
1952      TREE_CONSTANT for things of class `c', but it does not.  */
1953   TREE_CONSTANT (ptrmem_cst) = 1;
1954   TREE_TYPE (ptrmem_cst) = type;
1955   PTRMEM_CST_MEMBER (ptrmem_cst) = member;
1956   return ptrmem_cst;
1957 }
1958
1959 /* Apply FUNC to all language-specific sub-trees of TP in a pre-order
1960    traversal.  Called from walk_tree().  */
1961
1962 tree
1963 cp_walk_subtrees (tree* tp,
1964                   int* walk_subtrees_p,
1965                   walk_tree_fn func,
1966                   void* data,
1967                   void* htab)
1968 {
1969   enum tree_code code = TREE_CODE (*tp);
1970   tree result;
1971
1972 #define WALK_SUBTREE(NODE)                              \
1973   do                                                    \
1974     {                                                   \
1975       result = walk_tree (&(NODE), func, data, htab);   \
1976       if (result)                                       \
1977         return result;                                  \
1978     }                                                   \
1979   while (0)
1980
1981   /* Not one of the easy cases.  We must explicitly go through the
1982      children.  */
1983   switch (code)
1984     {
1985     case DEFAULT_ARG:
1986     case TEMPLATE_TEMPLATE_PARM:
1987     case BOUND_TEMPLATE_TEMPLATE_PARM:
1988     case UNBOUND_CLASS_TEMPLATE:
1989     case TEMPLATE_PARM_INDEX:
1990     case TEMPLATE_TYPE_PARM:
1991     case TYPENAME_TYPE:
1992     case TYPEOF_TYPE:
1993     case BASELINK:
1994       /* None of these have subtrees other than those already walked
1995          above.  */
1996       *walk_subtrees_p = 0;
1997       break;
1998
1999     case PTRMEM_CST:
2000       WALK_SUBTREE (TREE_TYPE (*tp));
2001       *walk_subtrees_p = 0;
2002       break;
2003
2004     case TREE_LIST:
2005       WALK_SUBTREE (TREE_PURPOSE (*tp));
2006       break;
2007
2008     case OVERLOAD:
2009       WALK_SUBTREE (OVL_FUNCTION (*tp));
2010       WALK_SUBTREE (OVL_CHAIN (*tp));
2011       *walk_subtrees_p = 0;
2012       break;
2013
2014     case RECORD_TYPE:
2015       if (TYPE_PTRMEMFUNC_P (*tp))
2016         WALK_SUBTREE (TYPE_PTRMEMFUNC_FN_TYPE (*tp));
2017       break;
2018
2019     default:
2020       break;
2021     }
2022
2023   /* We didn't find what we were looking for.  */
2024   return NULL_TREE;
2025
2026 #undef WALK_SUBTREE
2027 }
2028
2029 /* Decide whether there are language-specific reasons to not inline a
2030    function as a tree.  */
2031
2032 int
2033 cp_cannot_inline_tree_fn (tree* fnp)
2034 {
2035   tree fn = *fnp;
2036
2037   /* We can inline a template instantiation only if it's fully
2038      instantiated.  */
2039   if (DECL_TEMPLATE_INFO (fn)
2040       && TI_PENDING_TEMPLATE_FLAG (DECL_TEMPLATE_INFO (fn)))
2041     {
2042       /* Don't instantiate functions that are not going to be
2043          inlined.  */
2044       if (!DECL_INLINE (DECL_TEMPLATE_RESULT
2045                         (template_for_substitution (fn))))
2046         return 1;
2047
2048       fn = *fnp = instantiate_decl (fn, /*defer_ok=*/0);
2049
2050       if (TI_PENDING_TEMPLATE_FLAG (DECL_TEMPLATE_INFO (fn)))
2051         return 1;
2052     }
2053
2054   if (flag_really_no_inline
2055       && lookup_attribute ("always_inline", DECL_ATTRIBUTES (fn)) == NULL)
2056     return 1;
2057
2058   /* Don't auto-inline anything that might not be bound within
2059      this unit of translation.  */
2060   if (!DECL_DECLARED_INLINE_P (fn) && !(*targetm.binds_local_p) (fn))
2061     {
2062       DECL_UNINLINABLE (fn) = 1;
2063       return 1;
2064     }
2065
2066   if (varargs_function_p (fn))
2067     {
2068       DECL_UNINLINABLE (fn) = 1;
2069       return 1;
2070     }
2071
2072   if (! function_attribute_inlinable_p (fn))
2073     {
2074       DECL_UNINLINABLE (fn) = 1;
2075       return 1;
2076     }
2077
2078   return 0;
2079 }
2080
2081 /* Add any pending functions other than the current function (already
2082    handled by the caller), that thus cannot be inlined, to FNS_P, then
2083    return the latest function added to the array, PREV_FN.  */
2084
2085 tree
2086 cp_add_pending_fn_decls (void* fns_p, tree prev_fn)
2087 {
2088   varray_type *fnsp = (varray_type *)fns_p;
2089   struct saved_scope *s;
2090
2091   for (s = scope_chain; s; s = s->prev)
2092     if (s->function_decl && s->function_decl != prev_fn)
2093       {
2094         VARRAY_PUSH_TREE (*fnsp, s->function_decl);
2095         prev_fn = s->function_decl;
2096       }
2097
2098   return prev_fn;
2099 }
2100
2101 /* Determine whether a tree node is an OVERLOAD node.  Used to decide
2102    whether to copy a node or to preserve its chain when inlining a
2103    function.  */
2104
2105 int
2106 cp_is_overload_p (tree t)
2107 {
2108   return TREE_CODE (t) == OVERLOAD;
2109 }
2110
2111 /* Determine whether VAR is a declaration of an automatic variable in
2112    function FN.  */
2113
2114 int
2115 cp_auto_var_in_fn_p (tree var, tree fn)
2116 {
2117   return (DECL_P (var) && DECL_CONTEXT (var) == fn
2118           && nonstatic_local_decl_p (var));
2119 }
2120
2121 /* Tell whether a declaration is needed for the RESULT of a function
2122    FN being inlined into CALLER or if the top node of target_exprs is
2123    to be used.  */
2124
2125 tree
2126 cp_copy_res_decl_for_inlining (tree result,
2127                                tree fn,
2128                                tree caller,
2129                                void* decl_map_,
2130                                int* need_decl,
2131                                tree return_slot_addr)
2132 {
2133   splay_tree decl_map = (splay_tree)decl_map_;
2134   tree var;
2135
2136   /* If FN returns an aggregate then the caller will always pass the
2137      address of the return slot explicitly.  If we were just to
2138      create a new VAR_DECL here, then the result of this function
2139      would be copied (bitwise) into the variable initialized by the
2140      TARGET_EXPR.  That's incorrect, so we must transform any
2141      references to the RESULT into references to the target.  */
2142
2143   /* We should have an explicit return slot iff the return type is
2144      TREE_ADDRESSABLE.  See simplify_aggr_init_expr.  */
2145   if (TREE_ADDRESSABLE (TREE_TYPE (result))
2146       != (return_slot_addr != NULL_TREE))
2147     abort ();
2148
2149   *need_decl = !return_slot_addr;
2150   if (return_slot_addr)
2151     {
2152       var = build_indirect_ref (return_slot_addr, "");
2153       if (! same_type_ignoring_top_level_qualifiers_p (TREE_TYPE (var),
2154                                                        TREE_TYPE (result)))
2155         abort ();
2156     }
2157   /* Otherwise, make an appropriate copy.  */
2158   else
2159     var = copy_decl_for_inlining (result, fn, caller);
2160
2161   if (DECL_SAVED_FUNCTION_DATA (fn))
2162     {
2163       tree nrv = DECL_SAVED_FUNCTION_DATA (fn)->x_return_value;
2164       if (nrv)
2165         {
2166           /* We have a named return value; copy the name and source
2167              position so we can get reasonable debugging information, and
2168              register the return variable as its equivalent.  */
2169           if (TREE_CODE (var) == VAR_DECL
2170               /* But not if we're initializing a variable from the
2171                  enclosing function which already has its own name.  */
2172               && DECL_NAME (var) == NULL_TREE)
2173             {
2174               DECL_NAME (var) = DECL_NAME (nrv);
2175               DECL_SOURCE_LOCATION (var) = DECL_SOURCE_LOCATION (nrv);
2176               DECL_ABSTRACT_ORIGIN (var) = DECL_ORIGIN (nrv);
2177               /* Don't lose initialization info.  */
2178               DECL_INITIAL (var) = DECL_INITIAL (nrv);
2179               /* Don't forget that it needs to go in the stack.  */
2180               TREE_ADDRESSABLE (var) = TREE_ADDRESSABLE (nrv);
2181             }
2182
2183           splay_tree_insert (decl_map,
2184                              (splay_tree_key) nrv,
2185                              (splay_tree_value) var);
2186         }
2187     }
2188
2189   return var;
2190 }
2191
2192 /* Initialize tree.c.  */
2193
2194 void
2195 init_tree (void)
2196 {
2197   list_hash_table = htab_create_ggc (31, list_hash, list_hash_eq, NULL);
2198 }
2199
2200 /* Called via walk_tree.  If *TP points to a DECL_STMT for a local
2201    declaration, copies the declaration and enters it in the splay_tree
2202    pointed to by DATA (which is really a `splay_tree *').  */
2203
2204 static tree
2205 mark_local_for_remap_r (tree* tp,
2206                         int* walk_subtrees ATTRIBUTE_UNUSED ,
2207                         void* data)
2208 {
2209   tree t = *tp;
2210   splay_tree st = (splay_tree) data;
2211   tree decl;
2212
2213
2214   if (TREE_CODE (t) == DECL_STMT
2215       && nonstatic_local_decl_p (DECL_STMT_DECL (t)))
2216     decl = DECL_STMT_DECL (t);
2217   else if (TREE_CODE (t) == LABEL_STMT)
2218     decl = LABEL_STMT_LABEL (t);
2219   else if (TREE_CODE (t) == TARGET_EXPR
2220            && nonstatic_local_decl_p (TREE_OPERAND (t, 0)))
2221     decl = TREE_OPERAND (t, 0);
2222   else if (TREE_CODE (t) == CASE_LABEL)
2223     decl = CASE_LABEL_DECL (t);
2224   else
2225     decl = NULL_TREE;
2226
2227   if (decl)
2228     {
2229       tree copy;
2230
2231       /* Make a copy.  */
2232       copy = copy_decl_for_inlining (decl,
2233                                      DECL_CONTEXT (decl),
2234                                      DECL_CONTEXT (decl));
2235
2236       /* Remember the copy.  */
2237       splay_tree_insert (st,
2238                          (splay_tree_key) decl,
2239                          (splay_tree_value) copy);
2240     }
2241
2242   return NULL_TREE;
2243 }
2244
2245 /* Called via walk_tree when an expression is unsaved.  Using the
2246    splay_tree pointed to by ST (which is really a `splay_tree'),
2247    remaps all local declarations to appropriate replacements.  */
2248
2249 static tree
2250 cp_unsave_r (tree* tp,
2251              int* walk_subtrees,
2252              void* data)
2253 {
2254   splay_tree st = (splay_tree) data;
2255   splay_tree_node n;
2256
2257   /* Only a local declaration (variable or label).  */
2258   if (nonstatic_local_decl_p (*tp))
2259     {
2260       /* Lookup the declaration.  */
2261       n = splay_tree_lookup (st, (splay_tree_key) *tp);
2262
2263       /* If it's there, remap it.  */
2264       if (n)
2265         *tp = (tree) n->value;
2266     }
2267   else if (TREE_CODE (*tp) == SAVE_EXPR)
2268     remap_save_expr (tp, st, current_function_decl, walk_subtrees);
2269   else
2270     {
2271       copy_tree_r (tp, walk_subtrees, NULL);
2272
2273       /* Do whatever unsaving is required.  */
2274       unsave_expr_1 (*tp);
2275     }
2276
2277   /* Keep iterating.  */
2278   return NULL_TREE;
2279 }
2280
2281 /* Called whenever an expression needs to be unsaved.  */
2282
2283 tree
2284 cxx_unsave_expr_now (tree tp)
2285 {
2286   splay_tree st;
2287
2288   /* Create a splay-tree to map old local variable declarations to new
2289      ones.  */
2290   st = splay_tree_new (splay_tree_compare_pointers, NULL, NULL);
2291
2292   /* Walk the tree once figuring out what needs to be remapped.  */
2293   walk_tree (&tp, mark_local_for_remap_r, st, NULL);
2294
2295   /* Walk the tree again, copying, remapping, and unsaving.  */
2296   walk_tree (&tp, cp_unsave_r, st, NULL);
2297
2298   /* Clean up.  */
2299   splay_tree_delete (st);
2300
2301   return tp;
2302 }
2303
2304 /* Returns the kind of special function that DECL (a FUNCTION_DECL)
2305    is.  Note that sfk_none is zero, so this function can be used as a
2306    predicate to test whether or not DECL is a special function.  */
2307
2308 special_function_kind
2309 special_function_p (tree decl)
2310 {
2311   /* Rather than doing all this stuff with magic names, we should
2312      probably have a field of type `special_function_kind' in
2313      DECL_LANG_SPECIFIC.  */
2314   if (DECL_COPY_CONSTRUCTOR_P (decl))
2315     return sfk_copy_constructor;
2316   if (DECL_CONSTRUCTOR_P (decl))
2317     return sfk_constructor;
2318   if (DECL_OVERLOADED_OPERATOR_P (decl) == NOP_EXPR)
2319     return sfk_assignment_operator;
2320   if (DECL_MAYBE_IN_CHARGE_DESTRUCTOR_P (decl))
2321     return sfk_destructor;
2322   if (DECL_COMPLETE_DESTRUCTOR_P (decl))
2323     return sfk_complete_destructor;
2324   if (DECL_BASE_DESTRUCTOR_P (decl))
2325     return sfk_base_destructor;
2326   if (DECL_DELETING_DESTRUCTOR_P (decl))
2327     return sfk_deleting_destructor;
2328   if (DECL_CONV_FN_P (decl))
2329     return sfk_conversion;
2330
2331   return sfk_none;
2332 }
2333
2334 /* Returns true if and only if NODE is a name, i.e., a node created
2335    by the parser when processing an id-expression.  */
2336
2337 bool
2338 name_p (tree node)
2339 {
2340   if (TREE_CODE (node) == TEMPLATE_ID_EXPR)
2341     node = TREE_OPERAND (node, 0);
2342   return (/* An ordinary unqualified name.  */
2343           TREE_CODE (node) == IDENTIFIER_NODE
2344           /* A destructor name.  */
2345           || TREE_CODE (node) == BIT_NOT_EXPR
2346           /* A qualified name.  */
2347           || TREE_CODE (node) == SCOPE_REF);
2348 }
2349
2350 /* Returns nonzero if TYPE is a character type, including wchar_t.  */
2351
2352 int
2353 char_type_p (tree type)
2354 {
2355   return (same_type_p (type, char_type_node)
2356           || same_type_p (type, unsigned_char_type_node)
2357           || same_type_p (type, signed_char_type_node)
2358           || same_type_p (type, wchar_type_node));
2359 }
2360
2361 /* Returns the kind of linkage associated with the indicated DECL.  Th
2362    value returned is as specified by the language standard; it is
2363    independent of implementation details regarding template
2364    instantiation, etc.  For example, it is possible that a declaration
2365    to which this function assigns external linkage would not show up
2366    as a global symbol when you run `nm' on the resulting object file.  */
2367
2368 linkage_kind
2369 decl_linkage (tree decl)
2370 {
2371   /* This function doesn't attempt to calculate the linkage from first
2372      principles as given in [basic.link].  Instead, it makes use of
2373      the fact that we have already set TREE_PUBLIC appropriately, and
2374      then handles a few special cases.  Ideally, we would calculate
2375      linkage first, and then transform that into a concrete
2376      implementation.  */
2377
2378   /* Things that don't have names have no linkage.  */
2379   if (!DECL_NAME (decl))
2380     return lk_none;
2381
2382   /* Things that are TREE_PUBLIC have external linkage.  */
2383   if (TREE_PUBLIC (decl))
2384     return lk_external;
2385
2386   /* Some things that are not TREE_PUBLIC have external linkage, too.
2387      For example, on targets that don't have weak symbols, we make all
2388      template instantiations have internal linkage (in the object
2389      file), but the symbols should still be treated as having external
2390      linkage from the point of view of the language.  */
2391   if (DECL_LANG_SPECIFIC (decl) && DECL_COMDAT (decl))
2392     return lk_external;
2393
2394   /* Things in local scope do not have linkage, if they don't have
2395      TREE_PUBLIC set.  */
2396   if (decl_function_context (decl))
2397     return lk_none;
2398
2399   /* Everything else has internal linkage.  */
2400   return lk_internal;
2401 }
2402 \f
2403 /* EXP is an expression that we want to pre-evaluate.  Returns via INITP an
2404    expression to perform the pre-evaluation, and returns directly an
2405    expression to use the precalculated result.  */
2406
2407 tree
2408 stabilize_expr (tree exp, tree* initp)
2409 {
2410   tree init_expr;
2411
2412   if (!TREE_SIDE_EFFECTS (exp))
2413     {
2414       init_expr = void_zero_node;
2415     }
2416   else if (!real_lvalue_p (exp)
2417            || !TYPE_NEEDS_CONSTRUCTING (TREE_TYPE (exp)))
2418     {
2419       init_expr = get_target_expr (exp);
2420       exp = TARGET_EXPR_SLOT (init_expr);
2421     }
2422   else
2423     {
2424       exp = build_unary_op (ADDR_EXPR, exp, 1);
2425       init_expr = get_target_expr (exp);
2426       exp = TARGET_EXPR_SLOT (init_expr);
2427       exp = build_indirect_ref (exp, 0);
2428     }
2429
2430   *initp = init_expr;
2431   return exp;
2432 }
2433 \f
2434 #if defined ENABLE_TREE_CHECKING && (GCC_VERSION >= 2007)
2435 /* Complain that some language-specific thing hanging off a tree
2436    node has been accessed improperly.  */
2437
2438 void
2439 lang_check_failed (const char* file, int line, const char* function)
2440 {
2441   internal_error ("lang_* check: failed in %s, at %s:%d",
2442                   function, trim_filename (file), line);
2443 }
2444 #endif /* ENABLE_TREE_CHECKING */
2445
2446 #include "gt-cp-tree.h"