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 PARM_DECL:
1861       /* For comparing uses of parameters in late-specified return types
1862          with an out-of-class definition of the function.  */
1863       if ((!DECL_CONTEXT (t1) || !DECL_CONTEXT (t2))
1864           && same_type_p (TREE_TYPE (t1), TREE_TYPE (t2))
1865           && DECL_NAME (t1) == DECL_NAME (t2))
1866         return true;
1867       else
1868         return false;
1869
1870     case VAR_DECL:
1871     case CONST_DECL:
1872     case FUNCTION_DECL:
1873     case TEMPLATE_DECL:
1874     case IDENTIFIER_NODE:
1875     case SSA_NAME:
1876       return false;
1877
1878     case BASELINK:
1879       return (BASELINK_BINFO (t1) == BASELINK_BINFO (t2)
1880               && BASELINK_ACCESS_BINFO (t1) == BASELINK_ACCESS_BINFO (t2)
1881               && cp_tree_equal (BASELINK_FUNCTIONS (t1),
1882                                 BASELINK_FUNCTIONS (t2)));
1883
1884     case TEMPLATE_PARM_INDEX:
1885       return (TEMPLATE_PARM_IDX (t1) == TEMPLATE_PARM_IDX (t2)
1886               && TEMPLATE_PARM_LEVEL (t1) == TEMPLATE_PARM_LEVEL (t2)
1887               && same_type_p (TREE_TYPE (TEMPLATE_PARM_DECL (t1)),
1888                               TREE_TYPE (TEMPLATE_PARM_DECL (t2))));
1889
1890     case TEMPLATE_ID_EXPR:
1891       {
1892         unsigned ix;
1893         tree vec1, vec2;
1894
1895         if (!cp_tree_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0)))
1896           return false;
1897         vec1 = TREE_OPERAND (t1, 1);
1898         vec2 = TREE_OPERAND (t2, 1);
1899
1900         if (!vec1 || !vec2)
1901           return !vec1 && !vec2;
1902
1903         if (TREE_VEC_LENGTH (vec1) != TREE_VEC_LENGTH (vec2))
1904           return false;
1905
1906         for (ix = TREE_VEC_LENGTH (vec1); ix--;)
1907           if (!cp_tree_equal (TREE_VEC_ELT (vec1, ix),
1908                               TREE_VEC_ELT (vec2, ix)))
1909             return false;
1910
1911         return true;
1912       }
1913
1914     case SIZEOF_EXPR:
1915     case ALIGNOF_EXPR:
1916       {
1917         tree o1 = TREE_OPERAND (t1, 0);
1918         tree o2 = TREE_OPERAND (t2, 0);
1919
1920         if (TREE_CODE (o1) != TREE_CODE (o2))
1921           return false;
1922         if (TYPE_P (o1))
1923           return same_type_p (o1, o2);
1924         else
1925           return cp_tree_equal (o1, o2);
1926       }
1927
1928     case MODOP_EXPR:
1929       {
1930         tree t1_op1, t2_op1;
1931
1932         if (!cp_tree_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0)))
1933           return false;
1934
1935         t1_op1 = TREE_OPERAND (t1, 1);
1936         t2_op1 = TREE_OPERAND (t2, 1);
1937         if (TREE_CODE (t1_op1) != TREE_CODE (t2_op1))
1938           return false;
1939
1940         return cp_tree_equal (TREE_OPERAND (t1, 2), TREE_OPERAND (t2, 2));
1941       }
1942
1943     case PTRMEM_CST:
1944       /* Two pointer-to-members are the same if they point to the same
1945          field or function in the same class.  */
1946       if (PTRMEM_CST_MEMBER (t1) != PTRMEM_CST_MEMBER (t2))
1947         return false;
1948
1949       return same_type_p (PTRMEM_CST_CLASS (t1), PTRMEM_CST_CLASS (t2));
1950
1951     case OVERLOAD:
1952       if (OVL_FUNCTION (t1) != OVL_FUNCTION (t2))
1953         return false;
1954       return cp_tree_equal (OVL_CHAIN (t1), OVL_CHAIN (t2));
1955
1956     case TRAIT_EXPR:
1957       if (TRAIT_EXPR_KIND (t1) != TRAIT_EXPR_KIND (t2))
1958         return false;
1959       return same_type_p (TRAIT_EXPR_TYPE1 (t1), TRAIT_EXPR_TYPE1 (t2))
1960         && same_type_p (TRAIT_EXPR_TYPE2 (t1), TRAIT_EXPR_TYPE2 (t2));
1961
1962     default:
1963       break;
1964     }
1965
1966   switch (TREE_CODE_CLASS (code1))
1967     {
1968     case tcc_unary:
1969     case tcc_binary:
1970     case tcc_comparison:
1971     case tcc_expression:
1972     case tcc_vl_exp:
1973     case tcc_reference:
1974     case tcc_statement:
1975       {
1976         int i, n;
1977
1978         n = TREE_OPERAND_LENGTH (t1);
1979         if (TREE_CODE_CLASS (code1) == tcc_vl_exp
1980             && n != TREE_OPERAND_LENGTH (t2))
1981           return false;
1982
1983         for (i = 0; i < n; ++i)
1984           if (!cp_tree_equal (TREE_OPERAND (t1, i), TREE_OPERAND (t2, i)))
1985             return false;
1986
1987         return true;
1988       }
1989
1990     case tcc_type:
1991       return same_type_p (t1, t2);
1992     default:
1993       gcc_unreachable ();
1994     }
1995   /* We can get here with --disable-checking.  */
1996   return false;
1997 }
1998
1999 /* The type of ARG when used as an lvalue.  */
2000
2001 tree
2002 lvalue_type (tree arg)
2003 {
2004   tree type = TREE_TYPE (arg);
2005   return type;
2006 }
2007
2008 /* The type of ARG for printing error messages; denote lvalues with
2009    reference types.  */
2010
2011 tree
2012 error_type (tree arg)
2013 {
2014   tree type = TREE_TYPE (arg);
2015
2016   if (TREE_CODE (type) == ARRAY_TYPE)
2017     ;
2018   else if (TREE_CODE (type) == ERROR_MARK)
2019     ;
2020   else if (real_lvalue_p (arg))
2021     type = build_reference_type (lvalue_type (arg));
2022   else if (MAYBE_CLASS_TYPE_P (type))
2023     type = lvalue_type (arg);
2024
2025   return type;
2026 }
2027
2028 /* Does FUNCTION use a variable-length argument list?  */
2029
2030 int
2031 varargs_function_p (const_tree function)
2032 {
2033   const_tree parm = TYPE_ARG_TYPES (TREE_TYPE (function));
2034   for (; parm; parm = TREE_CHAIN (parm))
2035     if (TREE_VALUE (parm) == void_type_node)
2036       return 0;
2037   return 1;
2038 }
2039
2040 /* Returns 1 if decl is a member of a class.  */
2041
2042 int
2043 member_p (const_tree decl)
2044 {
2045   const_tree const ctx = DECL_CONTEXT (decl);
2046   return (ctx && TYPE_P (ctx));
2047 }
2048
2049 /* Create a placeholder for member access where we don't actually have an
2050    object that the access is against.  */
2051
2052 tree
2053 build_dummy_object (tree type)
2054 {
2055   tree decl = build1 (NOP_EXPR, build_pointer_type (type), void_zero_node);
2056   return cp_build_indirect_ref (decl, NULL, tf_warning_or_error);
2057 }
2058
2059 /* We've gotten a reference to a member of TYPE.  Return *this if appropriate,
2060    or a dummy object otherwise.  If BINFOP is non-0, it is filled with the
2061    binfo path from current_class_type to TYPE, or 0.  */
2062
2063 tree
2064 maybe_dummy_object (tree type, tree* binfop)
2065 {
2066   tree decl, context;
2067   tree binfo;
2068
2069   if (current_class_type
2070       && (binfo = lookup_base (current_class_type, type,
2071                                ba_unique | ba_quiet, NULL)))
2072     context = current_class_type;
2073   else
2074     {
2075       /* Reference from a nested class member function.  */
2076       context = type;
2077       binfo = TYPE_BINFO (type);
2078     }
2079
2080   if (binfop)
2081     *binfop = binfo;
2082
2083   if (current_class_ref && context == current_class_type
2084       /* Kludge: Make sure that current_class_type is actually
2085          correct.  It might not be if we're in the middle of
2086          tsubst_default_argument.  */
2087       && same_type_p (TYPE_MAIN_VARIANT (TREE_TYPE (current_class_ref)),
2088                       current_class_type))
2089     decl = current_class_ref;
2090   else
2091     decl = build_dummy_object (context);
2092
2093   return decl;
2094 }
2095
2096 /* Returns 1 if OB is a placeholder object, or a pointer to one.  */
2097
2098 int
2099 is_dummy_object (const_tree ob)
2100 {
2101   if (TREE_CODE (ob) == INDIRECT_REF)
2102     ob = TREE_OPERAND (ob, 0);
2103   return (TREE_CODE (ob) == NOP_EXPR
2104           && TREE_OPERAND (ob, 0) == void_zero_node);
2105 }
2106
2107 /* Returns 1 iff type T is a POD type, as defined in [basic.types].  */
2108
2109 int
2110 pod_type_p (const_tree t)
2111 {
2112   /* This CONST_CAST is okay because strip_array_types returns its
2113      argument unmodified and we assign it to a const_tree.  */
2114   t = strip_array_types (CONST_CAST_TREE(t));
2115
2116   if (t == error_mark_node)
2117     return 1;
2118   if (INTEGRAL_TYPE_P (t))
2119     return 1;  /* integral, character or enumeral type */
2120   if (FLOAT_TYPE_P (t))
2121     return 1;
2122   if (TYPE_PTR_P (t))
2123     return 1; /* pointer to non-member */
2124   if (TYPE_PTR_TO_MEMBER_P (t))
2125     return 1; /* pointer to member */
2126
2127   if (TREE_CODE (t) == VECTOR_TYPE)
2128     return 1; /* vectors are (small) arrays of scalars */
2129
2130   if (! RECORD_OR_UNION_CODE_P (TREE_CODE (t)))
2131     return 0; /* other non-class type (reference or function) */
2132   if (! CLASS_TYPE_P (t))
2133     return 1; /* struct created by the back end */
2134   if (CLASSTYPE_NON_POD_P (t))
2135     return 0;
2136   return 1;
2137 }
2138
2139 /* Nonzero iff type T is a class template implicit specialization.  */
2140
2141 bool
2142 class_tmpl_impl_spec_p (const_tree t)
2143 {
2144   return CLASS_TYPE_P (t) && CLASSTYPE_TEMPLATE_INSTANTIATION (t);
2145 }
2146
2147 /* Returns 1 iff zero initialization of type T means actually storing
2148    zeros in it.  */
2149
2150 int
2151 zero_init_p (const_tree t)
2152 {
2153   /* This CONST_CAST is okay because strip_array_types returns its
2154      argument unmodified and we assign it to a const_tree.  */
2155   t = strip_array_types (CONST_CAST_TREE(t));
2156
2157   if (t == error_mark_node)
2158     return 1;
2159
2160   /* NULL pointers to data members are initialized with -1.  */
2161   if (TYPE_PTRMEM_P (t))
2162     return 0;
2163
2164   /* Classes that contain types that can't be zero-initialized, cannot
2165      be zero-initialized themselves.  */
2166   if (CLASS_TYPE_P (t) && CLASSTYPE_NON_ZERO_INIT_P (t))
2167     return 0;
2168
2169   return 1;
2170 }
2171
2172 /* Table of valid C++ attributes.  */
2173 const struct attribute_spec cxx_attribute_table[] =
2174 {
2175   /* { name, min_len, max_len, decl_req, type_req, fn_type_req, handler } */
2176   { "java_interface", 0, 0, false, false, false, handle_java_interface_attribute },
2177   { "com_interface",  0, 0, false, false, false, handle_com_interface_attribute },
2178   { "init_priority",  1, 1, true,  false, false, handle_init_priority_attribute },
2179   { NULL,             0, 0, false, false, false, NULL }
2180 };
2181
2182 /* Handle a "java_interface" attribute; arguments as in
2183    struct attribute_spec.handler.  */
2184 static tree
2185 handle_java_interface_attribute (tree* node,
2186                                  tree name,
2187                                  tree args ATTRIBUTE_UNUSED ,
2188                                  int flags,
2189                                  bool* no_add_attrs)
2190 {
2191   if (DECL_P (*node)
2192       || !CLASS_TYPE_P (*node)
2193       || !TYPE_FOR_JAVA (*node))
2194     {
2195       error ("%qE attribute can only be applied to Java class definitions",
2196              name);
2197       *no_add_attrs = true;
2198       return NULL_TREE;
2199     }
2200   if (!(flags & (int) ATTR_FLAG_TYPE_IN_PLACE))
2201     *node = build_variant_type_copy (*node);
2202   TYPE_JAVA_INTERFACE (*node) = 1;
2203
2204   return NULL_TREE;
2205 }
2206
2207 /* Handle a "com_interface" attribute; arguments as in
2208    struct attribute_spec.handler.  */
2209 static tree
2210 handle_com_interface_attribute (tree* node,
2211                                 tree name,
2212                                 tree args ATTRIBUTE_UNUSED ,
2213                                 int flags ATTRIBUTE_UNUSED ,
2214                                 bool* no_add_attrs)
2215 {
2216   static int warned;
2217
2218   *no_add_attrs = true;
2219
2220   if (DECL_P (*node)
2221       || !CLASS_TYPE_P (*node)
2222       || *node != TYPE_MAIN_VARIANT (*node))
2223     {
2224       warning (OPT_Wattributes, "%qE attribute can only be applied "
2225                "to class definitions", name);
2226       return NULL_TREE;
2227     }
2228
2229   if (!warned++)
2230     warning (0, "%qE is obsolete; g++ vtables are now COM-compatible by default",
2231              name);
2232
2233   return NULL_TREE;
2234 }
2235
2236 /* Handle an "init_priority" attribute; arguments as in
2237    struct attribute_spec.handler.  */
2238 static tree
2239 handle_init_priority_attribute (tree* node,
2240                                 tree name,
2241                                 tree args,
2242                                 int flags ATTRIBUTE_UNUSED ,
2243                                 bool* no_add_attrs)
2244 {
2245   tree initp_expr = TREE_VALUE (args);
2246   tree decl = *node;
2247   tree type = TREE_TYPE (decl);
2248   int pri;
2249
2250   STRIP_NOPS (initp_expr);
2251
2252   if (!initp_expr || TREE_CODE (initp_expr) != INTEGER_CST)
2253     {
2254       error ("requested init_priority is not an integer constant");
2255       *no_add_attrs = true;
2256       return NULL_TREE;
2257     }
2258
2259   pri = TREE_INT_CST_LOW (initp_expr);
2260
2261   type = strip_array_types (type);
2262
2263   if (decl == NULL_TREE
2264       || TREE_CODE (decl) != VAR_DECL
2265       || !TREE_STATIC (decl)
2266       || DECL_EXTERNAL (decl)
2267       || (TREE_CODE (type) != RECORD_TYPE
2268           && TREE_CODE (type) != UNION_TYPE)
2269       /* Static objects in functions are initialized the
2270          first time control passes through that
2271          function. This is not precise enough to pin down an
2272          init_priority value, so don't allow it.  */
2273       || current_function_decl)
2274     {
2275       error ("can only use %qE attribute on file-scope definitions "
2276              "of objects of class type", name);
2277       *no_add_attrs = true;
2278       return NULL_TREE;
2279     }
2280
2281   if (pri > MAX_INIT_PRIORITY || pri <= 0)
2282     {
2283       error ("requested init_priority is out of range");
2284       *no_add_attrs = true;
2285       return NULL_TREE;
2286     }
2287
2288   /* Check for init_priorities that are reserved for
2289      language and runtime support implementations.*/
2290   if (pri <= MAX_RESERVED_INIT_PRIORITY)
2291     {
2292       warning
2293         (0, "requested init_priority is reserved for internal use");
2294     }
2295
2296   if (SUPPORTS_INIT_PRIORITY)
2297     {
2298       SET_DECL_INIT_PRIORITY (decl, pri);
2299       DECL_HAS_INIT_PRIORITY_P (decl) = 1;
2300       return NULL_TREE;
2301     }
2302   else
2303     {
2304       error ("%qE attribute is not supported on this platform", name);
2305       *no_add_attrs = true;
2306       return NULL_TREE;
2307     }
2308 }
2309
2310 /* Return a new PTRMEM_CST of the indicated TYPE.  The MEMBER is the
2311    thing pointed to by the constant.  */
2312
2313 tree
2314 make_ptrmem_cst (tree type, tree member)
2315 {
2316   tree ptrmem_cst = make_node (PTRMEM_CST);
2317   TREE_TYPE (ptrmem_cst) = type;
2318   PTRMEM_CST_MEMBER (ptrmem_cst) = member;
2319   return ptrmem_cst;
2320 }
2321
2322 /* Build a variant of TYPE that has the indicated ATTRIBUTES.  May
2323    return an existing type if an appropriate type already exists.  */
2324
2325 tree
2326 cp_build_type_attribute_variant (tree type, tree attributes)
2327 {
2328   tree new_type;
2329
2330   new_type = build_type_attribute_variant (type, attributes);
2331   if (TREE_CODE (new_type) == FUNCTION_TYPE
2332       && (TYPE_RAISES_EXCEPTIONS (new_type)
2333           != TYPE_RAISES_EXCEPTIONS (type)))
2334     new_type = build_exception_variant (new_type,
2335                                         TYPE_RAISES_EXCEPTIONS (type));
2336
2337   /* Making a new main variant of a class type is broken.  */
2338   gcc_assert (!CLASS_TYPE_P (type) || new_type == type);
2339
2340   return new_type;
2341 }
2342
2343 /* Return TRUE if TYPE1 and TYPE2 are identical for type hashing purposes.
2344    Called only after doing all language independent checks.  Only
2345    to check TYPE_RAISES_EXCEPTIONS for FUNCTION_TYPE, the rest is already
2346    compared in type_hash_eq.  */
2347
2348 bool
2349 cxx_type_hash_eq (const_tree typea, const_tree typeb)
2350 {
2351   gcc_assert (TREE_CODE (typea) == FUNCTION_TYPE);
2352
2353   return comp_except_specs (TYPE_RAISES_EXCEPTIONS (typea),
2354                             TYPE_RAISES_EXCEPTIONS (typeb), 1);
2355 }
2356
2357 /* Apply FUNC to all language-specific sub-trees of TP in a pre-order
2358    traversal.  Called from walk_tree.  */
2359
2360 tree
2361 cp_walk_subtrees (tree *tp, int *walk_subtrees_p, walk_tree_fn func,
2362                   void *data, struct pointer_set_t *pset)
2363 {
2364   enum tree_code code = TREE_CODE (*tp);
2365   tree result;
2366
2367 #define WALK_SUBTREE(NODE)                              \
2368   do                                                    \
2369     {                                                   \
2370       result = cp_walk_tree (&(NODE), func, data, pset);        \
2371       if (result) goto out;                             \
2372     }                                                   \
2373   while (0)
2374
2375   /* Not one of the easy cases.  We must explicitly go through the
2376      children.  */
2377   result = NULL_TREE;
2378   switch (code)
2379     {
2380     case DEFAULT_ARG:
2381     case TEMPLATE_TEMPLATE_PARM:
2382     case BOUND_TEMPLATE_TEMPLATE_PARM:
2383     case UNBOUND_CLASS_TEMPLATE:
2384     case TEMPLATE_PARM_INDEX:
2385     case TEMPLATE_TYPE_PARM:
2386     case TYPENAME_TYPE:
2387     case TYPEOF_TYPE:
2388       /* None of these have subtrees other than those already walked
2389          above.  */
2390       *walk_subtrees_p = 0;
2391       break;
2392
2393     case BASELINK:
2394       WALK_SUBTREE (BASELINK_FUNCTIONS (*tp));
2395       *walk_subtrees_p = 0;
2396       break;
2397
2398     case PTRMEM_CST:
2399       WALK_SUBTREE (TREE_TYPE (*tp));
2400       *walk_subtrees_p = 0;
2401       break;
2402
2403     case TREE_LIST:
2404       WALK_SUBTREE (TREE_PURPOSE (*tp));
2405       break;
2406
2407     case OVERLOAD:
2408       WALK_SUBTREE (OVL_FUNCTION (*tp));
2409       WALK_SUBTREE (OVL_CHAIN (*tp));
2410       *walk_subtrees_p = 0;
2411       break;
2412
2413     case USING_DECL:
2414       WALK_SUBTREE (DECL_NAME (*tp));
2415       WALK_SUBTREE (USING_DECL_SCOPE (*tp));
2416       WALK_SUBTREE (USING_DECL_DECLS (*tp));
2417       *walk_subtrees_p = 0;
2418       break;
2419
2420     case RECORD_TYPE:
2421       if (TYPE_PTRMEMFUNC_P (*tp))
2422         WALK_SUBTREE (TYPE_PTRMEMFUNC_FN_TYPE (*tp));
2423       break;
2424
2425     case TYPE_ARGUMENT_PACK:
2426     case NONTYPE_ARGUMENT_PACK:
2427       {
2428         tree args = ARGUMENT_PACK_ARGS (*tp);
2429         int i, len = TREE_VEC_LENGTH (args);
2430         for (i = 0; i < len; i++)
2431           WALK_SUBTREE (TREE_VEC_ELT (args, i));
2432       }
2433       break;
2434
2435     case TYPE_PACK_EXPANSION:
2436       WALK_SUBTREE (TREE_TYPE (*tp));
2437       *walk_subtrees_p = 0;
2438       break;
2439
2440     case EXPR_PACK_EXPANSION:
2441       WALK_SUBTREE (TREE_OPERAND (*tp, 0));
2442       *walk_subtrees_p = 0;
2443       break;
2444
2445     case CAST_EXPR:
2446       if (TREE_TYPE (*tp))
2447         WALK_SUBTREE (TREE_TYPE (*tp));
2448
2449       {
2450         int i;
2451         for (i = 0; i < TREE_CODE_LENGTH (TREE_CODE (*tp)); ++i)
2452           WALK_SUBTREE (TREE_OPERAND (*tp, i));
2453       }
2454       *walk_subtrees_p = 0;
2455       break;
2456
2457     case TRAIT_EXPR:
2458       WALK_SUBTREE (TRAIT_EXPR_TYPE1 (*tp));
2459       WALK_SUBTREE (TRAIT_EXPR_TYPE2 (*tp));
2460       *walk_subtrees_p = 0;
2461       break;
2462
2463     case DECLTYPE_TYPE:
2464       WALK_SUBTREE (DECLTYPE_TYPE_EXPR (*tp));
2465       *walk_subtrees_p = 0;
2466       break;
2467
2468
2469     default:
2470       return NULL_TREE;
2471     }
2472
2473   /* We didn't find what we were looking for.  */
2474  out:
2475   return result;
2476
2477 #undef WALK_SUBTREE
2478 }
2479
2480 /* Like save_expr, but for C++.  */
2481
2482 tree
2483 cp_save_expr (tree expr)
2484 {
2485   /* There is no reason to create a SAVE_EXPR within a template; if
2486      needed, we can create the SAVE_EXPR when instantiating the
2487      template.  Furthermore, the middle-end cannot handle C++-specific
2488      tree codes.  */
2489   if (processing_template_decl)
2490     return expr;
2491   return save_expr (expr);
2492 }
2493
2494 /* Initialize tree.c.  */
2495
2496 void
2497 init_tree (void)
2498 {
2499   list_hash_table = htab_create_ggc (31, list_hash, list_hash_eq, NULL);
2500 }
2501
2502 /* Returns the kind of special function that DECL (a FUNCTION_DECL)
2503    is.  Note that sfk_none is zero, so this function can be used as a
2504    predicate to test whether or not DECL is a special function.  */
2505
2506 special_function_kind
2507 special_function_p (const_tree decl)
2508 {
2509   /* Rather than doing all this stuff with magic names, we should
2510      probably have a field of type `special_function_kind' in
2511      DECL_LANG_SPECIFIC.  */
2512   if (DECL_COPY_CONSTRUCTOR_P (decl))
2513     return sfk_copy_constructor;
2514   if (DECL_CONSTRUCTOR_P (decl))
2515     return sfk_constructor;
2516   if (DECL_OVERLOADED_OPERATOR_P (decl) == NOP_EXPR)
2517     return sfk_assignment_operator;
2518   if (DECL_MAYBE_IN_CHARGE_DESTRUCTOR_P (decl))
2519     return sfk_destructor;
2520   if (DECL_COMPLETE_DESTRUCTOR_P (decl))
2521     return sfk_complete_destructor;
2522   if (DECL_BASE_DESTRUCTOR_P (decl))
2523     return sfk_base_destructor;
2524   if (DECL_DELETING_DESTRUCTOR_P (decl))
2525     return sfk_deleting_destructor;
2526   if (DECL_CONV_FN_P (decl))
2527     return sfk_conversion;
2528
2529   return sfk_none;
2530 }
2531
2532 /* Returns nonzero if TYPE is a character type, including wchar_t.  */
2533
2534 int
2535 char_type_p (tree type)
2536 {
2537   return (same_type_p (type, char_type_node)
2538           || same_type_p (type, unsigned_char_type_node)
2539           || same_type_p (type, signed_char_type_node)
2540           || same_type_p (type, char16_type_node)
2541           || same_type_p (type, char32_type_node)
2542           || same_type_p (type, wchar_type_node));
2543 }
2544
2545 /* Returns the kind of linkage associated with the indicated DECL.  Th
2546    value returned is as specified by the language standard; it is
2547    independent of implementation details regarding template
2548    instantiation, etc.  For example, it is possible that a declaration
2549    to which this function assigns external linkage would not show up
2550    as a global symbol when you run `nm' on the resulting object file.  */
2551
2552 linkage_kind
2553 decl_linkage (tree decl)
2554 {
2555   /* This function doesn't attempt to calculate the linkage from first
2556      principles as given in [basic.link].  Instead, it makes use of
2557      the fact that we have already set TREE_PUBLIC appropriately, and
2558      then handles a few special cases.  Ideally, we would calculate
2559      linkage first, and then transform that into a concrete
2560      implementation.  */
2561
2562   /* Things that don't have names have no linkage.  */
2563   if (!DECL_NAME (decl))
2564     return lk_none;
2565
2566   /* Fields have no linkage.  */
2567   if (TREE_CODE (decl) == FIELD_DECL)
2568     return lk_none;
2569
2570   /* Things that are TREE_PUBLIC have external linkage.  */
2571   if (TREE_PUBLIC (decl))
2572     return lk_external;
2573
2574   if (TREE_CODE (decl) == NAMESPACE_DECL)
2575     return lk_external;
2576
2577   /* Linkage of a CONST_DECL depends on the linkage of the enumeration
2578      type.  */
2579   if (TREE_CODE (decl) == CONST_DECL)
2580     return decl_linkage (TYPE_NAME (TREE_TYPE (decl)));
2581
2582   /* Some things that are not TREE_PUBLIC have external linkage, too.
2583      For example, on targets that don't have weak symbols, we make all
2584      template instantiations have internal linkage (in the object
2585      file), but the symbols should still be treated as having external
2586      linkage from the point of view of the language.  */
2587   if (TREE_CODE (decl) != TYPE_DECL && DECL_LANG_SPECIFIC (decl)
2588       && DECL_COMDAT (decl))
2589     return lk_external;
2590
2591   /* Things in local scope do not have linkage, if they don't have
2592      TREE_PUBLIC set.  */
2593   if (decl_function_context (decl))
2594     return lk_none;
2595
2596   /* Members of the anonymous namespace also have TREE_PUBLIC unset, but
2597      are considered to have external linkage for language purposes.  DECLs
2598      really meant to have internal linkage have DECL_THIS_STATIC set.  */
2599   if (TREE_CODE (decl) == TYPE_DECL)
2600     return lk_external;
2601   if (TREE_CODE (decl) == VAR_DECL || TREE_CODE (decl) == FUNCTION_DECL)
2602     {
2603       if (!DECL_THIS_STATIC (decl))
2604         return lk_external;
2605
2606       /* Static data members and static member functions from classes
2607          in anonymous namespace also don't have TREE_PUBLIC set.  */
2608       if (DECL_CLASS_CONTEXT (decl))
2609         return lk_external;
2610     }
2611
2612   /* Everything else has internal linkage.  */
2613   return lk_internal;
2614 }
2615 \f
2616 /* EXP is an expression that we want to pre-evaluate.  Returns (in
2617    *INITP) an expression that will perform the pre-evaluation.  The
2618    value returned by this function is a side-effect free expression
2619    equivalent to the pre-evaluated expression.  Callers must ensure
2620    that *INITP is evaluated before EXP.  */
2621
2622 tree
2623 stabilize_expr (tree exp, tree* initp)
2624 {
2625   tree init_expr;
2626
2627   if (!TREE_SIDE_EFFECTS (exp))
2628     init_expr = NULL_TREE;
2629   else if (!real_lvalue_p (exp)
2630            || !TYPE_NEEDS_CONSTRUCTING (TREE_TYPE (exp)))
2631     {
2632       init_expr = get_target_expr (exp);
2633       exp = TARGET_EXPR_SLOT (init_expr);
2634     }
2635   else
2636     {
2637       exp = cp_build_unary_op (ADDR_EXPR, exp, 1, tf_warning_or_error);
2638       init_expr = get_target_expr (exp);
2639       exp = TARGET_EXPR_SLOT (init_expr);
2640       exp = cp_build_indirect_ref (exp, 0, tf_warning_or_error);
2641     }
2642   *initp = init_expr;
2643
2644   gcc_assert (!TREE_SIDE_EFFECTS (exp));
2645   return exp;
2646 }
2647
2648 /* Add NEW_EXPR, an expression whose value we don't care about, after the
2649    similar expression ORIG.  */
2650
2651 tree
2652 add_stmt_to_compound (tree orig, tree new_expr)
2653 {
2654   if (!new_expr || !TREE_SIDE_EFFECTS (new_expr))
2655     return orig;
2656   if (!orig || !TREE_SIDE_EFFECTS (orig))
2657     return new_expr;
2658   return build2 (COMPOUND_EXPR, void_type_node, orig, new_expr);
2659 }
2660
2661 /* Like stabilize_expr, but for a call whose arguments we want to
2662    pre-evaluate.  CALL is modified in place to use the pre-evaluated
2663    arguments, while, upon return, *INITP contains an expression to
2664    compute the arguments.  */
2665
2666 void
2667 stabilize_call (tree call, tree *initp)
2668 {
2669   tree inits = NULL_TREE;
2670   int i;
2671   int nargs = call_expr_nargs (call);
2672
2673   if (call == error_mark_node || processing_template_decl)
2674     {
2675       *initp = NULL_TREE;
2676       return;
2677     }
2678
2679   gcc_assert (TREE_CODE (call) == CALL_EXPR);
2680
2681   for (i = 0; i < nargs; i++)
2682     {
2683       tree init;
2684       CALL_EXPR_ARG (call, i) =
2685         stabilize_expr (CALL_EXPR_ARG (call, i), &init);
2686       inits = add_stmt_to_compound (inits, init);
2687     }
2688
2689   *initp = inits;
2690 }
2691
2692 /* Like stabilize_expr, but for an AGGR_INIT_EXPR whose arguments we want
2693    to pre-evaluate.  CALL is modified in place to use the pre-evaluated
2694    arguments, while, upon return, *INITP contains an expression to
2695    compute the arguments.  */
2696
2697 void
2698 stabilize_aggr_init (tree call, tree *initp)
2699 {
2700   tree inits = NULL_TREE;
2701   int i;
2702   int nargs = aggr_init_expr_nargs (call);
2703
2704   if (call == error_mark_node)
2705     return;
2706
2707   gcc_assert (TREE_CODE (call) == AGGR_INIT_EXPR);
2708
2709   for (i = 0; i < nargs; i++)
2710     {
2711       tree init;
2712       AGGR_INIT_EXPR_ARG (call, i) =
2713         stabilize_expr (AGGR_INIT_EXPR_ARG (call, i), &init);
2714       inits = add_stmt_to_compound (inits, init);
2715     }
2716
2717   *initp = inits;
2718 }
2719
2720 /* Like stabilize_expr, but for an initialization.
2721
2722    If the initialization is for an object of class type, this function
2723    takes care not to introduce additional temporaries.
2724
2725    Returns TRUE iff the expression was successfully pre-evaluated,
2726    i.e., if INIT is now side-effect free, except for, possible, a
2727    single call to a constructor.  */
2728
2729 bool
2730 stabilize_init (tree init, tree *initp)
2731 {
2732   tree t = init;
2733
2734   *initp = NULL_TREE;
2735
2736   if (t == error_mark_node || processing_template_decl)
2737     return true;
2738
2739   if (TREE_CODE (t) == INIT_EXPR
2740       && TREE_CODE (TREE_OPERAND (t, 1)) != TARGET_EXPR
2741       && TREE_CODE (TREE_OPERAND (t, 1)) != AGGR_INIT_EXPR)
2742     {
2743       TREE_OPERAND (t, 1) = stabilize_expr (TREE_OPERAND (t, 1), initp);
2744       return true;
2745     }
2746
2747   if (TREE_CODE (t) == INIT_EXPR)
2748     t = TREE_OPERAND (t, 1);
2749   if (TREE_CODE (t) == TARGET_EXPR)
2750     t = TARGET_EXPR_INITIAL (t);
2751   if (TREE_CODE (t) == COMPOUND_EXPR)
2752     t = expr_last (t);
2753   if (TREE_CODE (t) == CONSTRUCTOR
2754       && EMPTY_CONSTRUCTOR_P (t))
2755     /* Default-initialization.  */
2756     return true;
2757
2758   /* If the initializer is a COND_EXPR, we can't preevaluate
2759      anything.  */
2760   if (TREE_CODE (t) == COND_EXPR)
2761     return false;
2762
2763   if (TREE_CODE (t) == CALL_EXPR)
2764     {
2765       stabilize_call (t, initp);
2766       return true;
2767     }
2768
2769   if (TREE_CODE (t) == AGGR_INIT_EXPR)
2770     {
2771       stabilize_aggr_init (t, initp);
2772       return true;
2773     }
2774
2775   /* The initialization is being performed via a bitwise copy -- and
2776      the item copied may have side effects.  */
2777   return TREE_SIDE_EFFECTS (init);
2778 }
2779
2780 /* Like "fold", but should be used whenever we might be processing the
2781    body of a template.  */
2782
2783 tree
2784 fold_if_not_in_template (tree expr)
2785 {
2786   /* In the body of a template, there is never any need to call
2787      "fold".  We will call fold later when actually instantiating the
2788      template.  Integral constant expressions in templates will be
2789      evaluated via fold_non_dependent_expr, as necessary.  */
2790   if (processing_template_decl)
2791     return expr;
2792
2793   /* Fold C++ front-end specific tree codes.  */
2794   if (TREE_CODE (expr) == UNARY_PLUS_EXPR)
2795     return fold_convert (TREE_TYPE (expr), TREE_OPERAND (expr, 0));
2796
2797   return fold (expr);
2798 }
2799
2800 /* Returns true if a cast to TYPE may appear in an integral constant
2801    expression.  */
2802
2803 bool
2804 cast_valid_in_integral_constant_expression_p (tree type)
2805 {
2806   return (INTEGRAL_OR_ENUMERATION_TYPE_P (type)
2807           || dependent_type_p (type)
2808           || type == error_mark_node);
2809 }
2810
2811 \f
2812 #if defined ENABLE_TREE_CHECKING && (GCC_VERSION >= 2007)
2813 /* Complain that some language-specific thing hanging off a tree
2814    node has been accessed improperly.  */
2815
2816 void
2817 lang_check_failed (const char* file, int line, const char* function)
2818 {
2819   internal_error ("lang_* check: failed in %s, at %s:%d",
2820                   function, trim_filename (file), line);
2821 }
2822 #endif /* ENABLE_TREE_CHECKING */
2823
2824 #include "gt-cp-tree.h"