gcc/cp/tree.c

   1 /* Language-dependent node constructors for parse phase of GNU compiler.
   2    Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
   3    1999, 2000, 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
   4    Hacked by Michael Tiemann (tiemann@cygnus.com)
   5
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify
   9 it under the terms of the GNU General Public License as published by
  10 the Free Software Foundation; either version 2, or (at your option)
  11 any later version.
  12
  13 GCC is distributed in the hope that it will be useful,
  14 but WITHOUT ANY WARRANTY; without even the implied warranty of
  15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16 GNU General Public License for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GCC; see the file COPYING.  If not, write to
  20 the Free Software Foundation, 51 Franklin Street, Fifth Floor,
  21 Boston, MA 02110-1301, USA.  */
  22
  23 #include "config.h"
  24 #include "system.h"
  25 #include "coretypes.h"
  26 #include "tm.h"
  27 #include "tree.h"
  28 #include "cp-tree.h"
  29 #include "flags.h"
  30 #include "real.h"
  31 #include "rtl.h"
  32 #include "toplev.h"
  33 #include "insn-config.h"
  34 #include "integrate.h"
  35 #include "tree-inline.h"
  36 #include "debug.h"
  37 #include "target.h"
  38 #include "convert.h"
  39
  40 static tree bot_manip (tree *, int *, void *);
  41 static tree bot_replace (tree *, int *, void *);
  42 static tree build_cplus_array_type_1 (tree, tree);
  43 static int list_hash_eq (const void *, const void *);
  44 static hashval_t list_hash_pieces (tree, tree, tree);
  45 static hashval_t list_hash (const void *);
  46 static cp_lvalue_kind lvalue_p_1 (tree, int);
  47 static tree build_target_expr (tree, tree);
  48 static tree count_trees_r (tree *, int *, void *);
  49 static tree verify_stmt_tree_r (tree *, int *, void *);
  50 static tree build_local_temp (tree);
  51
  52 static tree handle_java_interface_attribute (tree *, tree, tree, int, bool *);
  53 static tree handle_com_interface_attribute (tree *, tree, tree, int, bool *);
  54 static tree handle_init_priority_attribute (tree *, tree, tree, int, bool *);
  55
  56 /* If REF is an lvalue, returns the kind of lvalue that REF is.
  57    Otherwise, returns clk_none.  If TREAT_CLASS_RVALUES_AS_LVALUES is
  58    nonzero, rvalues of class type are considered lvalues.  */
  59
  60 static cp_lvalue_kind
  61 lvalue_p_1 (tree ref,
  62             int treat_class_rvalues_as_lvalues)
  63 {
  64   cp_lvalue_kind op1_lvalue_kind = clk_none;
  65   cp_lvalue_kind op2_lvalue_kind = clk_none;
  66
  67   if (TREE_CODE (TREE_TYPE (ref)) == REFERENCE_TYPE)
  68     return clk_ordinary;
  69
  70   if (ref == current_class_ptr)
  71     return clk_none;
  72
  73   switch (TREE_CODE (ref))
  74     {
  75       /* preincrements and predecrements are valid lvals, provided
  76          what they refer to are valid lvals.  */
  77     case PREINCREMENT_EXPR:
  78     case PREDECREMENT_EXPR:
  79     case SAVE_EXPR:
  80     case TRY_CATCH_EXPR:
  81     case WITH_CLEANUP_EXPR:
  82     case REALPART_EXPR:
  83     case IMAGPART_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       /* Look at the member designator.  */
  91       if (!op1_lvalue_kind
  92           /* The "field" can be a FUNCTION_DECL or an OVERLOAD in some
  93              situations.  */
  94           || TREE_CODE (TREE_OPERAND (ref, 1)) != FIELD_DECL)
  95         ;
  96       else if (DECL_C_BIT_FIELD (TREE_OPERAND (ref, 1)))
  97         {
  98           /* Clear the ordinary bit.  If this object was a class
  99              rvalue we want to preserve that information.  */
 100           op1_lvalue_kind &= ~clk_ordinary;
 101           /* The lvalue is for a bitfield.  */
 102           op1_lvalue_kind |= clk_bitfield;
 103         }
 104       else if (DECL_PACKED (TREE_OPERAND (ref, 1)))
 105         op1_lvalue_kind |= clk_packed;
 106
 107       return op1_lvalue_kind;
 108
 109     case STRING_CST:
 110       return clk_ordinary;
 111
 112     case CONST_DECL:
 113     case VAR_DECL:
 114       if (TREE_READONLY (ref) && ! TREE_STATIC (ref)
 115           && DECL_LANG_SPECIFIC (ref)
 116           && DECL_IN_AGGR_P (ref))
 117         return clk_none;
 118     case INDIRECT_REF:
 119     case ARRAY_REF:
 120     case PARM_DECL:
 121     case RESULT_DECL:
 122       if (TREE_CODE (TREE_TYPE (ref)) != METHOD_TYPE)
 123         return clk_ordinary;
 124       break;
 125
 126       /* A currently unresolved scope ref.  */
 127     case SCOPE_REF:
 128       gcc_unreachable ();
 129     case MAX_EXPR:
 130     case MIN_EXPR:
 131       /* Disallow <? and >? as lvalues if either argument side-effects.  */
 132       if (TREE_SIDE_EFFECTS (TREE_OPERAND (ref, 0))
 133           || TREE_SIDE_EFFECTS (TREE_OPERAND (ref, 1)))
 134         return clk_none;
 135       op1_lvalue_kind = lvalue_p_1 (TREE_OPERAND (ref, 0),
 136                                     treat_class_rvalues_as_lvalues);
 137       op2_lvalue_kind = lvalue_p_1 (TREE_OPERAND (ref, 1),
 138                                     treat_class_rvalues_as_lvalues);
 139       break;
 140
 141     case COND_EXPR:
 142       op1_lvalue_kind = lvalue_p_1 (TREE_OPERAND (ref, 1),
 143                                     treat_class_rvalues_as_lvalues);
 144       op2_lvalue_kind = lvalue_p_1 (TREE_OPERAND (ref, 2),
 145                                     treat_class_rvalues_as_lvalues);
 146       break;
 147
 148     case MODIFY_EXPR:
 149       return clk_ordinary;
 150
 151     case COMPOUND_EXPR:
 152       return lvalue_p_1 (TREE_OPERAND (ref, 1),
 153                          treat_class_rvalues_as_lvalues);
 154
 155     case TARGET_EXPR:
 156       return treat_class_rvalues_as_lvalues ? clk_class : clk_none;
 157
 158     case VA_ARG_EXPR:
 159       return (treat_class_rvalues_as_lvalues
 160               && CLASS_TYPE_P (TREE_TYPE (ref))
 161               ? clk_class : clk_none);
 162
 163     case CALL_EXPR:
 164       /* Any class-valued call would be wrapped in a TARGET_EXPR.  */
 165       return clk_none;
 166
 167     case FUNCTION_DECL:
 168       /* All functions (except non-static-member functions) are
 169          lvalues.  */
 170       return (DECL_NONSTATIC_MEMBER_FUNCTION_P (ref)
 171               ? clk_none : clk_ordinary);
 172
 173     case NON_DEPENDENT_EXPR:
 174       /* We must consider NON_DEPENDENT_EXPRs to be lvalues so that
 175          things like "&E" where "E" is an expression with a
 176          non-dependent type work. It is safe to be lenient because an
 177          error will be issued when the template is instantiated if "E"
 178          is not an lvalue.  */
 179       return clk_ordinary;
 180
 181     default:
 182       break;
 183     }
 184
 185   /* If one operand is not an lvalue at all, then this expression is
 186      not an lvalue.  */
 187   if (!op1_lvalue_kind || !op2_lvalue_kind)
 188     return clk_none;
 189
 190   /* Otherwise, it's an lvalue, and it has all the odd properties
 191      contributed by either operand.  */
 192   op1_lvalue_kind = op1_lvalue_kind | op2_lvalue_kind;
 193   /* It's not an ordinary lvalue if it involves either a bit-field or
 194      a class rvalue.  */
 195   if ((op1_lvalue_kind & ~clk_ordinary) != clk_none)
 196     op1_lvalue_kind &= ~clk_ordinary;
 197   return op1_lvalue_kind;
 198 }
 199
 200 /* Returns the kind of lvalue that REF is, in the sense of
 201    [basic.lval].  This function should really be named lvalue_p; it
 202    computes the C++ definition of lvalue.  */
 203
 204 cp_lvalue_kind
 205 real_lvalue_p (tree ref)
 206 {
 207   return lvalue_p_1 (ref,
 208                      /*treat_class_rvalues_as_lvalues=*/0);
 209 }
 210
 211 /* This differs from real_lvalue_p in that class rvalues are
 212    considered lvalues.  */
 213
 214 int
 215 lvalue_p (tree ref)
 216 {
 217   return
 218     (lvalue_p_1 (ref, /*class rvalue ok*/ 1) != clk_none);
 219 }
 220
 221 /* Test whether DECL is a builtin that may appear in a
 222    constant-expression. */
 223
 224 bool
 225 builtin_valid_in_constant_expr_p (tree decl)
 226 {
 227   /* At present BUILT_IN_CONSTANT_P is the only builtin we're allowing
 228      in constant-expressions.  We may want to add other builtins later. */
 229   return DECL_IS_BUILTIN_CONSTANT_P (decl);
 230 }
 231
 232 /* Build a TARGET_EXPR, initializing the DECL with the VALUE.  */
 233
 234 static tree
 235 build_target_expr (tree decl, tree value)
 236 {
 237   tree t;
 238
 239   t = build4 (TARGET_EXPR, TREE_TYPE (decl), decl, value,
 240               cxx_maybe_build_cleanup (decl), NULL_TREE);
 241   /* We always set TREE_SIDE_EFFECTS so that expand_expr does not
 242      ignore the TARGET_EXPR.  If there really turn out to be no
 243      side-effects, then the optimizer should be able to get rid of
 244      whatever code is generated anyhow.  */
 245   TREE_SIDE_EFFECTS (t) = 1;
 246
 247   return t;
 248 }
 249
 250 /* Return an undeclared local temporary of type TYPE for use in building a
 251    TARGET_EXPR.  */
 252
 253 static tree
 254 build_local_temp (tree type)
 255 {
 256   tree slot = build_decl (VAR_DECL, NULL_TREE, type);
 257   DECL_ARTIFICIAL (slot) = 1;
 258   DECL_IGNORED_P (slot) = 1;
 259   DECL_CONTEXT (slot) = current_function_decl;
 260   layout_decl (slot, 0);
 261   return slot;
 262 }
 263
 264 /* INIT is a CALL_EXPR which needs info about its target.
 265    TYPE is the type that this initialization should appear to have.
 266
 267    Build an encapsulation of the initialization to perform
 268    and return it so that it can be processed by language-independent
 269    and language-specific expression expanders.  */
 270
 271 tree
 272 build_cplus_new (tree type, tree init)
 273 {
 274   tree fn;
 275   tree slot;
 276   tree rval;
 277   int is_ctor;
 278
 279   /* Make sure that we're not trying to create an instance of an
 280      abstract class.  */
 281   abstract_virtuals_error (NULL_TREE, type);
 282
 283   if (TREE_CODE (init) != CALL_EXPR && TREE_CODE (init) != AGGR_INIT_EXPR)
 284     return convert (type, init);
 285
 286   fn = TREE_OPERAND (init, 0);
 287   is_ctor = (TREE_CODE (fn) == ADDR_EXPR
 288              && TREE_CODE (TREE_OPERAND (fn, 0)) == FUNCTION_DECL
 289              && DECL_CONSTRUCTOR_P (TREE_OPERAND (fn, 0)));
 290
 291   slot = build_local_temp (type);
 292
 293   /* We split the CALL_EXPR into its function and its arguments here.
 294      Then, in expand_expr, we put them back together.  The reason for
 295      this is that this expression might be a default argument
 296      expression.  In that case, we need a new temporary every time the
 297      expression is used.  That's what break_out_target_exprs does; it
 298      replaces every AGGR_INIT_EXPR with a copy that uses a fresh
 299      temporary slot.  Then, expand_expr builds up a call-expression
 300      using the new slot.  */
 301
 302   /* If we don't need to use a constructor to create an object of this
 303      type, don't mess with AGGR_INIT_EXPR.  */
 304   if (is_ctor || TREE_ADDRESSABLE (type))
 305     {
 306       rval = build3 (AGGR_INIT_EXPR, void_type_node, fn,
 307                      TREE_OPERAND (init, 1), slot);
 308       TREE_SIDE_EFFECTS (rval) = 1;
 309       AGGR_INIT_VIA_CTOR_P (rval) = is_ctor;
 310     }
 311   else
 312     rval = init;
 313
 314   rval = build_target_expr (slot, rval);
 315   TARGET_EXPR_IMPLICIT_P (rval) = 1;
 316
 317   return rval;
 318 }
 319
 320 /* Build a TARGET_EXPR using INIT to initialize a new temporary of the
 321    indicated TYPE.  */
 322
 323 tree
 324 build_target_expr_with_type (tree init, tree type)
 325 {
 326   gcc_assert (!VOID_TYPE_P (type));
 327
 328   if (TREE_CODE (init) == TARGET_EXPR)
 329     return init;
 330   else if (CLASS_TYPE_P (type) && !TYPE_HAS_TRIVIAL_INIT_REF (type)
 331            && TREE_CODE (init) != COND_EXPR
 332            && TREE_CODE (init) != CONSTRUCTOR
 333            && TREE_CODE (init) != VA_ARG_EXPR)
 334     /* We need to build up a copy constructor call.  COND_EXPR is a special
 335        case because we already have copies on the arms and we don't want
 336        another one here.  A CONSTRUCTOR is aggregate initialization, which
 337        is handled separately.  A VA_ARG_EXPR is magic creation of an
 338        aggregate; there's no additional work to be done.  */
 339     return force_rvalue (init);
 340
 341   return force_target_expr (type, init);
 342 }
 343
 344 /* Like the above function, but without the checking.  This function should
 345    only be used by code which is deliberately trying to subvert the type
 346    system, such as call_builtin_trap.  */
 347
 348 tree
 349 force_target_expr (tree type, tree init)
 350 {
 351   tree slot;
 352
 353   gcc_assert (!VOID_TYPE_P (type));
 354
 355   slot = build_local_temp (type);
 356   return build_target_expr (slot, init);
 357 }
 358
 359 /* Like build_target_expr_with_type, but use the type of INIT.  */
 360
 361 tree
 362 get_target_expr (tree init)
 363 {
 364   return build_target_expr_with_type (init, TREE_TYPE (init));
 365 }
 366
 367 /* If EXPR is a bitfield reference, convert it to the declared type of
 368    the bitfield, and return the resulting expression.  Otherwise,
 369    return EXPR itself.  */
 370
 371 tree
 372 convert_bitfield_to_declared_type (tree expr)
 373 {
 374   tree bitfield_type;
 375
 376   bitfield_type = is_bitfield_expr_with_lowered_type (expr);
 377   if (bitfield_type)
 378     expr = convert_to_integer (TYPE_MAIN_VARIANT (bitfield_type),
 379                                expr);
 380   return expr;
 381 }
 382
 383 /* EXPR is being used in an rvalue context.  Return a version of EXPR
 384    that is marked as an rvalue.  */
 385
 386 tree
 387 rvalue (tree expr)
 388 {
 389   tree type;
 390
 391   if (error_operand_p (expr))
 392     return expr;
 393
 394   /* [basic.lval]
 395
 396      Non-class rvalues always have cv-unqualified types.  */
 397   type = TREE_TYPE (expr);
 398   if (!CLASS_TYPE_P (type) && cp_type_quals (type))
 399     type = TYPE_MAIN_VARIANT (type);
 400
 401   if (!processing_template_decl && real_lvalue_p (expr))
 402     expr = build1 (NON_LVALUE_EXPR, type, expr);
 403   else if (type != TREE_TYPE (expr))
 404     expr = build_nop (type, expr);
 405
 406   return expr;
 407 }
 408
 409 \f
 410 /* Hash an ARRAY_TYPE.  K is really of type `tree'.  */
 411
 412 static hashval_t
 413 cplus_array_hash (const void* k)
 414 {
 415   hashval_t hash;
 416   tree t = (tree) k;
 417
 418   hash = (htab_hash_pointer (TREE_TYPE (t))
 419           ^ htab_hash_pointer (TYPE_DOMAIN (t)));
 420
 421   return hash;
 422 }
 423
 424 typedef struct cplus_array_info {
 425   tree type;
 426   tree domain;
 427 } cplus_array_info;
 428
 429 /* Compare two ARRAY_TYPEs.  K1 is really of type `tree', K2 is really
 430    of type `cplus_array_info*'. */
 431
 432 static int
 433 cplus_array_compare (const void * k1, const void * k2)
 434 {
 435   tree t1 = (tree) k1;
 436   const cplus_array_info *t2 = (const cplus_array_info*) k2;
 437
 438   if (!comptypes (TREE_TYPE (t1), t2->type, COMPARE_STRUCTURAL))
 439     return 0;
 440
 441   if (!TYPE_DOMAIN (t1))
 442     return !t2->domain;
 443
 444   if (!t2->domain)
 445     return 0;
 446
 447   return comptypes (TYPE_DOMAIN (t1), t2->domain, COMPARE_STRUCTURAL);
 448 }
 449
 450 static GTY ((param_is (union tree_node))) htab_t cplus_array_htab;
 451
 452
 453 static tree
 454 build_cplus_array_type_1 (tree elt_type, tree index_type)
 455 {
 456   tree t;
 457
 458   if (elt_type == error_mark_node || index_type == error_mark_node)
 459     return error_mark_node;
 460
 461   if (dependent_type_p (elt_type)
 462       || (index_type
 463           && value_dependent_expression_p (TYPE_MAX_VALUE (index_type))))
 464     {
 465       void **e;
 466       cplus_array_info cai;
 467       hashval_t hash;
 468
 469       if (cplus_array_htab == NULL)
 470         cplus_array_htab = htab_create_ggc (61, &cplus_array_hash,
 471                                             &cplus_array_compare, NULL);
 472
 473       hash = (htab_hash_pointer (elt_type)
 474               ^ htab_hash_pointer (index_type));
 475       cai.type = elt_type;
 476       cai.domain = index_type;
 477
 478       e = htab_find_slot_with_hash (cplus_array_htab, &cai, hash, INSERT);
 479       if (*e)
 480         /* We have found the type: we're done. */
 481         return (tree) *e;
 482       else
 483         {
 484           /* Build a new array type. */
 485           t = make_node (ARRAY_TYPE);
 486           TREE_TYPE (t) = elt_type;
 487           TYPE_DOMAIN (t) = index_type;
 488
 489           /* Complete building the array type. */
 490           if (TYPE_STRUCTURAL_EQUALITY_P (elt_type)
 491               || (index_type && TYPE_STRUCTURAL_EQUALITY_P (index_type)))
 492             SET_TYPE_STRUCTURAL_EQUALITY (t);
 493           else if (TYPE_CANONICAL (elt_type) != elt_type
 494                    || (index_type
 495                        && TYPE_CANONICAL (index_type) != index_type))
 496             TYPE_CANONICAL (t)
 497               = TYPE_CANONICAL
 498                   (build_cplus_array_type_1 (TYPE_CANONICAL (elt_type),
 499                                              index_type?
 500                                                TYPE_CANONICAL (index_type)
 501                                                : index_type));
 502
 503           /* Store it in the hash table. */
 504           *e = t;
 505         }
 506     }
 507   else
 508     t = build_array_type (elt_type, index_type);
 509
 510   /* Push these needs up so that initialization takes place
 511      more easily.  */
 512   TYPE_NEEDS_CONSTRUCTING (t)
 513     = TYPE_NEEDS_CONSTRUCTING (TYPE_MAIN_VARIANT (elt_type));
 514   TYPE_HAS_NONTRIVIAL_DESTRUCTOR (t)
 515     = TYPE_HAS_NONTRIVIAL_DESTRUCTOR (TYPE_MAIN_VARIANT (elt_type));
 516   return t;
 517 }
 518
 519 tree
 520 build_cplus_array_type (tree elt_type, tree index_type)
 521 {
 522   tree t;
 523   int type_quals = cp_type_quals (elt_type);
 524
 525   if (type_quals != TYPE_UNQUALIFIED)
 526     elt_type = cp_build_qualified_type (elt_type, TYPE_UNQUALIFIED);
 527
 528   t = build_cplus_array_type_1 (elt_type, index_type);
 529
 530   if (type_quals != TYPE_UNQUALIFIED)
 531     t = cp_build_qualified_type (t, type_quals);
 532
 533   return t;
 534 }
 535 \f
 536 /* Make a variant of TYPE, qualified with the TYPE_QUALS.  Handles
 537    arrays correctly.  In particular, if TYPE is an array of T's, and
 538    TYPE_QUALS is non-empty, returns an array of qualified T's.
 539
 540    FLAGS determines how to deal with illformed qualifications. If
 541    tf_ignore_bad_quals is set, then bad qualifications are dropped
 542    (this is permitted if TYPE was introduced via a typedef or template
 543    type parameter). If bad qualifications are dropped and tf_warning
 544    is set, then a warning is issued for non-const qualifications.  If
 545    tf_ignore_bad_quals is not set and tf_error is not set, we
 546    return error_mark_node. Otherwise, we issue an error, and ignore
 547    the qualifications.
 548
 549    Qualification of a reference type is valid when the reference came
 550    via a typedef or template type argument. [dcl.ref] No such
 551    dispensation is provided for qualifying a function type.  [dcl.fct]
 552    DR 295 queries this and the proposed resolution brings it into line
 553    with qualifying a reference.  We implement the DR.  We also behave
 554    in a similar manner for restricting non-pointer types.  */
 555
 556 tree
 557 cp_build_qualified_type_real (tree type,
 558                               int type_quals,
 559                               tsubst_flags_t complain)
 560 {
 561   tree result;
 562   int bad_quals = TYPE_UNQUALIFIED;
 563
 564   if (type == error_mark_node)
 565     return type;
 566
 567   if (type_quals == cp_type_quals (type))
 568     return type;
 569
 570   if (TREE_CODE (type) == ARRAY_TYPE)
 571     {
 572       /* In C++, the qualification really applies to the array element
 573          type.  Obtain the appropriately qualified element type.  */
 574       tree t;
 575       tree element_type
 576         = cp_build_qualified_type_real (TREE_TYPE (type),
 577                                         type_quals,
 578                                         complain);
 579
 580       if (element_type == error_mark_node)
 581         return error_mark_node;
 582
 583       /* See if we already have an identically qualified type.  */
 584       for (t = TYPE_MAIN_VARIANT (type); t; t = TYPE_NEXT_VARIANT (t))
 585         if (cp_type_quals (t) == type_quals
 586             && TYPE_NAME (t) == TYPE_NAME (type)
 587             && TYPE_CONTEXT (t) == TYPE_CONTEXT (type))
 588           break;
 589
 590       if (!t)
 591         {
 592           tree domain = TYPE_DOMAIN (type);
 593
 594           /* Make a new array type, just like the old one, but with the
 595              appropriately qualified element type.  */
 596           t = build_variant_type_copy (type);
 597           TREE_TYPE (t) = element_type;
 598
 599           /* This is a new type. */
 600           TYPE_CANONICAL (t) = t;
 601
 602           if (dependent_type_p (element_type)
 603               || (domain
 604                   && value_dependent_expression_p (TYPE_MAX_VALUE (domain))))
 605             {
 606               /* The new dependent array type we just created might be
 607                  equivalent to an existing dependent array type, so we
 608                  need to keep track of this new array type with a
 609                  lookup into CPLUS_ARRAY_HTAB. Note that we cannot
 610                  directly call build_cplus_array_type (that would
 611                  recurse) or build_cplus_array_type_1 (that would lose
 612                  attributes). */
 613               void **e;
 614               cplus_array_info cai;
 615               hashval_t hash;
 616
 617               if (cplus_array_htab == NULL)
 618                 cplus_array_htab = htab_create_ggc (61, &cplus_array_hash,
 619                                                     &cplus_array_compare,
 620                                                     NULL);
 621
 622               hash = (htab_hash_pointer (element_type)
 623                       ^ htab_hash_pointer (domain));
 624               cai.type = element_type;
 625               cai.domain = domain;
 626
 627               e = htab_find_slot_with_hash (cplus_array_htab, &cai, hash,
 628                                             INSERT);
 629               if (! *e)
 630                 /* Save this new type. */
 631                 *e = t;
 632             }
 633
 634           if (TYPE_STRUCTURAL_EQUALITY_P (TREE_TYPE (t))
 635                    || (TYPE_DOMAIN (t)
 636                        && TYPE_STRUCTURAL_EQUALITY_P (TYPE_DOMAIN (t))))
 637             SET_TYPE_STRUCTURAL_EQUALITY (t);
 638           else
 639             TYPE_CANONICAL (t)
 640               = TYPE_CANONICAL
 641                   (build_array_type (TYPE_CANONICAL (TREE_TYPE (t)),
 642                                      TYPE_DOMAIN (t)?
 643                                        TYPE_CANONICAL (TYPE_DOMAIN(t))
 644                                        : TYPE_DOMAIN (t)));
 645         }
 646
 647       /* Even if we already had this variant, we update
 648          TYPE_NEEDS_CONSTRUCTING and TYPE_HAS_NONTRIVIAL_DESTRUCTOR in case
 649          they changed since the variant was originally created.
 650
 651          This seems hokey; if there is some way to use a previous
 652          variant *without* coming through here,
 653          TYPE_NEEDS_CONSTRUCTING will never be updated.  */
 654       TYPE_NEEDS_CONSTRUCTING (t)
 655         = TYPE_NEEDS_CONSTRUCTING (TYPE_MAIN_VARIANT (element_type));
 656       TYPE_HAS_NONTRIVIAL_DESTRUCTOR (t)
 657         = TYPE_HAS_NONTRIVIAL_DESTRUCTOR (TYPE_MAIN_VARIANT (element_type));
 658       return t;
 659     }
 660   else if (TYPE_PTRMEMFUNC_P (type))
 661     {
 662       /* For a pointer-to-member type, we can't just return a
 663          cv-qualified version of the RECORD_TYPE.  If we do, we
 664          haven't changed the field that contains the actual pointer to
 665          a method, and so TYPE_PTRMEMFUNC_FN_TYPE will be wrong.  */
 666       tree t;
 667
 668       t = TYPE_PTRMEMFUNC_FN_TYPE (type);
 669       t = cp_build_qualified_type_real (t, type_quals, complain);
 670       return build_ptrmemfunc_type (t);
 671     }
 672
 673   /* A reference or method type shall not be cv qualified.
 674      [dcl.ref], [dct.fct]  */
 675   if (type_quals & (TYPE_QUAL_CONST | TYPE_QUAL_VOLATILE)
 676       && (TREE_CODE (type) == REFERENCE_TYPE
 677           || TREE_CODE (type) == METHOD_TYPE))
 678     {
 679       bad_quals |= type_quals & (TYPE_QUAL_CONST | TYPE_QUAL_VOLATILE);
 680       type_quals &= ~(TYPE_QUAL_CONST | TYPE_QUAL_VOLATILE);
 681     }
 682
 683   /* A restrict-qualified type must be a pointer (or reference)
 684      to object or incomplete type, or a function type. */
 685   if ((type_quals & TYPE_QUAL_RESTRICT)
 686       && TREE_CODE (type) != TEMPLATE_TYPE_PARM
 687       && TREE_CODE (type) != TYPENAME_TYPE
 688       && TREE_CODE (type) != FUNCTION_TYPE
 689       && !POINTER_TYPE_P (type))
 690     {
 691       bad_quals |= TYPE_QUAL_RESTRICT;
 692       type_quals &= ~TYPE_QUAL_RESTRICT;
 693     }
 694
 695   if (bad_quals == TYPE_UNQUALIFIED)
 696     /*OK*/;
 697   else if (!(complain & (tf_error | tf_ignore_bad_quals)))
 698     return error_mark_node;
 699   else
 700     {
 701       if (complain & tf_ignore_bad_quals)
 702         /* We're not going to warn about constifying things that can't
 703            be constified.  */
 704         bad_quals &= ~TYPE_QUAL_CONST;
 705       if (bad_quals)
 706         {
 707           tree bad_type = build_qualified_type (ptr_type_node, bad_quals);
 708
 709           if (!(complain & tf_ignore_bad_quals))
 710             error ("%qV qualifiers cannot be applied to %qT",
 711                    bad_type, type);
 712         }
 713     }
 714
 715   /* Retrieve (or create) the appropriately qualified variant.  */
 716   result = build_qualified_type (type, type_quals);
 717
 718   /* If this was a pointer-to-method type, and we just made a copy,
 719      then we need to unshare the record that holds the cached
 720      pointer-to-member-function type, because these will be distinct
 721      between the unqualified and qualified types.  */
 722   if (result != type
 723       && TREE_CODE (type) == POINTER_TYPE
 724       && TREE_CODE (TREE_TYPE (type)) == METHOD_TYPE)
 725     TYPE_LANG_SPECIFIC (result) = NULL;
 726
 727   return result;
 728 }
 729
 730 /* Returns the canonical version of TYPE.  In other words, if TYPE is
 731    a typedef, returns the underlying type.  The cv-qualification of
 732    the type returned matches the type input; they will always be
 733    compatible types.  */
 734
 735 tree
 736 canonical_type_variant (tree t)
 737 {
 738   return cp_build_qualified_type (TYPE_MAIN_VARIANT (t), cp_type_quals (t));
 739 }
 740 \f
 741 /* Makes a copy of BINFO and TYPE, which is to be inherited into a
 742    graph dominated by T.  If BINFO is NULL, TYPE is a dependent base,
 743    and we do a shallow copy.  If BINFO is non-NULL, we do a deep copy.
 744    VIRT indicates whether TYPE is inherited virtually or not.
 745    IGO_PREV points at the previous binfo of the inheritance graph
 746    order chain.  The newly copied binfo's TREE_CHAIN forms this
 747    ordering.
 748
 749    The CLASSTYPE_VBASECLASSES vector of T is constructed in the
 750    correct order. That is in the order the bases themselves should be
 751    constructed in.
 752
 753    The BINFO_INHERITANCE of a virtual base class points to the binfo
 754    of the most derived type. ??? We could probably change this so that
 755    BINFO_INHERITANCE becomes synonymous with BINFO_PRIMARY, and hence
 756    remove a field.  They currently can only differ for primary virtual
 757    virtual bases.  */
 758
 759 tree
 760 copy_binfo (tree binfo, tree type, tree t, tree *igo_prev, int virt)
 761 {
 762   tree new_binfo;
 763
 764   if (virt)
 765     {
 766       /* See if we've already made this virtual base.  */
 767       new_binfo = binfo_for_vbase (type, t);
 768       if (new_binfo)
 769         return new_binfo;
 770     }
 771
 772   new_binfo = make_tree_binfo (binfo ? BINFO_N_BASE_BINFOS (binfo) : 0);
 773   BINFO_TYPE (new_binfo) = type;
 774
 775   /* Chain it into the inheritance graph.  */
 776   TREE_CHAIN (*igo_prev) = new_binfo;
 777   *igo_prev = new_binfo;
 778
 779   if (binfo)
 780     {
 781       int ix;
 782       tree base_binfo;
 783
 784       gcc_assert (!BINFO_DEPENDENT_BASE_P (binfo));
 785       gcc_assert (SAME_BINFO_TYPE_P (BINFO_TYPE (binfo), type));
 786
 787       BINFO_OFFSET (new_binfo) = BINFO_OFFSET (binfo);
 788       BINFO_VIRTUALS (new_binfo) = BINFO_VIRTUALS (binfo);
 789
 790       /* We do not need to copy the accesses, as they are read only.  */
 791       BINFO_BASE_ACCESSES (new_binfo) = BINFO_BASE_ACCESSES (binfo);
 792
 793       /* Recursively copy base binfos of BINFO.  */
 794       for (ix = 0; BINFO_BASE_ITERATE (binfo, ix, base_binfo); ix++)
 795         {
 796           tree new_base_binfo;
 797
 798           gcc_assert (!BINFO_DEPENDENT_BASE_P (base_binfo));
 799           new_base_binfo = copy_binfo (base_binfo, BINFO_TYPE (base_binfo),
 800                                        t, igo_prev,
 801                                        BINFO_VIRTUAL_P (base_binfo));
 802
 803           if (!BINFO_INHERITANCE_CHAIN (new_base_binfo))
 804             BINFO_INHERITANCE_CHAIN (new_base_binfo) = new_binfo;
 805           BINFO_BASE_APPEND (new_binfo, new_base_binfo);
 806         }
 807     }
 808   else
 809     BINFO_DEPENDENT_BASE_P (new_binfo) = 1;
 810
 811   if (virt)
 812     {
 813       /* Push it onto the list after any virtual bases it contains
 814          will have been pushed.  */
 815       VEC_quick_push (tree, CLASSTYPE_VBASECLASSES (t), new_binfo);
 816       BINFO_VIRTUAL_P (new_binfo) = 1;
 817       BINFO_INHERITANCE_CHAIN (new_binfo) = TYPE_BINFO (t);
 818     }
 819
 820   return new_binfo;
 821 }
 822 \f
 823 /* Hashing of lists so that we don't make duplicates.
 824    The entry point is `list_hash_canon'.  */
 825
 826 /* Now here is the hash table.  When recording a list, it is added
 827    to the slot whose index is the hash code mod the table size.
 828    Note that the hash table is used for several kinds of lists.
 829    While all these live in the same table, they are completely independent,
 830    and the hash code is computed differently for each of these.  */
 831
 832 static GTY ((param_is (union tree_node))) htab_t list_hash_table;
 833
 834 struct list_proxy
 835 {
 836   tree purpose;
 837   tree value;
 838   tree chain;
 839 };
 840
 841 /* Compare ENTRY (an entry in the hash table) with DATA (a list_proxy
 842    for a node we are thinking about adding).  */
 843
 844 static int
 845 list_hash_eq (const void* entry, const void* data)
 846 {
 847   tree t = (tree) entry;
 848   struct list_proxy *proxy = (struct list_proxy *) data;
 849
 850   return (TREE_VALUE (t) == proxy->value
 851           && TREE_PURPOSE (t) == proxy->purpose
 852           && TREE_CHAIN (t) == proxy->chain);
 853 }
 854
 855 /* Compute a hash code for a list (chain of TREE_LIST nodes
 856    with goodies in the TREE_PURPOSE, TREE_VALUE, and bits of the
 857    TREE_COMMON slots), by adding the hash codes of the individual entries.  */
 858
 859 static hashval_t
 860 list_hash_pieces (tree purpose, tree value, tree chain)
 861 {
 862   hashval_t hashcode = 0;
 863
 864   if (chain)
 865     hashcode += TREE_HASH (chain);
 866
 867   if (value)
 868     hashcode += TREE_HASH (value);
 869   else
 870     hashcode += 1007;
 871   if (purpose)
 872     hashcode += TREE_HASH (purpose);
 873   else
 874     hashcode += 1009;
 875   return hashcode;
 876 }
 877
 878 /* Hash an already existing TREE_LIST.  */
 879
 880 static hashval_t
 881 list_hash (const void* p)
 882 {
 883   tree t = (tree) p;
 884   return list_hash_pieces (TREE_PURPOSE (t),
 885                            TREE_VALUE (t),
 886                            TREE_CHAIN (t));
 887 }
 888
 889 /* Given list components PURPOSE, VALUE, AND CHAIN, return the canonical
 890    object for an identical list if one already exists.  Otherwise, build a
 891    new one, and record it as the canonical object.  */
 892
 893 tree
 894 hash_tree_cons (tree purpose, tree value, tree chain)
 895 {
 896   int hashcode = 0;
 897   void **slot;
 898   struct list_proxy proxy;
 899
 900   /* Hash the list node.  */
 901   hashcode = list_hash_pieces (purpose, value, chain);
 902   /* Create a proxy for the TREE_LIST we would like to create.  We
 903      don't actually create it so as to avoid creating garbage.  */
 904   proxy.purpose = purpose;
 905   proxy.value = value;
 906   proxy.chain = chain;
 907   /* See if it is already in the table.  */
 908   slot = htab_find_slot_with_hash (list_hash_table, &proxy, hashcode,
 909                                    INSERT);
 910   /* If not, create a new node.  */
 911   if (!*slot)
 912     *slot = tree_cons (purpose, value, chain);
 913   return (tree) *slot;
 914 }
 915
 916 /* Constructor for hashed lists.  */
 917
 918 tree
 919 hash_tree_chain (tree value, tree chain)
 920 {
 921   return hash_tree_cons (NULL_TREE, value, chain);
 922 }
 923 \f
 924 void
 925 debug_binfo (tree elem)
 926 {
 927   HOST_WIDE_INT n;
 928   tree virtuals;
 929
 930   fprintf (stderr, "type \"%s\", offset = " HOST_WIDE_INT_PRINT_DEC
 931            "\nvtable type:\n",
 932            TYPE_NAME_STRING (BINFO_TYPE (elem)),
 933            TREE_INT_CST_LOW (BINFO_OFFSET (elem)));
 934   debug_tree (BINFO_TYPE (elem));
 935   if (BINFO_VTABLE (elem))
 936     fprintf (stderr, "vtable decl \"%s\"\n",
 937              IDENTIFIER_POINTER (DECL_NAME (get_vtbl_decl_for_binfo (elem))));
 938   else
 939     fprintf (stderr, "no vtable decl yet\n");
 940   fprintf (stderr, "virtuals:\n");
 941   virtuals = BINFO_VIRTUALS (elem);
 942   n = 0;
 943
 944   while (virtuals)
 945     {
 946       tree fndecl = TREE_VALUE (virtuals);
 947       fprintf (stderr, "%s [%ld =? %ld]\n",
 948                IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (fndecl)),
 949                (long) n, (long) TREE_INT_CST_LOW (DECL_VINDEX (fndecl)));
 950       ++n;
 951       virtuals = TREE_CHAIN (virtuals);
 952     }
 953 }
 954
 955 /* Build a representation for the qualified name SCOPE::NAME.  TYPE is
 956    the type of the result expression, if known, or NULL_TREE if the
 957    resulting expression is type-dependent.  If TEMPLATE_P is true,
 958    NAME is known to be a template because the user explicitly used the
 959    "template" keyword after the "::".
 960
 961    All SCOPE_REFs should be built by use of this function.  */
 962
 963 tree
 964 build_qualified_name (tree type, tree scope, tree name, bool template_p)
 965 {
 966   tree t;
 967   if (type == error_mark_node
 968       || scope == error_mark_node
 969       || name == error_mark_node)
 970     return error_mark_node;
 971   t = build2 (SCOPE_REF, type, scope, name);
 972   QUALIFIED_NAME_IS_TEMPLATE (t) = template_p;
 973   return t;
 974 }
 975
 976 /* Returns non-zero if X is an expression for a (possibly overloaded)
 977    function.  If "f" is a function or function template, "f", "c->f",
 978    "c.f", "C::f", and "f<int>" will all be considered possibly
 979    overloaded functions.  Returns 2 if the function is actually
 980    overloaded, i.e., if it is impossible to know the the type of the
 981    function without performing overload resolution.  */
 982
 983 int
 984 is_overloaded_fn (tree x)
 985 {
 986   /* A baselink is also considered an overloaded function.  */
 987   if (TREE_CODE (x) == OFFSET_REF
 988       || TREE_CODE (x) == COMPONENT_REF)
 989     x = TREE_OPERAND (x, 1);
 990   if (BASELINK_P (x))
 991     x = BASELINK_FUNCTIONS (x);
 992   if (TREE_CODE (x) == TEMPLATE_ID_EXPR
 993       || DECL_FUNCTION_TEMPLATE_P (OVL_CURRENT (x))
 994       || (TREE_CODE (x) == OVERLOAD && OVL_CHAIN (x)))
 995     return 2;
 996   return  (TREE_CODE (x) == FUNCTION_DECL
 997            || TREE_CODE (x) == OVERLOAD);
 998 }
 999
1000 /* Returns true iff X is an expression for an overloaded function
1001    whose type cannot be known without performing overload
1002    resolution.  */
1003
1004 bool
1005 really_overloaded_fn (tree x)
1006 {
1007   return is_overloaded_fn (x) == 2;
1008 }
1009
1010 tree
1011 get_first_fn (tree from)
1012 {
1013   gcc_assert (is_overloaded_fn (from));
1014   /* A baselink is also considered an overloaded function.  */
1015   if (TREE_CODE (from) == COMPONENT_REF)
1016     from = TREE_OPERAND (from, 1);
1017   if (BASELINK_P (from))
1018     from = BASELINK_FUNCTIONS (from);
1019   return OVL_CURRENT (from);
1020 }
1021
1022 /* Return a new OVL node, concatenating it with the old one.  */
1023
1024 tree
1025 ovl_cons (tree decl, tree chain)
1026 {
1027   tree result = make_node (OVERLOAD);
1028   TREE_TYPE (result) = unknown_type_node;
1029   OVL_FUNCTION (result) = decl;
1030   TREE_CHAIN (result) = chain;
1031
1032   return result;
1033 }
1034
1035 /* Build a new overloaded function. If this is the first one,
1036    just return it; otherwise, ovl_cons the _DECLs */
1037
1038 tree
1039 build_overload (tree decl, tree chain)
1040 {
1041   if (! chain && TREE_CODE (decl) != TEMPLATE_DECL)
1042     return decl;
1043   if (chain && TREE_CODE (chain) != OVERLOAD)
1044     chain = ovl_cons (chain, NULL_TREE);
1045   return ovl_cons (decl, chain);
1046 }
1047
1048 \f
1049 #define PRINT_RING_SIZE 4
1050
1051 const char *
1052 cxx_printable_name (tree decl, int v)
1053 {
1054   static tree decl_ring[PRINT_RING_SIZE];
1055   static char *print_ring[PRINT_RING_SIZE];
1056   static int ring_counter;
1057   int i;
1058
1059   /* Only cache functions.  */
1060   if (v < 2
1061       || TREE_CODE (decl) != FUNCTION_DECL
1062       || DECL_LANG_SPECIFIC (decl) == 0)
1063     return lang_decl_name (decl, v);
1064
1065   /* See if this print name is lying around.  */
1066   for (i = 0; i < PRINT_RING_SIZE; i++)
1067     if (decl_ring[i] == decl)
1068       /* yes, so return it.  */
1069       return print_ring[i];
1070
1071   if (++ring_counter == PRINT_RING_SIZE)
1072     ring_counter = 0;
1073
1074   if (current_function_decl != NULL_TREE)
1075     {
1076       if (decl_ring[ring_counter] == current_function_decl)
1077         ring_counter += 1;
1078       if (ring_counter == PRINT_RING_SIZE)
1079         ring_counter = 0;
1080       gcc_assert (decl_ring[ring_counter] != current_function_decl);
1081     }
1082
1083   if (print_ring[ring_counter])
1084     free (print_ring[ring_counter]);
1085
1086   print_ring[ring_counter] = xstrdup (lang_decl_name (decl, v));
1087   decl_ring[ring_counter] = decl;
1088   return print_ring[ring_counter];
1089 }
1090 \f
1091 /* Build the FUNCTION_TYPE or METHOD_TYPE which may throw exceptions
1092    listed in RAISES.  */
1093
1094 tree
1095 build_exception_variant (tree type, tree raises)
1096 {
1097   tree v = TYPE_MAIN_VARIANT (type);
1098   int type_quals = TYPE_QUALS (type);
1099
1100   for (; v; v = TYPE_NEXT_VARIANT (v))
1101     if (check_qualified_type (v, type, type_quals)
1102         && comp_except_specs (raises, TYPE_RAISES_EXCEPTIONS (v), 1))
1103       return v;
1104
1105   /* Need to build a new variant.  */
1106   v = build_variant_type_copy (type);
1107   TYPE_RAISES_EXCEPTIONS (v) = raises;
1108   return v;
1109 }
1110
1111 /* Given a TEMPLATE_TEMPLATE_PARM node T, create a new
1112    BOUND_TEMPLATE_TEMPLATE_PARM bound with NEWARGS as its template
1113    arguments.  */
1114
1115 tree
1116 bind_template_template_parm (tree t, tree newargs)
1117 {
1118   tree decl = TYPE_NAME (t);
1119   tree t2;
1120
1121   t2 = make_aggr_type (BOUND_TEMPLATE_TEMPLATE_PARM);
1122   decl = build_decl (TYPE_DECL, DECL_NAME (decl), NULL_TREE);
1123
1124   /* These nodes have to be created to reflect new TYPE_DECL and template
1125      arguments.  */
1126   TEMPLATE_TYPE_PARM_INDEX (t2) = copy_node (TEMPLATE_TYPE_PARM_INDEX (t));
1127   TEMPLATE_PARM_DECL (TEMPLATE_TYPE_PARM_INDEX (t2)) = decl;
1128   TEMPLATE_TEMPLATE_PARM_TEMPLATE_INFO (t2)
1129     = tree_cons (TEMPLATE_TEMPLATE_PARM_TEMPLATE_DECL (t),
1130                  newargs, NULL_TREE);
1131
1132   TREE_TYPE (decl) = t2;
1133   TYPE_NAME (t2) = decl;
1134   TYPE_STUB_DECL (t2) = decl;
1135   TYPE_SIZE (t2) = 0;
1136   SET_TYPE_STRUCTURAL_EQUALITY (t2);
1137
1138   return t2;
1139 }
1140
1141 /* Called from count_trees via walk_tree.  */
1142
1143 static tree
1144 count_trees_r (tree *tp, int *walk_subtrees, void *data)
1145 {
1146   ++*((int *) data);
1147
1148   if (TYPE_P (*tp))
1149     *walk_subtrees = 0;
1150
1151   return NULL_TREE;
1152 }
1153
1154 /* Debugging function for measuring the rough complexity of a tree
1155    representation.  */
1156
1157 int
1158 count_trees (tree t)
1159 {
1160   int n_trees = 0;
1161   walk_tree_without_duplicates (&t, count_trees_r, &n_trees);
1162   return n_trees;
1163 }
1164
1165 /* Called from verify_stmt_tree via walk_tree.  */
1166
1167 static tree
1168 verify_stmt_tree_r (tree* tp,
1169                     int* walk_subtrees ATTRIBUTE_UNUSED ,
1170                     void* data)
1171 {
1172   tree t = *tp;
1173   htab_t *statements = (htab_t *) data;
1174   void **slot;
1175
1176   if (!STATEMENT_CODE_P (TREE_CODE (t)))
1177     return NULL_TREE;
1178
1179   /* If this statement is already present in the hash table, then
1180      there is a circularity in the statement tree.  */
1181   gcc_assert (!htab_find (*statements, t));
1182
1183   slot = htab_find_slot (*statements, t, INSERT);
1184   *slot = t;
1185
1186   return NULL_TREE;
1187 }
1188
1189 /* Debugging function to check that the statement T has not been
1190    corrupted.  For now, this function simply checks that T contains no
1191    circularities.  */
1192
1193 void
1194 verify_stmt_tree (tree t)
1195 {
1196   htab_t statements;
1197   statements = htab_create (37, htab_hash_pointer, htab_eq_pointer, NULL);
1198   walk_tree (&t, verify_stmt_tree_r, &statements, NULL);
1199   htab_delete (statements);
1200 }
1201
1202 /* Check if the type T depends on a type with no linkage and if so, return
1203    it.  If RELAXED_P then do not consider a class type declared within
1204    a TREE_PUBLIC function to have no linkage.  */
1205
1206 tree
1207 no_linkage_check (tree t, bool relaxed_p)
1208 {
1209   tree r;
1210
1211   /* There's no point in checking linkage on template functions; we
1212      can't know their complete types.  */
1213   if (processing_template_decl)
1214     return NULL_TREE;
1215
1216   switch (TREE_CODE (t))
1217     {
1218       tree fn;
1219
1220     case RECORD_TYPE:
1221       if (TYPE_PTRMEMFUNC_P (t))
1222         goto ptrmem;
1223       /* Fall through.  */
1224     case UNION_TYPE:
1225       if (!CLASS_TYPE_P (t))
1226         return NULL_TREE;
1227       /* Fall through.  */
1228     case ENUMERAL_TYPE:
1229       if (TYPE_ANONYMOUS_P (t))
1230         return t;
1231       fn = decl_function_context (TYPE_MAIN_DECL (t));
1232       if (fn && (!relaxed_p || !TREE_PUBLIC (fn)))
1233         return t;
1234       return NULL_TREE;
1235
1236     case ARRAY_TYPE:
1237     case POINTER_TYPE:
1238     case REFERENCE_TYPE:
1239       return no_linkage_check (TREE_TYPE (t), relaxed_p);
1240
1241     case OFFSET_TYPE:
1242     ptrmem:
1243       r = no_linkage_check (TYPE_PTRMEM_POINTED_TO_TYPE (t),
1244                             relaxed_p);
1245       if (r)
1246         return r;
1247       return no_linkage_check (TYPE_PTRMEM_CLASS_TYPE (t), relaxed_p);
1248
1249     case METHOD_TYPE:
1250       r = no_linkage_check (TYPE_METHOD_BASETYPE (t), relaxed_p);
1251       if (r)
1252         return r;
1253       /* Fall through.  */
1254     case FUNCTION_TYPE:
1255       {
1256         tree parm;
1257         for (parm = TYPE_ARG_TYPES (t);
1258              parm && parm != void_list_node;
1259              parm = TREE_CHAIN (parm))
1260           {
1261             r = no_linkage_check (TREE_VALUE (parm), relaxed_p);
1262             if (r)
1263               return r;
1264           }
1265         return no_linkage_check (TREE_TYPE (t), relaxed_p);
1266       }
1267
1268     default:
1269       return NULL_TREE;
1270     }
1271 }
1272
1273 #ifdef GATHER_STATISTICS
1274 extern int depth_reached;
1275 #endif
1276
1277 void
1278 cxx_print_statistics (void)
1279 {
1280   print_search_statistics ();
1281   print_class_statistics ();
1282 #ifdef GATHER_STATISTICS
1283   fprintf (stderr, "maximum template instantiation depth reached: %d\n",
1284            depth_reached);
1285 #endif
1286 }
1287
1288 /* Return, as an INTEGER_CST node, the number of elements for TYPE
1289    (which is an ARRAY_TYPE).  This counts only elements of the top
1290    array.  */
1291
1292 tree
1293 array_type_nelts_top (tree type)
1294 {
1295   return fold_build2 (PLUS_EXPR, sizetype,
1296                       array_type_nelts (type),
1297                       integer_one_node);
1298 }
1299
1300 /* Return, as an INTEGER_CST node, the number of elements for TYPE
1301    (which is an ARRAY_TYPE).  This one is a recursive count of all
1302    ARRAY_TYPEs that are clumped together.  */
1303
1304 tree
1305 array_type_nelts_total (tree type)
1306 {
1307   tree sz = array_type_nelts_top (type);
1308   type = TREE_TYPE (type);
1309   while (TREE_CODE (type) == ARRAY_TYPE)
1310     {
1311       tree n = array_type_nelts_top (type);
1312       sz = fold_build2 (MULT_EXPR, sizetype, sz, n);
1313       type = TREE_TYPE (type);
1314     }
1315   return sz;
1316 }
1317
1318 /* Called from break_out_target_exprs via mapcar.  */
1319
1320 static tree
1321 bot_manip (tree* tp, int* walk_subtrees, void* data)
1322 {
1323   splay_tree target_remap = ((splay_tree) data);
1324   tree t = *tp;
1325
1326   if (!TYPE_P (t) && TREE_CONSTANT (t))
1327     {
1328       /* There can't be any TARGET_EXPRs or their slot variables below
1329          this point.  We used to check !TREE_SIDE_EFFECTS, but then we
1330          failed to copy an ADDR_EXPR of the slot VAR_DECL.  */
1331       *walk_subtrees = 0;
1332       return NULL_TREE;
1333     }
1334   if (TREE_CODE (t) == TARGET_EXPR)
1335     {
1336       tree u;
1337
1338       if (TREE_CODE (TREE_OPERAND (t, 1)) == AGGR_INIT_EXPR)
1339         u = build_cplus_new
1340           (TREE_TYPE (t), break_out_target_exprs (TREE_OPERAND (t, 1)));
1341       else
1342         u = build_target_expr_with_type
1343           (break_out_target_exprs (TREE_OPERAND (t, 1)), TREE_TYPE (t));
1344
1345       /* Map the old variable to the new one.  */
1346       splay_tree_insert (target_remap,
1347                          (splay_tree_key) TREE_OPERAND (t, 0),
1348                          (splay_tree_value) TREE_OPERAND (u, 0));
1349
1350       /* Replace the old expression with the new version.  */
1351       *tp = u;
1352       /* We don't have to go below this point; the recursive call to
1353          break_out_target_exprs will have handled anything below this
1354          point.  */
1355       *walk_subtrees = 0;
1356       return NULL_TREE;
1357     }
1358
1359   /* Make a copy of this node.  */
1360   return copy_tree_r (tp, walk_subtrees, NULL);
1361 }
1362
1363 /* Replace all remapped VAR_DECLs in T with their new equivalents.
1364    DATA is really a splay-tree mapping old variables to new
1365    variables.  */
1366
1367 static tree
1368 bot_replace (tree* t,
1369              int* walk_subtrees ATTRIBUTE_UNUSED ,
1370              void* data)
1371 {
1372   splay_tree target_remap = ((splay_tree) data);
1373
1374   if (TREE_CODE (*t) == VAR_DECL)
1375     {
1376       splay_tree_node n = splay_tree_lookup (target_remap,
1377                                              (splay_tree_key) *t);
1378       if (n)
1379         *t = (tree) n->value;
1380     }
1381
1382   return NULL_TREE;
1383 }
1384
1385 /* When we parse a default argument expression, we may create
1386    temporary variables via TARGET_EXPRs.  When we actually use the
1387    default-argument expression, we make a copy of the expression, but
1388    we must replace the temporaries with appropriate local versions.  */
1389
1390 tree
1391 break_out_target_exprs (tree t)
1392 {
1393   static int target_remap_count;
1394   static splay_tree target_remap;
1395
1396   if (!target_remap_count++)
1397     target_remap = splay_tree_new (splay_tree_compare_pointers,
1398                                    /*splay_tree_delete_key_fn=*/NULL,
1399                                    /*splay_tree_delete_value_fn=*/NULL);
1400   walk_tree (&t, bot_manip, target_remap, NULL);
1401   walk_tree (&t, bot_replace, target_remap, NULL);
1402
1403   if (!--target_remap_count)
1404     {
1405       splay_tree_delete (target_remap);
1406       target_remap = NULL;
1407     }
1408
1409   return t;
1410 }
1411
1412 /* Similar to `build_nt', but for template definitions of dependent
1413    expressions  */
1414
1415 tree
1416 build_min_nt (enum tree_code code, ...)
1417 {
1418   tree t;
1419   int length;
1420   int i;
1421   va_list p;
1422
1423   va_start (p, code);
1424
1425   t = make_node (code);
1426   length = TREE_CODE_LENGTH (code);
1427
1428   for (i = 0; i < length; i++)
1429     {
1430       tree x = va_arg (p, tree);
1431       TREE_OPERAND (t, i) = x;
1432     }
1433
1434   va_end (p);
1435   return t;
1436 }
1437
1438 /* Similar to `build', but for template definitions.  */
1439
1440 tree
1441 build_min (enum tree_code code, tree tt, ...)
1442 {
1443   tree t;
1444   int length;
1445   int i;
1446   va_list p;
1447
1448   va_start (p, tt);
1449
1450   t = make_node (code);
1451   length = TREE_CODE_LENGTH (code);
1452   TREE_TYPE (t) = tt;
1453
1454   for (i = 0; i < length; i++)
1455     {
1456       tree x = va_arg (p, tree);
1457       TREE_OPERAND (t, i) = x;
1458       if (x && !TYPE_P (x) && TREE_SIDE_EFFECTS (x))
1459         TREE_SIDE_EFFECTS (t) = 1;
1460     }
1461
1462   va_end (p);
1463   return t;
1464 }
1465
1466 /* Similar to `build', but for template definitions of non-dependent
1467    expressions. NON_DEP is the non-dependent expression that has been
1468    built.  */
1469
1470 tree
1471 build_min_non_dep (enum tree_code code, tree non_dep, ...)
1472 {
1473   tree t;
1474   int length;
1475   int i;
1476   va_list p;
1477
1478   va_start (p, non_dep);
1479
1480   t = make_node (code);
1481   length = TREE_CODE_LENGTH (code);
1482   TREE_TYPE (t) = TREE_TYPE (non_dep);
1483   TREE_SIDE_EFFECTS (t) = TREE_SIDE_EFFECTS (non_dep);
1484
1485   for (i = 0; i < length; i++)
1486     {
1487       tree x = va_arg (p, tree);
1488       TREE_OPERAND (t, i) = x;
1489     }
1490
1491   if (code == COMPOUND_EXPR && TREE_CODE (non_dep) != COMPOUND_EXPR)
1492     /* This should not be considered a COMPOUND_EXPR, because it
1493        resolves to an overload.  */
1494     COMPOUND_EXPR_OVERLOADED (t) = 1;
1495
1496   va_end (p);
1497   return t;
1498 }
1499
1500 tree
1501 get_type_decl (tree t)
1502 {
1503   if (TREE_CODE (t) == TYPE_DECL)
1504     return t;
1505   if (TYPE_P (t))
1506     return TYPE_STUB_DECL (t);
1507   gcc_assert (t == error_mark_node);
1508   return t;
1509 }
1510
1511 /* Returns the namespace that contains DECL, whether directly or
1512    indirectly.  */
1513
1514 tree
1515 decl_namespace_context (tree decl)
1516 {
1517   while (1)
1518     {
1519       if (TREE_CODE (decl) == NAMESPACE_DECL)
1520         return decl;
1521       else if (TYPE_P (decl))
1522         decl = CP_DECL_CONTEXT (TYPE_MAIN_DECL (decl));
1523       else
1524         decl = CP_DECL_CONTEXT (decl);
1525     }
1526 }
1527
1528 /* Returns true if decl is within an anonymous namespace, however deeply
1529    nested, or false otherwise.  */
1530
1531 bool
1532 decl_anon_ns_mem_p (tree decl)
1533 {
1534   while (1)
1535     {
1536       if (decl == NULL_TREE || decl == error_mark_node)
1537         return false;
1538       if (TREE_CODE (decl) == NAMESPACE_DECL
1539           && DECL_NAME (decl) == NULL_TREE)
1540         return true;
1541       /* Classes and namespaces inside anonymous namespaces have
1542          TREE_PUBLIC == 0, so we can shortcut the search.  */
1543       else if (TYPE_P (decl))
1544         return (TREE_PUBLIC (TYPE_NAME (decl)) == 0);
1545       else if (TREE_CODE (decl) == NAMESPACE_DECL)
1546         return (TREE_PUBLIC (decl) == 0);
1547       else
1548         decl = DECL_CONTEXT (decl);
1549     }
1550 }
1551
1552 /* Return truthvalue of whether T1 is the same tree structure as T2.
1553    Return 1 if they are the same. Return 0 if they are different.  */
1554
1555 bool
1556 cp_tree_equal (tree t1, tree t2)
1557 {
1558   enum tree_code code1, code2;
1559
1560   if (t1 == t2)
1561     return true;
1562   if (!t1 || !t2)
1563     return false;
1564
1565   for (code1 = TREE_CODE (t1);
1566        code1 == NOP_EXPR || code1 == CONVERT_EXPR
1567          || code1 == NON_LVALUE_EXPR;
1568        code1 = TREE_CODE (t1))
1569     t1 = TREE_OPERAND (t1, 0);
1570   for (code2 = TREE_CODE (t2);
1571        code2 == NOP_EXPR || code2 == CONVERT_EXPR
1572          || code1 == NON_LVALUE_EXPR;
1573        code2 = TREE_CODE (t2))
1574     t2 = TREE_OPERAND (t2, 0);
1575
1576   /* They might have become equal now.  */
1577   if (t1 == t2)
1578     return true;
1579
1580   if (code1 != code2)
1581     return false;
1582
1583   switch (code1)
1584     {
1585     case INTEGER_CST:
1586       return TREE_INT_CST_LOW (t1) == TREE_INT_CST_LOW (t2)
1587         && TREE_INT_CST_HIGH (t1) == TREE_INT_CST_HIGH (t2);
1588
1589     case REAL_CST:
1590       return REAL_VALUES_EQUAL (TREE_REAL_CST (t1), TREE_REAL_CST (t2));
1591
1592     case STRING_CST:
1593       return TREE_STRING_LENGTH (t1) == TREE_STRING_LENGTH (t2)
1594         && !memcmp (TREE_STRING_POINTER (t1), TREE_STRING_POINTER (t2),
1595                     TREE_STRING_LENGTH (t1));
1596
1597     case CONSTRUCTOR:
1598       /* We need to do this when determining whether or not two
1599          non-type pointer to member function template arguments
1600          are the same.  */
1601       if (!(same_type_p (TREE_TYPE (t1), TREE_TYPE (t2))
1602             /* The first operand is RTL.  */
1603             && TREE_OPERAND (t1, 0) == TREE_OPERAND (t2, 0)))
1604         return false;
1605       return cp_tree_equal (TREE_OPERAND (t1, 1), TREE_OPERAND (t2, 1));
1606
1607     case TREE_LIST:
1608       if (!cp_tree_equal (TREE_PURPOSE (t1), TREE_PURPOSE (t2)))
1609         return false;
1610       if (!cp_tree_equal (TREE_VALUE (t1), TREE_VALUE (t2)))
1611         return false;
1612       return cp_tree_equal (TREE_CHAIN (t1), TREE_CHAIN (t2));
1613
1614     case SAVE_EXPR:
1615       return cp_tree_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
1616
1617     case CALL_EXPR:
1618       if (!cp_tree_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0)))
1619         return false;
1620       return cp_tree_equal (TREE_OPERAND (t1, 1), TREE_OPERAND (t2, 1));
1621
1622     case TARGET_EXPR:
1623       {
1624         tree o1 = TREE_OPERAND (t1, 0);
1625         tree o2 = TREE_OPERAND (t2, 0);
1626
1627         /* Special case: if either target is an unallocated VAR_DECL,
1628            it means that it's going to be unified with whatever the
1629            TARGET_EXPR is really supposed to initialize, so treat it
1630            as being equivalent to anything.  */
1631         if (TREE_CODE (o1) == VAR_DECL && DECL_NAME (o1) == NULL_TREE
1632             && !DECL_RTL_SET_P (o1))
1633           /*Nop*/;
1634         else if (TREE_CODE (o2) == VAR_DECL && DECL_NAME (o2) == NULL_TREE
1635                  && !DECL_RTL_SET_P (o2))
1636           /*Nop*/;
1637         else if (!cp_tree_equal (o1, o2))
1638           return false;
1639
1640         return cp_tree_equal (TREE_OPERAND (t1, 1), TREE_OPERAND (t2, 1));
1641       }
1642
1643     case WITH_CLEANUP_EXPR:
1644       if (!cp_tree_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0)))
1645         return false;
1646       return cp_tree_equal (TREE_OPERAND (t1, 1), TREE_OPERAND (t1, 1));
1647
1648     case COMPONENT_REF:
1649       if (TREE_OPERAND (t1, 1) != TREE_OPERAND (t2, 1))
1650         return false;
1651       return cp_tree_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
1652
1653     case VAR_DECL:
1654     case PARM_DECL:
1655     case CONST_DECL:
1656     case FUNCTION_DECL:
1657     case TEMPLATE_DECL:
1658     case IDENTIFIER_NODE:
1659     case SSA_NAME:
1660       return false;
1661
1662     case BASELINK:
1663       return (BASELINK_BINFO (t1) == BASELINK_BINFO (t2)
1664               && BASELINK_ACCESS_BINFO (t1) == BASELINK_ACCESS_BINFO (t2)
1665               && cp_tree_equal (BASELINK_FUNCTIONS (t1),
1666                                 BASELINK_FUNCTIONS (t2)));
1667
1668     case TEMPLATE_PARM_INDEX:
1669       return (TEMPLATE_PARM_IDX (t1) == TEMPLATE_PARM_IDX (t2)
1670               && TEMPLATE_PARM_LEVEL (t1) == TEMPLATE_PARM_LEVEL (t2)
1671               && same_type_p (TREE_TYPE (TEMPLATE_PARM_DECL (t1)),
1672                               TREE_TYPE (TEMPLATE_PARM_DECL (t2))));
1673
1674     case TEMPLATE_ID_EXPR:
1675       {
1676         unsigned ix;
1677         tree vec1, vec2;
1678
1679         if (!cp_tree_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0)))
1680           return false;
1681         vec1 = TREE_OPERAND (t1, 1);
1682         vec2 = TREE_OPERAND (t2, 1);
1683
1684         if (!vec1 || !vec2)
1685           return !vec1 && !vec2;
1686
1687         if (TREE_VEC_LENGTH (vec1) != TREE_VEC_LENGTH (vec2))
1688           return false;
1689
1690         for (ix = TREE_VEC_LENGTH (vec1); ix--;)
1691           if (!cp_tree_equal (TREE_VEC_ELT (vec1, ix),
1692                               TREE_VEC_ELT (vec2, ix)))
1693             return false;
1694
1695         return true;
1696       }
1697
1698     case SIZEOF_EXPR:
1699     case ALIGNOF_EXPR:
1700       {
1701         tree o1 = TREE_OPERAND (t1, 0);
1702         tree o2 = TREE_OPERAND (t2, 0);
1703
1704         if (TREE_CODE (o1) != TREE_CODE (o2))
1705           return false;
1706         if (TYPE_P (o1))
1707           return same_type_p (o1, o2);
1708         else
1709           return cp_tree_equal (o1, o2);
1710       }
1711
1712     case PTRMEM_CST:
1713       /* Two pointer-to-members are the same if they point to the same
1714          field or function in the same class.  */
1715       if (PTRMEM_CST_MEMBER (t1) != PTRMEM_CST_MEMBER (t2))
1716         return false;
1717
1718       return same_type_p (PTRMEM_CST_CLASS (t1), PTRMEM_CST_CLASS (t2));
1719
1720     case OVERLOAD:
1721       if (OVL_FUNCTION (t1) != OVL_FUNCTION (t2))
1722         return false;
1723       return cp_tree_equal (OVL_CHAIN (t1), OVL_CHAIN (t2));
1724
1725     default:
1726       break;
1727     }
1728
1729   switch (TREE_CODE_CLASS (code1))
1730     {
1731     case tcc_unary:
1732     case tcc_binary:
1733     case tcc_comparison:
1734     case tcc_expression:
1735     case tcc_reference:
1736     case tcc_statement:
1737       {
1738         int i;
1739
1740         for (i = 0; i < TREE_CODE_LENGTH (code1); ++i)
1741           if (!cp_tree_equal (TREE_OPERAND (t1, i), TREE_OPERAND (t2, i)))
1742             return false;
1743
1744         return true;
1745       }
1746
1747     case tcc_type:
1748       return same_type_p (t1, t2);
1749     default:
1750       gcc_unreachable ();
1751     }
1752   /* We can get here with --disable-checking.  */
1753   return false;
1754 }
1755
1756 /* The type of ARG when used as an lvalue.  */
1757
1758 tree
1759 lvalue_type (tree arg)
1760 {
1761   tree type = TREE_TYPE (arg);
1762   return type;
1763 }
1764
1765 /* The type of ARG for printing error messages; denote lvalues with
1766    reference types.  */
1767
1768 tree
1769 error_type (tree arg)
1770 {
1771   tree type = TREE_TYPE (arg);
1772
1773   if (TREE_CODE (type) == ARRAY_TYPE)
1774     ;
1775   else if (TREE_CODE (type) == ERROR_MARK)
1776     ;
1777   else if (real_lvalue_p (arg))
1778     type = build_reference_type (lvalue_type (arg));
1779   else if (IS_AGGR_TYPE (type))
1780     type = lvalue_type (arg);
1781
1782   return type;
1783 }
1784
1785 /* Does FUNCTION use a variable-length argument list?  */
1786
1787 int
1788 varargs_function_p (tree function)
1789 {
1790   tree parm = TYPE_ARG_TYPES (TREE_TYPE (function));
1791   for (; parm; parm = TREE_CHAIN (parm))
1792     if (TREE_VALUE (parm) == void_type_node)
1793       return 0;
1794   return 1;
1795 }
1796
1797 /* Returns 1 if decl is a member of a class.  */
1798
1799 int
1800 member_p (tree decl)
1801 {
1802   const tree ctx = DECL_CONTEXT (decl);
1803   return (ctx && TYPE_P (ctx));
1804 }
1805
1806 /* Create a placeholder for member access where we don't actually have an
1807    object that the access is against.  */
1808
1809 tree
1810 build_dummy_object (tree type)
1811 {
1812   tree decl = build1 (NOP_EXPR, build_pointer_type (type), void_zero_node);
1813   return build_indirect_ref (decl, NULL);
1814 }
1815
1816 /* We've gotten a reference to a member of TYPE.  Return *this if appropriate,
1817    or a dummy object otherwise.  If BINFOP is non-0, it is filled with the
1818    binfo path from current_class_type to TYPE, or 0.  */
1819
1820 tree
1821 maybe_dummy_object (tree type, tree* binfop)
1822 {
1823   tree decl, context;
1824   tree binfo;
1825
1826   if (current_class_type
1827       && (binfo = lookup_base (current_class_type, type,
1828                                ba_unique | ba_quiet, NULL)))
1829     context = current_class_type;
1830   else
1831     {
1832       /* Reference from a nested class member function.  */
1833       context = type;
1834       binfo = TYPE_BINFO (type);
1835     }
1836
1837   if (binfop)
1838     *binfop = binfo;
1839
1840   if (current_class_ref && context == current_class_type
1841       /* Kludge: Make sure that current_class_type is actually
1842          correct.  It might not be if we're in the middle of
1843          tsubst_default_argument.  */
1844       && same_type_p (TYPE_MAIN_VARIANT (TREE_TYPE (current_class_ref)),
1845                       current_class_type))
1846     decl = current_class_ref;
1847   else
1848     decl = build_dummy_object (context);
1849
1850   return decl;
1851 }
1852
1853 /* Returns 1 if OB is a placeholder object, or a pointer to one.  */
1854
1855 int
1856 is_dummy_object (tree ob)
1857 {
1858   if (TREE_CODE (ob) == INDIRECT_REF)
1859     ob = TREE_OPERAND (ob, 0);
1860   return (TREE_CODE (ob) == NOP_EXPR
1861           && TREE_OPERAND (ob, 0) == void_zero_node);
1862 }
1863
1864 /* Returns 1 iff type T is a POD type, as defined in [basic.types].  */
1865
1866 int
1867 pod_type_p (tree t)
1868 {
1869   t = strip_array_types (t);
1870
1871   if (t == error_mark_node)
1872     return 1;
1873   if (INTEGRAL_TYPE_P (t))
1874     return 1;  /* integral, character or enumeral type */
1875   if (FLOAT_TYPE_P (t))
1876     return 1;
1877   if (TYPE_PTR_P (t))
1878     return 1; /* pointer to non-member */
1879   if (TYPE_PTR_TO_MEMBER_P (t))
1880     return 1; /* pointer to member */
1881
1882   if (TREE_CODE (t) == VECTOR_TYPE)
1883     return 1; /* vectors are (small) arrays of scalars */
1884
1885   if (! CLASS_TYPE_P (t))
1886     return 0; /* other non-class type (reference or function) */
1887   if (CLASSTYPE_NON_POD_P (t))
1888     return 0;
1889   return 1;
1890 }
1891
1892 /* Returns 1 iff zero initialization of type T means actually storing
1893    zeros in it.  */
1894
1895 int
1896 zero_init_p (tree t)
1897 {
1898   t = strip_array_types (t);
1899
1900   if (t == error_mark_node)
1901     return 1;
1902
1903   /* NULL pointers to data members are initialized with -1.  */
1904   if (TYPE_PTRMEM_P (t))
1905     return 0;
1906
1907   /* Classes that contain types that can't be zero-initialized, cannot
1908      be zero-initialized themselves.  */
1909   if (CLASS_TYPE_P (t) && CLASSTYPE_NON_ZERO_INIT_P (t))
1910     return 0;
1911
1912   return 1;
1913 }
1914
1915 /* Table of valid C++ attributes.  */
1916 const struct attribute_spec cxx_attribute_table[] =
1917 {
1918   /* { name, min_len, max_len, decl_req, type_req, fn_type_req, handler } */
1919   { "java_interface", 0, 0, false, false, false, handle_java_interface_attribute },
1920   { "com_interface",  0, 0, false, false, false, handle_com_interface_attribute },
1921   { "init_priority",  1, 1, true,  false, false, handle_init_priority_attribute },
1922   { NULL,             0, 0, false, false, false, NULL }
1923 };
1924
1925 /* Handle a "java_interface" attribute; arguments as in
1926    struct attribute_spec.handler.  */
1927 static tree
1928 handle_java_interface_attribute (tree* node,
1929                                  tree name,
1930                                  tree args ATTRIBUTE_UNUSED ,
1931                                  int flags,
1932                                  bool* no_add_attrs)
1933 {
1934   if (DECL_P (*node)
1935       || !CLASS_TYPE_P (*node)
1936       || !TYPE_FOR_JAVA (*node))
1937     {
1938       error ("%qE attribute can only be applied to Java class definitions",
1939              name);
1940       *no_add_attrs = true;
1941       return NULL_TREE;
1942     }
1943   if (!(flags & (int) ATTR_FLAG_TYPE_IN_PLACE))
1944     *node = build_variant_type_copy (*node);
1945   TYPE_JAVA_INTERFACE (*node) = 1;
1946
1947   return NULL_TREE;
1948 }
1949
1950 /* Handle a "com_interface" attribute; arguments as in
1951    struct attribute_spec.handler.  */
1952 static tree
1953 handle_com_interface_attribute (tree* node,
1954                                 tree name,
1955                                 tree args ATTRIBUTE_UNUSED ,
1956                                 int flags ATTRIBUTE_UNUSED ,
1957                                 bool* no_add_attrs)
1958 {
1959   static int warned;
1960
1961   *no_add_attrs = true;
1962
1963   if (DECL_P (*node)
1964       || !CLASS_TYPE_P (*node)
1965       || *node != TYPE_MAIN_VARIANT (*node))
1966     {
1967       warning (OPT_Wattributes, "%qE attribute can only be applied "
1968                "to class definitions", name);
1969       return NULL_TREE;
1970     }
1971
1972   if (!warned++)
1973     warning (0, "%qE is obsolete; g++ vtables are now COM-compatible by default",
1974              name);
1975
1976   return NULL_TREE;
1977 }
1978
1979 /* Handle an "init_priority" attribute; arguments as in
1980    struct attribute_spec.handler.  */
1981 static tree
1982 handle_init_priority_attribute (tree* node,
1983                                 tree name,
1984                                 tree args,
1985                                 int flags ATTRIBUTE_UNUSED ,
1986                                 bool* no_add_attrs)
1987 {
1988   tree initp_expr = TREE_VALUE (args);
1989   tree decl = *node;
1990   tree type = TREE_TYPE (decl);
1991   int pri;
1992
1993   STRIP_NOPS (initp_expr);
1994
1995   if (!initp_expr || TREE_CODE (initp_expr) != INTEGER_CST)
1996     {
1997       error ("requested init_priority is not an integer constant");
1998       *no_add_attrs = true;
1999       return NULL_TREE;
2000     }
2001
2002   pri = TREE_INT_CST_LOW (initp_expr);
2003
2004   type = strip_array_types (type);
2005
2006   if (decl == NULL_TREE
2007       || TREE_CODE (decl) != VAR_DECL
2008       || !TREE_STATIC (decl)
2009       || DECL_EXTERNAL (decl)
2010       || (TREE_CODE (type) != RECORD_TYPE
2011           && TREE_CODE (type) != UNION_TYPE)
2012       /* Static objects in functions are initialized the
2013          first time control passes through that
2014          function. This is not precise enough to pin down an
2015          init_priority value, so don't allow it.  */
2016       || current_function_decl)
2017     {
2018       error ("can only use %qE attribute on file-scope definitions "
2019              "of objects of class type", name);
2020       *no_add_attrs = true;
2021       return NULL_TREE;
2022     }
2023
2024   if (pri > MAX_INIT_PRIORITY || pri <= 0)
2025     {
2026       error ("requested init_priority is out of range");
2027       *no_add_attrs = true;
2028       return NULL_TREE;
2029     }
2030
2031   /* Check for init_priorities that are reserved for
2032      language and runtime support implementations.*/
2033   if (pri <= MAX_RESERVED_INIT_PRIORITY)
2034     {
2035       warning
2036         (0, "requested init_priority is reserved for internal use");
2037     }
2038
2039   if (SUPPORTS_INIT_PRIORITY)
2040     {
2041       SET_DECL_INIT_PRIORITY (decl, pri);
2042       DECL_HAS_INIT_PRIORITY_P (decl) = 1;
2043       return NULL_TREE;
2044     }
2045   else
2046     {
2047       error ("%qE attribute is not supported on this platform", name);
2048       *no_add_attrs = true;
2049       return NULL_TREE;
2050     }
2051 }
2052
2053 /* Return a new PTRMEM_CST of the indicated TYPE.  The MEMBER is the
2054    thing pointed to by the constant.  */
2055
2056 tree
2057 make_ptrmem_cst (tree type, tree member)
2058 {
2059   tree ptrmem_cst = make_node (PTRMEM_CST);
2060   TREE_TYPE (ptrmem_cst) = type;
2061   PTRMEM_CST_MEMBER (ptrmem_cst) = member;
2062   return ptrmem_cst;
2063 }
2064
2065 /* Build a variant of TYPE that has the indicated ATTRIBUTES.  May
2066    return an existing type of an appropriate type already exists.  */
2067
2068 tree
2069 cp_build_type_attribute_variant (tree type, tree attributes)
2070 {
2071   tree new_type;
2072
2073   new_type = build_type_attribute_variant (type, attributes);
2074   if (TREE_CODE (new_type) == FUNCTION_TYPE
2075       && (TYPE_RAISES_EXCEPTIONS (new_type)
2076           != TYPE_RAISES_EXCEPTIONS (type)))
2077     new_type = build_exception_variant (new_type,
2078                                         TYPE_RAISES_EXCEPTIONS (type));
2079
2080   /* Making a new main variant of a class type is broken.  */
2081   gcc_assert (!CLASS_TYPE_P (type) || new_type == type);
2082
2083   return new_type;
2084 }
2085
2086 /* Apply FUNC to all language-specific sub-trees of TP in a pre-order
2087    traversal.  Called from walk_tree.  */
2088
2089 tree
2090 cp_walk_subtrees (tree *tp, int *walk_subtrees_p, walk_tree_fn func,
2091                   void *data, struct pointer_set_t *pset)
2092 {
2093   enum tree_code code = TREE_CODE (*tp);
2094   location_t save_locus;
2095   tree result;
2096
2097 #define WALK_SUBTREE(NODE)                              \
2098   do                                                    \
2099     {                                                   \
2100       result = walk_tree (&(NODE), func, data, pset);   \
2101       if (result) goto out;                             \
2102     }                                                   \
2103   while (0)
2104
2105   /* Set input_location here so we get the right instantiation context
2106      if we call instantiate_decl from inlinable_function_p.  */
2107   save_locus = input_location;
2108   if (EXPR_HAS_LOCATION (*tp))
2109     input_location = EXPR_LOCATION (*tp);
2110
2111   /* Not one of the easy cases.  We must explicitly go through the
2112      children.  */
2113   result = NULL_TREE;
2114   switch (code)
2115     {
2116     case DEFAULT_ARG:
2117     case TEMPLATE_TEMPLATE_PARM:
2118     case BOUND_TEMPLATE_TEMPLATE_PARM:
2119     case UNBOUND_CLASS_TEMPLATE:
2120     case TEMPLATE_PARM_INDEX:
2121     case TEMPLATE_TYPE_PARM:
2122     case TYPENAME_TYPE:
2123     case TYPEOF_TYPE:
2124     case BASELINK:
2125       /* None of these have subtrees other than those already walked
2126          above.  */
2127       *walk_subtrees_p = 0;
2128       break;
2129
2130     case TINST_LEVEL:
2131       WALK_SUBTREE (TINST_DECL (*tp));
2132       *walk_subtrees_p = 0;
2133       break;
2134
2135     case PTRMEM_CST:
2136       WALK_SUBTREE (TREE_TYPE (*tp));
2137       *walk_subtrees_p = 0;
2138       break;
2139
2140     case TREE_LIST:
2141       WALK_SUBTREE (TREE_PURPOSE (*tp));
2142       break;
2143
2144     case OVERLOAD:
2145       WALK_SUBTREE (OVL_FUNCTION (*tp));
2146       WALK_SUBTREE (OVL_CHAIN (*tp));
2147       *walk_subtrees_p = 0;
2148       break;
2149
2150     case RECORD_TYPE:
2151       if (TYPE_PTRMEMFUNC_P (*tp))
2152         WALK_SUBTREE (TYPE_PTRMEMFUNC_FN_TYPE (*tp));
2153       break;
2154
2155     default:
2156       input_location = save_locus;
2157       return NULL_TREE;
2158     }
2159
2160   /* We didn't find what we were looking for.  */
2161  out:
2162   input_location = save_locus;
2163   return result;
2164
2165 #undef WALK_SUBTREE
2166 }
2167
2168 /* Decide whether there are language-specific reasons to not inline a
2169    function as a tree.  */
2170
2171 int
2172 cp_cannot_inline_tree_fn (tree* fnp)
2173 {
2174   tree fn = *fnp;
2175
2176   /* We can inline a template instantiation only if it's fully
2177      instantiated.  */
2178   if (DECL_TEMPLATE_INFO (fn)
2179       && TI_PENDING_TEMPLATE_FLAG (DECL_TEMPLATE_INFO (fn)))
2180     {
2181       /* Don't instantiate functions that are not going to be
2182          inlined.  */
2183       if (!DECL_INLINE (DECL_TEMPLATE_RESULT
2184                         (template_for_substitution (fn))))
2185         return 1;
2186
2187       fn = *fnp = instantiate_decl (fn, /*defer_ok=*/0, /*undefined_ok=*/0);
2188
2189       if (TI_PENDING_TEMPLATE_FLAG (DECL_TEMPLATE_INFO (fn)))
2190         return 1;
2191     }
2192
2193   if (flag_really_no_inline
2194       && lookup_attribute ("always_inline", DECL_ATTRIBUTES (fn)) == NULL)
2195     return 1;
2196
2197   /* Don't auto-inline anything that might not be bound within
2198      this unit of translation.
2199      Exclude comdat functions from this rule.  While they can be bound
2200      to the other unit, they all must be the same.  This is especially
2201      important so templates can inline.  */
2202   if (!DECL_DECLARED_INLINE_P (fn) && !(*targetm.binds_local_p) (fn)
2203       && !DECL_COMDAT (fn))
2204     {
2205       DECL_UNINLINABLE (fn) = 1;
2206       return 1;
2207     }
2208
2209   if (varargs_function_p (fn))
2210     {
2211       DECL_UNINLINABLE (fn) = 1;
2212       return 1;
2213     }
2214
2215   if (! function_attribute_inlinable_p (fn))
2216     {
2217       DECL_UNINLINABLE (fn) = 1;
2218       return 1;
2219     }
2220
2221   return 0;
2222 }
2223
2224 /* Add any pending functions other than the current function (already
2225    handled by the caller), that thus cannot be inlined, to FNS_P, then
2226    return the latest function added to the array, PREV_FN.  */
2227
2228 tree
2229 cp_add_pending_fn_decls (void* fns_p, tree prev_fn)
2230 {
2231   varray_type *fnsp = (varray_type *)fns_p;
2232   struct saved_scope *s;
2233
2234   for (s = scope_chain; s; s = s->prev)
2235     if (s->function_decl && s->function_decl != prev_fn)
2236       {
2237         VARRAY_PUSH_TREE (*fnsp, s->function_decl);
2238         prev_fn = s->function_decl;
2239       }
2240
2241   return prev_fn;
2242 }
2243
2244 /* Determine whether VAR is a declaration of an automatic variable in
2245    function FN.  */
2246
2247 int
2248 cp_auto_var_in_fn_p (tree var, tree fn)
2249 {
2250   return (DECL_P (var) && DECL_CONTEXT (var) == fn
2251           && nonstatic_local_decl_p (var));
2252 }
2253
2254 /* Like save_expr, but for C++.  */
2255
2256 tree
2257 cp_save_expr (tree expr)
2258 {
2259   /* There is no reason to create a SAVE_EXPR within a template; if
2260      needed, we can create the SAVE_EXPR when instantiating the
2261      template.  Furthermore, the middle-end cannot handle C++-specific
2262      tree codes.  */
2263   if (processing_template_decl)
2264     return expr;
2265   return save_expr (expr);
2266 }
2267
2268 /* Initialize tree.c.  */
2269
2270 void
2271 init_tree (void)
2272 {
2273   list_hash_table = htab_create_ggc (31, list_hash, list_hash_eq, NULL);
2274 }
2275
2276 /* Returns the kind of special function that DECL (a FUNCTION_DECL)
2277    is.  Note that sfk_none is zero, so this function can be used as a
2278    predicate to test whether or not DECL is a special function.  */
2279
2280 special_function_kind
2281 special_function_p (tree decl)
2282 {
2283   /* Rather than doing all this stuff with magic names, we should
2284      probably have a field of type `special_function_kind' in
2285      DECL_LANG_SPECIFIC.  */
2286   if (DECL_COPY_CONSTRUCTOR_P (decl))
2287     return sfk_copy_constructor;
2288   if (DECL_CONSTRUCTOR_P (decl))
2289     return sfk_constructor;
2290   if (DECL_OVERLOADED_OPERATOR_P (decl) == NOP_EXPR)
2291     return sfk_assignment_operator;
2292   if (DECL_MAYBE_IN_CHARGE_DESTRUCTOR_P (decl))
2293     return sfk_destructor;
2294   if (DECL_COMPLETE_DESTRUCTOR_P (decl))
2295     return sfk_complete_destructor;
2296   if (DECL_BASE_DESTRUCTOR_P (decl))
2297     return sfk_base_destructor;
2298   if (DECL_DELETING_DESTRUCTOR_P (decl))
2299     return sfk_deleting_destructor;
2300   if (DECL_CONV_FN_P (decl))
2301     return sfk_conversion;
2302
2303   return sfk_none;
2304 }
2305
2306 /* Returns nonzero if TYPE is a character type, including wchar_t.  */
2307
2308 int
2309 char_type_p (tree type)
2310 {
2311   return (same_type_p (type, char_type_node)
2312           || same_type_p (type, unsigned_char_type_node)
2313           || same_type_p (type, signed_char_type_node)
2314           || same_type_p (type, wchar_type_node));
2315 }
2316
2317 /* Returns the kind of linkage associated with the indicated DECL.  Th
2318    value returned is as specified by the language standard; it is
2319    independent of implementation details regarding template
2320    instantiation, etc.  For example, it is possible that a declaration
2321    to which this function assigns external linkage would not show up
2322    as a global symbol when you run `nm' on the resulting object file.  */
2323
2324 linkage_kind
2325 decl_linkage (tree decl)
2326 {
2327   /* This function doesn't attempt to calculate the linkage from first
2328      principles as given in [basic.link].  Instead, it makes use of
2329      the fact that we have already set TREE_PUBLIC appropriately, and
2330      then handles a few special cases.  Ideally, we would calculate
2331      linkage first, and then transform that into a concrete
2332      implementation.  */
2333
2334   /* Things that don't have names have no linkage.  */
2335   if (!DECL_NAME (decl))
2336     return lk_none;
2337
2338   /* Things that are TREE_PUBLIC have external linkage.  */
2339   if (TREE_PUBLIC (decl))
2340     return lk_external;
2341
2342   if (TREE_CODE (decl) == NAMESPACE_DECL)
2343     return lk_external;
2344
2345   /* Linkage of a CONST_DECL depends on the linkage of the enumeration
2346      type.  */
2347   if (TREE_CODE (decl) == CONST_DECL)
2348     return decl_linkage (TYPE_NAME (TREE_TYPE (decl)));
2349
2350   /* Some things that are not TREE_PUBLIC have external linkage, too.
2351      For example, on targets that don't have weak symbols, we make all
2352      template instantiations have internal linkage (in the object
2353      file), but the symbols should still be treated as having external
2354      linkage from the point of view of the language.  */
2355   if (TREE_CODE (decl) != TYPE_DECL && DECL_LANG_SPECIFIC (decl)
2356       && DECL_COMDAT (decl))
2357     return lk_external;
2358
2359   /* Things in local scope do not have linkage, if they don't have
2360      TREE_PUBLIC set.  */
2361   if (decl_function_context (decl))
2362     return lk_none;
2363
2364   /* Members of the anonymous namespace also have TREE_PUBLIC unset, but
2365      are considered to have external linkage for language purposes.  DECLs
2366      really meant to have internal linkage have DECL_THIS_STATIC set.  */
2367   if (TREE_CODE (decl) == TYPE_DECL
2368       || ((TREE_CODE (decl) == VAR_DECL || TREE_CODE (decl) == FUNCTION_DECL)
2369           && !DECL_THIS_STATIC (decl)))
2370     return lk_external;
2371
2372   /* Everything else has internal linkage.  */
2373   return lk_internal;
2374 }
2375 \f
2376 /* EXP is an expression that we want to pre-evaluate.  Returns (in
2377    *INITP) an expression that will perform the pre-evaluation.  The
2378    value returned by this function is a side-effect free expression
2379    equivalent to the pre-evaluated expression.  Callers must ensure
2380    that *INITP is evaluated before EXP.  */
2381
2382 tree
2383 stabilize_expr (tree exp, tree* initp)
2384 {
2385   tree init_expr;
2386
2387   if (!TREE_SIDE_EFFECTS (exp))
2388     init_expr = NULL_TREE;
2389   else if (!real_lvalue_p (exp)
2390            || !TYPE_NEEDS_CONSTRUCTING (TREE_TYPE (exp)))
2391     {
2392       init_expr = get_target_expr (exp);
2393       exp = TARGET_EXPR_SLOT (init_expr);
2394     }
2395   else
2396     {
2397       exp = build_unary_op (ADDR_EXPR, exp, 1);
2398       init_expr = get_target_expr (exp);
2399       exp = TARGET_EXPR_SLOT (init_expr);
2400       exp = build_indirect_ref (exp, 0);
2401     }
2402   *initp = init_expr;
2403
2404   gcc_assert (!TREE_SIDE_EFFECTS (exp));
2405   return exp;
2406 }
2407
2408 /* Add NEW, an expression whose value we don't care about, after the
2409    similar expression ORIG.  */
2410
2411 tree
2412 add_stmt_to_compound (tree orig, tree new)
2413 {
2414   if (!new || !TREE_SIDE_EFFECTS (new))
2415     return orig;
2416   if (!orig || !TREE_SIDE_EFFECTS (orig))
2417     return new;
2418   return build2 (COMPOUND_EXPR, void_type_node, orig, new);
2419 }
2420
2421 /* Like stabilize_expr, but for a call whose arguments we want to
2422    pre-evaluate.  CALL is modified in place to use the pre-evaluated
2423    arguments, while, upon return, *INITP contains an expression to
2424    compute the arguments.  */
2425
2426 void
2427 stabilize_call (tree call, tree *initp)
2428 {
2429   tree inits = NULL_TREE;
2430   tree t;
2431
2432   if (call == error_mark_node)
2433     return;
2434
2435   gcc_assert (TREE_CODE (call) == CALL_EXPR
2436               || TREE_CODE (call) == AGGR_INIT_EXPR);
2437
2438   for (t = TREE_OPERAND (call, 1); t; t = TREE_CHAIN (t))
2439     if (TREE_SIDE_EFFECTS (TREE_VALUE (t)))
2440       {
2441         tree init;
2442         TREE_VALUE (t) = stabilize_expr (TREE_VALUE (t), &init);
2443         inits = add_stmt_to_compound (inits, init);
2444       }
2445
2446   *initp = inits;
2447 }
2448
2449 /* Like stabilize_expr, but for an initialization.
2450
2451    If the initialization is for an object of class type, this function
2452    takes care not to introduce additional temporaries.
2453
2454    Returns TRUE iff the expression was successfully pre-evaluated,
2455    i.e., if INIT is now side-effect free, except for, possible, a
2456    single call to a constructor.  */
2457
2458 bool
2459 stabilize_init (tree init, tree *initp)
2460 {
2461   tree t = init;
2462
2463   *initp = NULL_TREE;
2464
2465   if (t == error_mark_node)
2466     return true;
2467
2468   if (TREE_CODE (t) == INIT_EXPR
2469       && TREE_CODE (TREE_OPERAND (t, 1)) != TARGET_EXPR)
2470     {
2471       TREE_OPERAND (t, 1) = stabilize_expr (TREE_OPERAND (t, 1), initp);
2472       return true;
2473     }
2474
2475   if (TREE_CODE (t) == INIT_EXPR)
2476     t = TREE_OPERAND (t, 1);
2477   if (TREE_CODE (t) == TARGET_EXPR)
2478     t = TARGET_EXPR_INITIAL (t);
2479   if (TREE_CODE (t) == COMPOUND_EXPR)
2480     t = expr_last (t);
2481   if (TREE_CODE (t) == CONSTRUCTOR
2482       && EMPTY_CONSTRUCTOR_P (t))
2483     /* Default-initialization.  */
2484     return true;
2485
2486   /* If the initializer is a COND_EXPR, we can't preevaluate
2487      anything.  */
2488   if (TREE_CODE (t) == COND_EXPR)
2489     return false;
2490
2491   if (TREE_CODE (t) == CALL_EXPR
2492       || TREE_CODE (t) == AGGR_INIT_EXPR)
2493     {
2494       stabilize_call (t, initp);
2495       return true;
2496     }
2497
2498   /* The initialization is being performed via a bitwise copy -- and
2499      the item copied may have side effects.  */
2500   return TREE_SIDE_EFFECTS (init);
2501 }
2502
2503 /* Like "fold", but should be used whenever we might be processing the
2504    body of a template.  */
2505
2506 tree
2507 fold_if_not_in_template (tree expr)
2508 {
2509   /* In the body of a template, there is never any need to call
2510      "fold".  We will call fold later when actually instantiating the
2511      template.  Integral constant expressions in templates will be
2512      evaluated via fold_non_dependent_expr, as necessary.  */
2513   if (processing_template_decl)
2514     return expr;
2515
2516   /* Fold C++ front-end specific tree codes.  */
2517   if (TREE_CODE (expr) == UNARY_PLUS_EXPR)
2518     return fold_convert (TREE_TYPE (expr), TREE_OPERAND (expr, 0));
2519
2520   return fold (expr);
2521 }
2522
2523 /* Returns true if a cast to TYPE may appear in an integral constant
2524    expression.  */
2525
2526 bool
2527 cast_valid_in_integral_constant_expression_p (tree type)
2528 {
2529   return (INTEGRAL_OR_ENUMERATION_TYPE_P (type)
2530           || dependent_type_p (type)
2531           || type == error_mark_node);
2532 }
2533
2534 \f
2535 #if defined ENABLE_TREE_CHECKING && (GCC_VERSION >= 2007)
2536 /* Complain that some language-specific thing hanging off a tree
2537    node has been accessed improperly.  */
2538
2539 void
2540 lang_check_failed (const char* file, int line, const char* function)
2541 {
2542   internal_error ("lang_* check: failed in %s, at %s:%d",
2543                   function, trim_filename (file), line);
2544 }
2545 #endif /* ENABLE_TREE_CHECKING */
2546
2547 #include "gt-cp-tree.h"