gcc/cp/tree.c

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