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