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