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