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