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