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