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