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