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