gcc/cp/tree.c

   1 /* Language-dependent node constructors for parse phase of GNU compiler.
   2    Copyright (C) 1987-2014 Free Software Foundation, Inc.
   3    Hacked by Michael Tiemann (tiemann@cygnus.com)
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 3, or (at your option)
  10 any later version.
  11
  12 GCC is distributed in the hope that it will be useful,
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 GNU General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING3.  If not see
  19 <http://www.gnu.org/licenses/>.  */
  20
  21 #include "config.h"
  22 #include "system.h"
  23 #include "coretypes.h"
  24 #include "tm.h"
  25 #include "tree.h"
  26 #include "tree-hasher.h"
  27 #include "stor-layout.h"
  28 #include "print-tree.h"
  29 #include "tree-iterator.h"
  30 #include "cp-tree.h"
  31 #include "flags.h"
  32 #include "tree-inline.h"
  33 #include "debug.h"
  34 #include "convert.h"
  35 #include "cgraph.h"
  36 #include "splay-tree.h"
  37 #include "hash-table.h"
  38 #include "gimple-expr.h"
  39 #include "gimplify.h"
  40 #include "wide-int.h"
  41
  42 static tree bot_manip (tree *, int *, void *);
  43 static tree bot_replace (tree *, int *, void *);
  44 static hashval_t list_hash_pieces (tree, tree, tree);
  45 static tree build_target_expr (tree, tree, tsubst_flags_t);
  46 static tree count_trees_r (tree *, int *, void *);
  47 static tree verify_stmt_tree_r (tree *, int *, void *);
  48 static tree build_local_temp (tree);
  49
  50 static tree handle_java_interface_attribute (tree *, tree, tree, int, bool *);
  51 static tree handle_com_interface_attribute (tree *, tree, tree, int, bool *);
  52 static tree handle_init_priority_attribute (tree *, tree, tree, int, bool *);
  53 static tree handle_abi_tag_attribute (tree *, tree, tree, int, bool *);
  54
  55 /* If REF is an lvalue, returns the kind of lvalue that REF is.
  56    Otherwise, returns clk_none.  */
  57
  58 cp_lvalue_kind
  59 lvalue_kind (const_tree ref)
  60 {
  61   cp_lvalue_kind op1_lvalue_kind = clk_none;
  62   cp_lvalue_kind op2_lvalue_kind = clk_none;
  63
  64   /* Expressions of reference type are sometimes wrapped in
  65      INDIRECT_REFs.  INDIRECT_REFs are just internal compiler
  66      representation, not part of the language, so we have to look
  67      through them.  */
  68   if (REFERENCE_REF_P (ref))
  69     return lvalue_kind (TREE_OPERAND (ref, 0));
  70
  71   if (TREE_TYPE (ref)
  72       && TREE_CODE (TREE_TYPE (ref)) == REFERENCE_TYPE)
  73     {
  74       /* unnamed rvalue references are rvalues */
  75       if (TYPE_REF_IS_RVALUE (TREE_TYPE (ref))
  76           && TREE_CODE (ref) != PARM_DECL
  77           && !VAR_P (ref)
  78           && TREE_CODE (ref) != COMPONENT_REF
  79           /* Functions are always lvalues.  */
  80           && TREE_CODE (TREE_TYPE (TREE_TYPE (ref))) != FUNCTION_TYPE)
  81         return clk_rvalueref;
  82
  83       /* lvalue references and named rvalue references are lvalues.  */
  84       return clk_ordinary;
  85     }
  86
  87   if (ref == current_class_ptr)
  88     return clk_none;
  89
  90   switch (TREE_CODE (ref))
  91     {
  92     case SAVE_EXPR:
  93       return clk_none;
  94       /* preincrements and predecrements are valid lvals, provided
  95          what they refer to are valid lvals.  */
  96     case PREINCREMENT_EXPR:
  97     case PREDECREMENT_EXPR:
  98     case TRY_CATCH_EXPR:
  99     case WITH_CLEANUP_EXPR:
 100     case REALPART_EXPR:
 101     case IMAGPART_EXPR:
 102       return lvalue_kind (TREE_OPERAND (ref, 0));
 103
 104     case MEMBER_REF:
 105     case DOTSTAR_EXPR:
 106       if (TREE_CODE (ref) == MEMBER_REF)
 107         op1_lvalue_kind = clk_ordinary;
 108       else
 109         op1_lvalue_kind = lvalue_kind (TREE_OPERAND (ref, 0));
 110       if (TYPE_PTRMEMFUNC_P (TREE_TYPE (TREE_OPERAND (ref, 1))))
 111         op1_lvalue_kind = clk_none;
 112       return op1_lvalue_kind;
 113
 114     case COMPONENT_REF:
 115       op1_lvalue_kind = lvalue_kind (TREE_OPERAND (ref, 0));
 116       /* Look at the member designator.  */
 117       if (!op1_lvalue_kind)
 118         ;
 119       else if (is_overloaded_fn (TREE_OPERAND (ref, 1)))
 120         /* The "field" can be a FUNCTION_DECL or an OVERLOAD in some
 121            situations.  If we're seeing a COMPONENT_REF, it's a non-static
 122            member, so it isn't an lvalue. */
 123         op1_lvalue_kind = clk_none;
 124       else if (TREE_CODE (TREE_OPERAND (ref, 1)) != FIELD_DECL)
 125         /* This can be IDENTIFIER_NODE in a template.  */;
 126       else if (DECL_C_BIT_FIELD (TREE_OPERAND (ref, 1)))
 127         {
 128           /* Clear the ordinary bit.  If this object was a class
 129              rvalue we want to preserve that information.  */
 130           op1_lvalue_kind &= ~clk_ordinary;
 131           /* The lvalue is for a bitfield.  */
 132           op1_lvalue_kind |= clk_bitfield;
 133         }
 134       else if (DECL_PACKED (TREE_OPERAND (ref, 1)))
 135         op1_lvalue_kind |= clk_packed;
 136
 137       return op1_lvalue_kind;
 138
 139     case STRING_CST:
 140     case COMPOUND_LITERAL_EXPR:
 141       return clk_ordinary;
 142
 143     case CONST_DECL:
 144       /* CONST_DECL without TREE_STATIC are enumeration values and
 145          thus not lvalues.  With TREE_STATIC they are used by ObjC++
 146          in objc_build_string_object and need to be considered as
 147          lvalues.  */
 148       if (! TREE_STATIC (ref))
 149         return clk_none;
 150     case VAR_DECL:
 151       if (TREE_READONLY (ref) && ! TREE_STATIC (ref)
 152           && DECL_LANG_SPECIFIC (ref)
 153           && DECL_IN_AGGR_P (ref))
 154         return clk_none;
 155     case INDIRECT_REF:
 156     case ARROW_EXPR:
 157     case ARRAY_REF:
 158     case ARRAY_NOTATION_REF:
 159     case PARM_DECL:
 160     case RESULT_DECL:
 161       return clk_ordinary;
 162
 163       /* A scope ref in a template, left as SCOPE_REF to support later
 164          access checking.  */
 165     case SCOPE_REF:
 166       gcc_assert (!type_dependent_expression_p (CONST_CAST_TREE (ref)));
 167       {
 168         tree op = TREE_OPERAND (ref, 1);
 169         if (TREE_CODE (op) == FIELD_DECL)
 170           return (DECL_C_BIT_FIELD (op) ? clk_bitfield : clk_ordinary);
 171         else
 172           return lvalue_kind (op);
 173       }
 174
 175     case MAX_EXPR:
 176     case MIN_EXPR:
 177       /* Disallow <? and >? as lvalues if either argument side-effects.  */
 178       if (TREE_SIDE_EFFECTS (TREE_OPERAND (ref, 0))
 179           || TREE_SIDE_EFFECTS (TREE_OPERAND (ref, 1)))
 180         return clk_none;
 181       op1_lvalue_kind = lvalue_kind (TREE_OPERAND (ref, 0));
 182       op2_lvalue_kind = lvalue_kind (TREE_OPERAND (ref, 1));
 183       break;
 184
 185     case COND_EXPR:
 186       op1_lvalue_kind = lvalue_kind (TREE_OPERAND (ref, 1)
 187                                     ? TREE_OPERAND (ref, 1)
 188                                     : TREE_OPERAND (ref, 0));
 189       op2_lvalue_kind = lvalue_kind (TREE_OPERAND (ref, 2));
 190       break;
 191
 192     case MODIFY_EXPR:
 193     case TYPEID_EXPR:
 194       return clk_ordinary;
 195
 196     case COMPOUND_EXPR:
 197       return lvalue_kind (TREE_OPERAND (ref, 1));
 198
 199     case TARGET_EXPR:
 200       return clk_class;
 201
 202     case VA_ARG_EXPR:
 203       return (CLASS_TYPE_P (TREE_TYPE (ref)) ? clk_class : clk_none);
 204
 205     case CALL_EXPR:
 206       /* We can see calls outside of TARGET_EXPR in templates.  */
 207       if (CLASS_TYPE_P (TREE_TYPE (ref)))
 208         return clk_class;
 209       return clk_none;
 210
 211     case FUNCTION_DECL:
 212       /* All functions (except non-static-member functions) are
 213          lvalues.  */
 214       return (DECL_NONSTATIC_MEMBER_FUNCTION_P (ref)
 215               ? clk_none : clk_ordinary);
 216
 217     case BASELINK:
 218       /* We now represent a reference to a single static member function
 219          with a BASELINK.  */
 220       /* This CONST_CAST is okay because BASELINK_FUNCTIONS returns
 221          its argument unmodified and we assign it to a const_tree.  */
 222       return lvalue_kind (BASELINK_FUNCTIONS (CONST_CAST_TREE (ref)));
 223
 224     case NON_DEPENDENT_EXPR:
 225       /* We just return clk_ordinary for NON_DEPENDENT_EXPR in C++98, but
 226          in C++11 lvalues don't bind to rvalue references, so we need to
 227          work harder to avoid bogus errors (c++/44870).  */
 228       if (cxx_dialect < cxx11)
 229         return clk_ordinary;
 230       else
 231         return lvalue_kind (TREE_OPERAND (ref, 0));
 232
 233     default:
 234       if (!TREE_TYPE (ref))
 235         return clk_none;
 236       if (CLASS_TYPE_P (TREE_TYPE (ref)))
 237         return clk_class;
 238       break;
 239     }
 240
 241   /* If one operand is not an lvalue at all, then this expression is
 242      not an lvalue.  */
 243   if (!op1_lvalue_kind || !op2_lvalue_kind)
 244     return clk_none;
 245
 246   /* Otherwise, it's an lvalue, and it has all the odd properties
 247      contributed by either operand.  */
 248   op1_lvalue_kind = op1_lvalue_kind | op2_lvalue_kind;
 249   /* It's not an ordinary lvalue if it involves any other kind.  */
 250   if ((op1_lvalue_kind & ~clk_ordinary) != clk_none)
 251     op1_lvalue_kind &= ~clk_ordinary;
 252   /* It can't be both a pseudo-lvalue and a non-addressable lvalue.
 253      A COND_EXPR of those should be wrapped in a TARGET_EXPR.  */
 254   if ((op1_lvalue_kind & (clk_rvalueref|clk_class))
 255       && (op1_lvalue_kind & (clk_bitfield|clk_packed)))
 256     op1_lvalue_kind = clk_none;
 257   return op1_lvalue_kind;
 258 }
 259
 260 /* Returns the kind of lvalue that REF is, in the sense of
 261    [basic.lval].  This function should really be named lvalue_p; it
 262    computes the C++ definition of lvalue.  */
 263
 264 cp_lvalue_kind
 265 real_lvalue_p (const_tree ref)
 266 {
 267   cp_lvalue_kind kind = lvalue_kind (ref);
 268   if (kind & (clk_rvalueref|clk_class))
 269     return clk_none;
 270   else
 271     return kind;
 272 }
 273
 274 /* This differs from real_lvalue_p in that class rvalues are considered
 275    lvalues.  */
 276
 277 bool
 278 lvalue_p (const_tree ref)
 279 {
 280   return (lvalue_kind (ref) != clk_none);
 281 }
 282
 283 /* This differs from real_lvalue_p in that rvalues formed by dereferencing
 284    rvalue references are considered rvalues.  */
 285
 286 bool
 287 lvalue_or_rvalue_with_address_p (const_tree ref)
 288 {
 289   cp_lvalue_kind kind = lvalue_kind (ref);
 290   if (kind & clk_class)
 291     return false;
 292   else
 293     return (kind != clk_none);
 294 }
 295
 296 /* Returns true if REF is an xvalue, false otherwise.  */
 297
 298 bool
 299 xvalue_p (const_tree ref)
 300 {
 301   return (lvalue_kind (ref) == clk_rvalueref);
 302 }
 303
 304 /* Test whether DECL is a builtin that may appear in a
 305    constant-expression. */
 306
 307 bool
 308 builtin_valid_in_constant_expr_p (const_tree decl)
 309 {
 310   /* At present BUILT_IN_CONSTANT_P is the only builtin we're allowing
 311      in constant-expressions.  We may want to add other builtins later. */
 312   return DECL_IS_BUILTIN_CONSTANT_P (decl);
 313 }
 314
 315 /* Build a TARGET_EXPR, initializing the DECL with the VALUE.  */
 316
 317 static tree
 318 build_target_expr (tree decl, tree value, tsubst_flags_t complain)
 319 {
 320   tree t;
 321   tree type = TREE_TYPE (decl);
 322
 323 #ifdef ENABLE_CHECKING
 324   gcc_assert (VOID_TYPE_P (TREE_TYPE (value))
 325               || TREE_TYPE (decl) == TREE_TYPE (value)
 326               /* On ARM ctors return 'this'.  */
 327               || (TYPE_PTR_P (TREE_TYPE (value))
 328                   && TREE_CODE (value) == CALL_EXPR)
 329               || useless_type_conversion_p (TREE_TYPE (decl),
 330                                             TREE_TYPE (value)));
 331 #endif
 332
 333   t = cxx_maybe_build_cleanup (decl, complain);
 334   if (t == error_mark_node)
 335     return error_mark_node;
 336   t = build4 (TARGET_EXPR, type, decl, value, t, NULL_TREE);
 337   /* We always set TREE_SIDE_EFFECTS so that expand_expr does not
 338      ignore the TARGET_EXPR.  If there really turn out to be no
 339      side-effects, then the optimizer should be able to get rid of
 340      whatever code is generated anyhow.  */
 341   TREE_SIDE_EFFECTS (t) = 1;
 342
 343   return t;
 344 }
 345
 346 /* Return an undeclared local temporary of type TYPE for use in building a
 347    TARGET_EXPR.  */
 348
 349 static tree
 350 build_local_temp (tree type)
 351 {
 352   tree slot = build_decl (input_location,
 353                           VAR_DECL, NULL_TREE, type);
 354   DECL_ARTIFICIAL (slot) = 1;
 355   DECL_IGNORED_P (slot) = 1;
 356   DECL_CONTEXT (slot) = current_function_decl;
 357   layout_decl (slot, 0);
 358   return slot;
 359 }
 360
 361 /* Set various status flags when building an AGGR_INIT_EXPR object T.  */
 362
 363 static void
 364 process_aggr_init_operands (tree t)
 365 {
 366   bool side_effects;
 367
 368   side_effects = TREE_SIDE_EFFECTS (t);
 369   if (!side_effects)
 370     {
 371       int i, n;
 372       n = TREE_OPERAND_LENGTH (t);
 373       for (i = 1; i < n; i++)
 374         {
 375           tree op = TREE_OPERAND (t, i);
 376           if (op && TREE_SIDE_EFFECTS (op))
 377             {
 378               side_effects = 1;
 379               break;
 380             }
 381         }
 382     }
 383   TREE_SIDE_EFFECTS (t) = side_effects;
 384 }
 385
 386 /* Build an AGGR_INIT_EXPR of class tcc_vl_exp with the indicated RETURN_TYPE,
 387    FN, and SLOT.  NARGS is the number of call arguments which are specified
 388    as a tree array ARGS.  */
 389
 390 static tree
 391 build_aggr_init_array (tree return_type, tree fn, tree slot, int nargs,
 392                        tree *args)
 393 {
 394   tree t;
 395   int i;
 396
 397   t = build_vl_exp (AGGR_INIT_EXPR, nargs + 3);
 398   TREE_TYPE (t) = return_type;
 399   AGGR_INIT_EXPR_FN (t) = fn;
 400   AGGR_INIT_EXPR_SLOT (t) = slot;
 401   for (i = 0; i < nargs; i++)
 402     AGGR_INIT_EXPR_ARG (t, i) = args[i];
 403   process_aggr_init_operands (t);
 404   return t;
 405 }
 406
 407 /* INIT is a CALL_EXPR or AGGR_INIT_EXPR which needs info about its
 408    target.  TYPE is the type to be initialized.
 409
 410    Build an AGGR_INIT_EXPR to represent the initialization.  This function
 411    differs from build_cplus_new in that an AGGR_INIT_EXPR can only be used
 412    to initialize another object, whereas a TARGET_EXPR can either
 413    initialize another object or create its own temporary object, and as a
 414    result building up a TARGET_EXPR requires that the type's destructor be
 415    callable.  */
 416
 417 tree
 418 build_aggr_init_expr (tree type, tree init)
 419 {
 420   tree fn;
 421   tree slot;
 422   tree rval;
 423   int is_ctor;
 424
 425   /* Don't build AGGR_INIT_EXPR in a template.  */
 426   if (processing_template_decl)
 427     return init;
 428
 429   if (TREE_CODE (init) == CALL_EXPR)
 430     fn = CALL_EXPR_FN (init);
 431   else if (TREE_CODE (init) == AGGR_INIT_EXPR)
 432     fn = AGGR_INIT_EXPR_FN (init);
 433   else
 434     return convert (type, init);
 435
 436   is_ctor = (TREE_CODE (fn) == ADDR_EXPR
 437              && TREE_CODE (TREE_OPERAND (fn, 0)) == FUNCTION_DECL
 438              && DECL_CONSTRUCTOR_P (TREE_OPERAND (fn, 0)));
 439
 440   /* We split the CALL_EXPR into its function and its arguments here.
 441      Then, in expand_expr, we put them back together.  The reason for
 442      this is that this expression might be a default argument
 443      expression.  In that case, we need a new temporary every time the
 444      expression is used.  That's what break_out_target_exprs does; it
 445      replaces every AGGR_INIT_EXPR with a copy that uses a fresh
 446      temporary slot.  Then, expand_expr builds up a call-expression
 447      using the new slot.  */
 448
 449   /* If we don't need to use a constructor to create an object of this
 450      type, don't mess with AGGR_INIT_EXPR.  */
 451   if (is_ctor || TREE_ADDRESSABLE (type))
 452     {
 453       slot = build_local_temp (type);
 454
 455       if (TREE_CODE(init) == CALL_EXPR)
 456         rval = build_aggr_init_array (void_type_node, fn, slot,
 457                                       call_expr_nargs (init),
 458                                       CALL_EXPR_ARGP (init));
 459       else
 460         rval = build_aggr_init_array (void_type_node, fn, slot,
 461                                       aggr_init_expr_nargs (init),
 462                                       AGGR_INIT_EXPR_ARGP (init));
 463       TREE_SIDE_EFFECTS (rval) = 1;
 464       AGGR_INIT_VIA_CTOR_P (rval) = is_ctor;
 465       TREE_NOTHROW (rval) = TREE_NOTHROW (init);
 466       CALL_EXPR_LIST_INIT_P (rval) = CALL_EXPR_LIST_INIT_P (init);
 467     }
 468   else
 469     rval = init;
 470
 471   return rval;
 472 }
 473
 474 /* INIT is a CALL_EXPR or AGGR_INIT_EXPR which needs info about its
 475    target.  TYPE is the type that this initialization should appear to
 476    have.
 477
 478    Build an encapsulation of the initialization to perform
 479    and return it so that it can be processed by language-independent
 480    and language-specific expression expanders.  */
 481
 482 tree
 483 build_cplus_new (tree type, tree init, tsubst_flags_t complain)
 484 {
 485   tree rval = build_aggr_init_expr (type, init);
 486   tree slot;
 487
 488   if (!complete_type_or_maybe_complain (type, init, complain))
 489     return error_mark_node;
 490
 491   /* Make sure that we're not trying to create an instance of an
 492      abstract class.  */
 493   if (abstract_virtuals_error_sfinae (NULL_TREE, type, complain))
 494     return error_mark_node;
 495
 496   if (TREE_CODE (rval) == AGGR_INIT_EXPR)
 497     slot = AGGR_INIT_EXPR_SLOT (rval);
 498   else if (TREE_CODE (rval) == CALL_EXPR
 499            || TREE_CODE (rval) == CONSTRUCTOR)
 500     slot = build_local_temp (type);
 501   else
 502     return rval;
 503
 504   rval = build_target_expr (slot, rval, complain);
 505
 506   if (rval != error_mark_node)
 507     TARGET_EXPR_IMPLICIT_P (rval) = 1;
 508
 509   return rval;
 510 }
 511
 512 /* Subroutine of build_vec_init_expr: Build up a single element
 513    intialization as a proxy for the full array initialization to get things
 514    marked as used and any appropriate diagnostics.
 515
 516    Since we're deferring building the actual constructor calls until
 517    gimplification time, we need to build one now and throw it away so
 518    that the relevant constructor gets mark_used before cgraph decides
 519    what functions are needed.  Here we assume that init is either
 520    NULL_TREE, void_type_node (indicating value-initialization), or
 521    another array to copy.  */
 522
 523 static tree
 524 build_vec_init_elt (tree type, tree init, tsubst_flags_t complain)
 525 {
 526   tree inner_type = strip_array_types (type);
 527   vec<tree, va_gc> *argvec;
 528
 529   if (integer_zerop (array_type_nelts_total (type))
 530       || !CLASS_TYPE_P (inner_type))
 531     /* No interesting initialization to do.  */
 532     return integer_zero_node;
 533   else if (init == void_type_node)
 534     return build_value_init (inner_type, complain);
 535
 536   gcc_assert (init == NULL_TREE
 537               || (same_type_ignoring_top_level_qualifiers_p
 538                   (type, TREE_TYPE (init))));
 539
 540   argvec = make_tree_vector ();
 541   if (init)
 542     {
 543       tree init_type = strip_array_types (TREE_TYPE (init));
 544       tree dummy = build_dummy_object (init_type);
 545       if (!real_lvalue_p (init))
 546         dummy = move (dummy);
 547       argvec->quick_push (dummy);
 548     }
 549   init = build_special_member_call (NULL_TREE, complete_ctor_identifier,
 550                                     &argvec, inner_type, LOOKUP_NORMAL,
 551                                     complain);
 552   release_tree_vector (argvec);
 553
 554   /* For a trivial constructor, build_over_call creates a TARGET_EXPR.  But
 555      we don't want one here because we aren't creating a temporary.  */
 556   if (TREE_CODE (init) == TARGET_EXPR)
 557     init = TARGET_EXPR_INITIAL (init);
 558
 559   return init;
 560 }
 561
 562 /* Return a TARGET_EXPR which expresses the initialization of an array to
 563    be named later, either default-initialization or copy-initialization
 564    from another array of the same type.  */
 565
 566 tree
 567 build_vec_init_expr (tree type, tree init, tsubst_flags_t complain)
 568 {
 569   tree slot;
 570   bool value_init = false;
 571   tree elt_init = build_vec_init_elt (type, init, complain);
 572
 573   if (init == void_type_node)
 574     {
 575       value_init = true;
 576       init = NULL_TREE;
 577     }
 578
 579   slot = build_local_temp (type);
 580   init = build2 (VEC_INIT_EXPR, type, slot, init);
 581   TREE_SIDE_EFFECTS (init) = true;
 582   SET_EXPR_LOCATION (init, input_location);
 583
 584   if (cxx_dialect >= cxx11
 585       && potential_constant_expression (elt_init))
 586     VEC_INIT_EXPR_IS_CONSTEXPR (init) = true;
 587   VEC_INIT_EXPR_VALUE_INIT (init) = value_init;
 588
 589   return init;
 590 }
 591
 592 /* Give a helpful diagnostic for a non-constexpr VEC_INIT_EXPR in a context
 593    that requires a constant expression.  */
 594
 595 void
 596 diagnose_non_constexpr_vec_init (tree expr)
 597 {
 598   tree type = TREE_TYPE (VEC_INIT_EXPR_SLOT (expr));
 599   tree init, elt_init;
 600   if (VEC_INIT_EXPR_VALUE_INIT (expr))
 601     init = void_type_node;
 602   else
 603     init = VEC_INIT_EXPR_INIT (expr);
 604
 605   elt_init = build_vec_init_elt (type, init, tf_warning_or_error);
 606   require_potential_constant_expression (elt_init);
 607 }
 608
 609 tree
 610 build_array_copy (tree init)
 611 {
 612   return build_vec_init_expr (TREE_TYPE (init), init, tf_warning_or_error);
 613 }
 614
 615 /* Build a TARGET_EXPR using INIT to initialize a new temporary of the
 616    indicated TYPE.  */
 617
 618 tree
 619 build_target_expr_with_type (tree init, tree type, tsubst_flags_t complain)
 620 {
 621   gcc_assert (!VOID_TYPE_P (type));
 622
 623   if (TREE_CODE (init) == TARGET_EXPR
 624       || init == error_mark_node)
 625     return init;
 626   else if (CLASS_TYPE_P (type) && type_has_nontrivial_copy_init (type)
 627            && !VOID_TYPE_P (TREE_TYPE (init))
 628            && TREE_CODE (init) != COND_EXPR
 629            && TREE_CODE (init) != CONSTRUCTOR
 630            && TREE_CODE (init) != VA_ARG_EXPR)
 631     /* We need to build up a copy constructor call.  A void initializer
 632        means we're being called from bot_manip.  COND_EXPR is a special
 633        case because we already have copies on the arms and we don't want
 634        another one here.  A CONSTRUCTOR is aggregate initialization, which
 635        is handled separately.  A VA_ARG_EXPR is magic creation of an
 636        aggregate; there's no additional work to be done.  */
 637     return force_rvalue (init, complain);
 638
 639   return force_target_expr (type, init, complain);
 640 }
 641
 642 /* Like the above function, but without the checking.  This function should
 643    only be used by code which is deliberately trying to subvert the type
 644    system, such as call_builtin_trap.  Or build_over_call, to avoid
 645    infinite recursion.  */
 646
 647 tree
 648 force_target_expr (tree type, tree init, tsubst_flags_t complain)
 649 {
 650   tree slot;
 651
 652   gcc_assert (!VOID_TYPE_P (type));
 653
 654   slot = build_local_temp (type);
 655   return build_target_expr (slot, init, complain);
 656 }
 657
 658 /* Like build_target_expr_with_type, but use the type of INIT.  */
 659
 660 tree
 661 get_target_expr_sfinae (tree init, tsubst_flags_t complain)
 662 {
 663   if (TREE_CODE (init) == AGGR_INIT_EXPR)
 664     return build_target_expr (AGGR_INIT_EXPR_SLOT (init), init, complain);
 665   else if (TREE_CODE (init) == VEC_INIT_EXPR)
 666     return build_target_expr (VEC_INIT_EXPR_SLOT (init), init, complain);
 667   else
 668     return build_target_expr_with_type (init, TREE_TYPE (init), complain);
 669 }
 670
 671 tree
 672 get_target_expr (tree init)
 673 {
 674   return get_target_expr_sfinae (init, tf_warning_or_error);
 675 }
 676
 677 /* If EXPR is a bitfield reference, convert it to the declared type of
 678    the bitfield, and return the resulting expression.  Otherwise,
 679    return EXPR itself.  */
 680
 681 tree
 682 convert_bitfield_to_declared_type (tree expr)
 683 {
 684   tree bitfield_type;
 685
 686   bitfield_type = is_bitfield_expr_with_lowered_type (expr);
 687   if (bitfield_type)
 688     expr = convert_to_integer (TYPE_MAIN_VARIANT (bitfield_type),
 689                                expr);
 690   return expr;
 691 }
 692
 693 /* EXPR is being used in an rvalue context.  Return a version of EXPR
 694    that is marked as an rvalue.  */
 695
 696 tree
 697 rvalue (tree expr)
 698 {
 699   tree type;
 700
 701   if (error_operand_p (expr))
 702     return expr;
 703
 704   expr = mark_rvalue_use (expr);
 705
 706   /* [basic.lval]
 707
 708      Non-class rvalues always have cv-unqualified types.  */
 709   type = TREE_TYPE (expr);
 710   if (!CLASS_TYPE_P (type) && cv_qualified_p (type))
 711     type = cv_unqualified (type);
 712
 713   /* We need to do this for rvalue refs as well to get the right answer
 714      from decltype; see c++/36628.  */
 715   if (!processing_template_decl && lvalue_or_rvalue_with_address_p (expr))
 716     expr = build1 (NON_LVALUE_EXPR, type, expr);
 717   else if (type != TREE_TYPE (expr))
 718     expr = build_nop (type, expr);
 719
 720   return expr;
 721 }
 722
 723 \f
 724 struct cplus_array_info
 725 {
 726   tree type;
 727   tree domain;
 728 };
 729
 730 struct cplus_array_hasher : ggc_hasher<tree>
 731 {
 732   typedef cplus_array_info *compare_type;
 733
 734   static hashval_t hash (tree t);
 735   static bool equal (tree, cplus_array_info *);
 736 };
 737
 738 /* Hash an ARRAY_TYPE.  K is really of type `tree'.  */
 739
 740 hashval_t
 741 cplus_array_hasher::hash (tree t)
 742 {
 743   hashval_t hash;
 744
 745   hash = TYPE_UID (TREE_TYPE (t));
 746   if (TYPE_DOMAIN (t))
 747     hash ^= TYPE_UID (TYPE_DOMAIN (t));
 748   return hash;
 749 }
 750
 751 /* Compare two ARRAY_TYPEs.  K1 is really of type `tree', K2 is really
 752    of type `cplus_array_info*'. */
 753
 754 bool
 755 cplus_array_hasher::equal (tree t1, cplus_array_info *t2)
 756 {
 757   return (TREE_TYPE (t1) == t2->type && TYPE_DOMAIN (t1) == t2->domain);
 758 }
 759
 760 /* Hash table containing dependent array types, which are unsuitable for
 761    the language-independent type hash table.  */
 762 static GTY (()) hash_table<cplus_array_hasher> *cplus_array_htab;
 763
 764 /* Build an ARRAY_TYPE without laying it out.  */
 765
 766 static tree
 767 build_min_array_type (tree elt_type, tree index_type)
 768 {
 769   tree t = cxx_make_type (ARRAY_TYPE);
 770   TREE_TYPE (t) = elt_type;
 771   TYPE_DOMAIN (t) = index_type;
 772   return t;
 773 }
 774
 775 /* Set TYPE_CANONICAL like build_array_type_1, but using
 776    build_cplus_array_type.  */
 777
 778 static void
 779 set_array_type_canon (tree t, tree elt_type, tree index_type)
 780 {
 781   /* Set the canonical type for this new node.  */
 782   if (TYPE_STRUCTURAL_EQUALITY_P (elt_type)
 783       || (index_type && TYPE_STRUCTURAL_EQUALITY_P (index_type)))
 784     SET_TYPE_STRUCTURAL_EQUALITY (t);
 785   else if (TYPE_CANONICAL (elt_type) != elt_type
 786            || (index_type && TYPE_CANONICAL (index_type) != index_type))
 787     TYPE_CANONICAL (t)
 788       = build_cplus_array_type (TYPE_CANONICAL (elt_type),
 789                                 index_type
 790                                 ? TYPE_CANONICAL (index_type) : index_type);
 791   else
 792     TYPE_CANONICAL (t) = t;
 793 }
 794
 795 /* Like build_array_type, but handle special C++ semantics: an array of a
 796    variant element type is a variant of the array of the main variant of
 797    the element type.  */
 798
 799 tree
 800 build_cplus_array_type (tree elt_type, tree index_type)
 801 {
 802   tree t;
 803
 804   if (elt_type == error_mark_node || index_type == error_mark_node)
 805     return error_mark_node;
 806
 807   bool dependent
 808     = (processing_template_decl
 809        && (dependent_type_p (elt_type)
 810            || (index_type && !TREE_CONSTANT (TYPE_MAX_VALUE (index_type)))));
 811
 812   if (elt_type != TYPE_MAIN_VARIANT (elt_type))
 813     /* Start with an array of the TYPE_MAIN_VARIANT.  */
 814     t = build_cplus_array_type (TYPE_MAIN_VARIANT (elt_type),
 815                                 index_type);
 816   else if (dependent)
 817     {
 818       /* Since type_hash_canon calls layout_type, we need to use our own
 819          hash table.  */
 820       cplus_array_info cai;
 821       hashval_t hash;
 822
 823       if (cplus_array_htab == NULL)
 824         cplus_array_htab = hash_table<cplus_array_hasher>::create_ggc (61);
 825
 826       hash = TYPE_UID (elt_type);
 827       if (index_type)
 828         hash ^= TYPE_UID (index_type);
 829       cai.type = elt_type;
 830       cai.domain = index_type;
 831
 832       tree *e = cplus_array_htab->find_slot_with_hash (&cai, hash, INSERT);
 833       if (*e)
 834         /* We have found the type: we're done.  */
 835         return (tree) *e;
 836       else
 837         {
 838           /* Build a new array type.  */
 839           t = build_min_array_type (elt_type, index_type);
 840
 841           /* Store it in the hash table. */
 842           *e = t;
 843
 844           /* Set the canonical type for this new node.  */
 845           set_array_type_canon (t, elt_type, index_type);
 846         }
 847     }
 848   else
 849     {
 850       t = build_array_type (elt_type, index_type);
 851     }
 852
 853   /* Now check whether we already have this array variant.  */
 854   if (elt_type != TYPE_MAIN_VARIANT (elt_type))
 855     {
 856       tree m = t;
 857       for (t = m; t; t = TYPE_NEXT_VARIANT (t))
 858         if (TREE_TYPE (t) == elt_type
 859             && TYPE_NAME (t) == NULL_TREE
 860             && TYPE_ATTRIBUTES (t) == NULL_TREE)
 861           break;
 862       if (!t)
 863         {
 864           t = build_min_array_type (elt_type, index_type);
 865           set_array_type_canon (t, elt_type, index_type);
 866           if (!dependent)
 867             layout_type (t);
 868
 869           TYPE_MAIN_VARIANT (t) = m;
 870           TYPE_NEXT_VARIANT (t) = TYPE_NEXT_VARIANT (m);
 871           TYPE_NEXT_VARIANT (m) = t;
 872         }
 873     }
 874
 875   /* Avoid spurious warnings with VLAs (c++/54583).  */
 876   if (TYPE_SIZE (t) && EXPR_P (TYPE_SIZE (t)))
 877     TREE_NO_WARNING (TYPE_SIZE (t)) = 1;
 878
 879   /* Push these needs up to the ARRAY_TYPE so that initialization takes
 880      place more easily.  */
 881   bool needs_ctor = (TYPE_NEEDS_CONSTRUCTING (t)
 882                      = TYPE_NEEDS_CONSTRUCTING (elt_type));
 883   bool needs_dtor = (TYPE_HAS_NONTRIVIAL_DESTRUCTOR (t)
 884                      = TYPE_HAS_NONTRIVIAL_DESTRUCTOR (elt_type));
 885
 886   if (!dependent && t == TYPE_MAIN_VARIANT (t)
 887       && !COMPLETE_TYPE_P (t) && COMPLETE_TYPE_P (elt_type))
 888     {
 889       /* The element type has been completed since the last time we saw
 890          this array type; update the layout and 'tor flags for any variants
 891          that need it.  */
 892       layout_type (t);
 893       for (tree v = TYPE_NEXT_VARIANT (t); v; v = TYPE_NEXT_VARIANT (v))
 894         {
 895           TYPE_NEEDS_CONSTRUCTING (v) = needs_ctor;
 896           TYPE_HAS_NONTRIVIAL_DESTRUCTOR (v) = needs_dtor;
 897         }
 898     }
 899
 900   return t;
 901 }
 902
 903 /* Return an ARRAY_TYPE with element type ELT and length N.  */
 904
 905 tree
 906 build_array_of_n_type (tree elt, int n)
 907 {
 908   return build_cplus_array_type (elt, build_index_type (size_int (n - 1)));
 909 }
 910
 911 /* True iff T is a C++14 array of runtime bound (VLA).  */
 912
 913 bool
 914 array_of_runtime_bound_p (tree t)
 915 {
 916   if (!t || TREE_CODE (t) != ARRAY_TYPE)
 917     return false;
 918   tree dom = TYPE_DOMAIN (t);
 919   if (!dom)
 920     return false;
 921   tree max = TYPE_MAX_VALUE (dom);
 922   return (!potential_rvalue_constant_expression (max)
 923           || (!value_dependent_expression_p (max) && !TREE_CONSTANT (max)));
 924 }
 925
 926 /* Return a reference type node referring to TO_TYPE.  If RVAL is
 927    true, return an rvalue reference type, otherwise return an lvalue
 928    reference type.  If a type node exists, reuse it, otherwise create
 929    a new one.  */
 930 tree
 931 cp_build_reference_type (tree to_type, bool rval)
 932 {
 933   tree lvalue_ref, t;
 934   lvalue_ref = build_reference_type (to_type);
 935   if (!rval)
 936     return lvalue_ref;
 937
 938   /* This code to create rvalue reference types is based on and tied
 939      to the code creating lvalue reference types in the middle-end
 940      functions build_reference_type_for_mode and build_reference_type.
 941
 942      It works by putting the rvalue reference type nodes after the
 943      lvalue reference nodes in the TYPE_NEXT_REF_TO linked list, so
 944      they will effectively be ignored by the middle end.  */
 945
 946   for (t = lvalue_ref; (t = TYPE_NEXT_REF_TO (t)); )
 947     if (TYPE_REF_IS_RVALUE (t))
 948       return t;
 949
 950   t = build_distinct_type_copy (lvalue_ref);
 951
 952   TYPE_REF_IS_RVALUE (t) = true;
 953   TYPE_NEXT_REF_TO (t) = TYPE_NEXT_REF_TO (lvalue_ref);
 954   TYPE_NEXT_REF_TO (lvalue_ref) = t;
 955
 956   if (TYPE_STRUCTURAL_EQUALITY_P (to_type))
 957     SET_TYPE_STRUCTURAL_EQUALITY (t);
 958   else if (TYPE_CANONICAL (to_type) != to_type)
 959     TYPE_CANONICAL (t)
 960       = cp_build_reference_type (TYPE_CANONICAL (to_type), rval);
 961   else
 962     TYPE_CANONICAL (t) = t;
 963
 964   layout_type (t);
 965
 966   return t;
 967
 968 }
 969
 970 /* Returns EXPR cast to rvalue reference type, like std::move.  */
 971
 972 tree
 973 move (tree expr)
 974 {
 975   tree type = TREE_TYPE (expr);
 976   gcc_assert (TREE_CODE (type) != REFERENCE_TYPE);
 977   type = cp_build_reference_type (type, /*rval*/true);
 978   return build_static_cast (type, expr, tf_warning_or_error);
 979 }
 980
 981 /* Used by the C++ front end to build qualified array types.  However,
 982    the C version of this function does not properly maintain canonical
 983    types (which are not used in C).  */
 984 tree
 985 c_build_qualified_type_1 (tree type, int type_quals, tree ARG_UNUSED(layout_qualiefier))
 986 {
 987   return cp_build_qualified_type (type, type_quals);
 988 }
 989
 990 \f
 991 /* Make a variant of TYPE, qualified with the TYPE_QUALS.  Handles
 992    arrays correctly.  In particular, if TYPE is an array of T's, and
 993    TYPE_QUALS is non-empty, returns an array of qualified T's.
 994
 995    FLAGS determines how to deal with ill-formed qualifications. If
 996    tf_ignore_bad_quals is set, then bad qualifications are dropped
 997    (this is permitted if TYPE was introduced via a typedef or template
 998    type parameter). If bad qualifications are dropped and tf_warning
 999    is set, then a warning is issued for non-const qualifications.  If
1000    tf_ignore_bad_quals is not set and tf_error is not set, we
1001    return error_mark_node. Otherwise, we issue an error, and ignore
1002    the qualifications.
1003
1004    Qualification of a reference type is valid when the reference came
1005    via a typedef or template type argument. [dcl.ref] No such
1006    dispensation is provided for qualifying a function type.  [dcl.fct]
1007    DR 295 queries this and the proposed resolution brings it into line
1008    with qualifying a reference.  We implement the DR.  We also behave
1009    in a similar manner for restricting non-pointer types.  */
1010
1011 tree
1012 cp_build_qualified_type_real (tree type,
1013                               int type_quals,
1014                               tsubst_flags_t complain)
1015 {
1016   tree result;
1017   int bad_quals = TYPE_UNQUALIFIED;
1018
1019   if (type == error_mark_node)
1020     return type;
1021
1022   if (type_quals == cp_type_quals (type))
1023     return type;
1024
1025   if (TREE_CODE (type) == ARRAY_TYPE)
1026     {
1027       /* In C++, the qualification really applies to the array element
1028          type.  Obtain the appropriately qualified element type.  */
1029       tree t;
1030       tree element_type
1031         = cp_build_qualified_type_real (TREE_TYPE (type),
1032                                         type_quals,
1033                                         complain);
1034
1035       if (element_type == error_mark_node)
1036         return error_mark_node;
1037
1038       /* See if we already have an identically qualified type.  Tests
1039          should be equivalent to those in check_qualified_type.  */
1040       for (t = TYPE_MAIN_VARIANT (type); t; t = TYPE_NEXT_VARIANT (t))
1041         if (TREE_TYPE (t) == element_type
1042             && TYPE_NAME (t) == TYPE_NAME (type)
1043             && TYPE_CONTEXT (t) == TYPE_CONTEXT (type)
1044             && attribute_list_equal (TYPE_ATTRIBUTES (t),
1045                                      TYPE_ATTRIBUTES (type)))
1046           break;
1047
1048       if (!t)
1049         {
1050           t = build_cplus_array_type (element_type, TYPE_DOMAIN (type));
1051
1052           /* Keep the typedef name.  */
1053           if (TYPE_NAME (t) != TYPE_NAME (type))
1054             {
1055               t = build_variant_type_copy (t);
1056               TYPE_NAME (t) = TYPE_NAME (type);
1057             }
1058         }
1059
1060       /* Even if we already had this variant, we update
1061          TYPE_NEEDS_CONSTRUCTING and TYPE_HAS_NONTRIVIAL_DESTRUCTOR in case
1062          they changed since the variant was originally created.
1063
1064          This seems hokey; if there is some way to use a previous
1065          variant *without* coming through here,
1066          TYPE_NEEDS_CONSTRUCTING will never be updated.  */
1067       TYPE_NEEDS_CONSTRUCTING (t)
1068         = TYPE_NEEDS_CONSTRUCTING (TYPE_MAIN_VARIANT (element_type));
1069       TYPE_HAS_NONTRIVIAL_DESTRUCTOR (t)
1070         = TYPE_HAS_NONTRIVIAL_DESTRUCTOR (TYPE_MAIN_VARIANT (element_type));
1071       return t;
1072     }
1073   else if (TYPE_PTRMEMFUNC_P (type))
1074     {
1075       /* For a pointer-to-member type, we can't just return a
1076          cv-qualified version of the RECORD_TYPE.  If we do, we
1077          haven't changed the field that contains the actual pointer to
1078          a method, and so TYPE_PTRMEMFUNC_FN_TYPE will be wrong.  */
1079       tree t;
1080
1081       t = TYPE_PTRMEMFUNC_FN_TYPE (type);
1082       t = cp_build_qualified_type_real (t, type_quals, complain);
1083       return build_ptrmemfunc_type (t);
1084     }
1085   else if (TREE_CODE (type) == TYPE_PACK_EXPANSION)
1086     {
1087       tree t = PACK_EXPANSION_PATTERN (type);
1088
1089       t = cp_build_qualified_type_real (t, type_quals, complain);
1090       return make_pack_expansion (t);
1091     }
1092
1093   /* A reference or method type shall not be cv-qualified.
1094      [dcl.ref], [dcl.fct].  This used to be an error, but as of DR 295
1095      (in CD1) we always ignore extra cv-quals on functions.  */
1096   if (type_quals & (TYPE_QUAL_CONST | TYPE_QUAL_VOLATILE)
1097       && (TREE_CODE (type) == REFERENCE_TYPE
1098           || TREE_CODE (type) == FUNCTION_TYPE
1099           || TREE_CODE (type) == METHOD_TYPE))
1100     {
1101       if (TREE_CODE (type) == REFERENCE_TYPE)
1102         bad_quals |= type_quals & (TYPE_QUAL_CONST | TYPE_QUAL_VOLATILE);
1103       type_quals &= ~(TYPE_QUAL_CONST | TYPE_QUAL_VOLATILE);
1104     }
1105
1106   /* But preserve any function-cv-quals on a FUNCTION_TYPE.  */
1107   if (TREE_CODE (type) == FUNCTION_TYPE)
1108     type_quals |= type_memfn_quals (type);
1109
1110   /* A restrict-qualified type must be a pointer (or reference)
1111      to object or incomplete type. */
1112   if ((type_quals & TYPE_QUAL_RESTRICT)
1113       && TREE_CODE (type) != TEMPLATE_TYPE_PARM
1114       && TREE_CODE (type) != TYPENAME_TYPE
1115       && !POINTER_TYPE_P (type))
1116     {
1117       bad_quals |= TYPE_QUAL_RESTRICT;
1118       type_quals &= ~TYPE_QUAL_RESTRICT;
1119     }
1120
1121   if (bad_quals == TYPE_UNQUALIFIED
1122       || (complain & tf_ignore_bad_quals))
1123     /*OK*/;
1124   else if (!(complain & tf_error))
1125     return error_mark_node;
1126   else
1127     {
1128       tree bad_type = build_qualified_type (ptr_type_node, bad_quals);
1129       error ("%qV qualifiers cannot be applied to %qT",
1130              bad_type, type);
1131     }
1132
1133   /* Retrieve (or create) the appropriately qualified variant.  */
1134   result = build_qualified_type (type, type_quals);
1135
1136   /* Preserve exception specs and ref-qualifier since build_qualified_type
1137      doesn't know about them.  */
1138   if (TREE_CODE (result) == FUNCTION_TYPE
1139       || TREE_CODE (result) == METHOD_TYPE)
1140     {
1141       result = build_exception_variant (result, TYPE_RAISES_EXCEPTIONS (type));
1142       result = build_ref_qualified_type (result, type_memfn_rqual (type));
1143     }
1144
1145   /* If this was a pointer-to-method type, and we just made a copy,
1146      then we need to unshare the record that holds the cached
1147      pointer-to-member-function type, because these will be distinct
1148      between the unqualified and qualified types.  */
1149   if (result != type
1150       && TYPE_PTR_P (type)
1151       && TREE_CODE (TREE_TYPE (type)) == METHOD_TYPE
1152       && TYPE_LANG_SPECIFIC (result) == TYPE_LANG_SPECIFIC (type))
1153     TYPE_LANG_SPECIFIC (result) = NULL;
1154
1155   /* We may also have ended up building a new copy of the canonical
1156      type of a pointer-to-method type, which could have the same
1157      sharing problem described above.  */
1158   if (TYPE_CANONICAL (result) != TYPE_CANONICAL (type)
1159       && TYPE_PTR_P (type)
1160       && TREE_CODE (TREE_TYPE (type)) == METHOD_TYPE
1161       && (TYPE_LANG_SPECIFIC (TYPE_CANONICAL (result))
1162           == TYPE_LANG_SPECIFIC (TYPE_CANONICAL (type))))
1163     TYPE_LANG_SPECIFIC (TYPE_CANONICAL (result)) = NULL;
1164
1165   return result;
1166 }
1167
1168 /* Return TYPE with const and volatile removed.  */
1169
1170 tree
1171 cv_unqualified (tree type)
1172 {
1173   int quals;
1174
1175   if (type == error_mark_node)
1176     return type;
1177
1178   quals = cp_type_quals (type);
1179   quals &= ~(TYPE_QUAL_CONST|TYPE_QUAL_VOLATILE);
1180   return cp_build_qualified_type (type, quals);
1181 }
1182
1183 /* Builds a qualified variant of T that is not a typedef variant.
1184    E.g. consider the following declarations:
1185      typedef const int ConstInt;
1186      typedef ConstInt* PtrConstInt;
1187    If T is PtrConstInt, this function returns a type representing
1188      const int*.
1189    In other words, if T is a typedef, the function returns the underlying type.
1190    The cv-qualification and attributes of the type returned match the
1191    input type.
1192    They will always be compatible types.
1193    The returned type is built so that all of its subtypes
1194    recursively have their typedefs stripped as well.
1195
1196    This is different from just returning TYPE_CANONICAL (T)
1197    Because of several reasons:
1198     * If T is a type that needs structural equality
1199       its TYPE_CANONICAL (T) will be NULL.
1200     * TYPE_CANONICAL (T) desn't carry type attributes
1201       and loses template parameter names.   */
1202
1203 tree
1204 strip_typedefs (tree t)
1205 {
1206   tree result = NULL, type = NULL, t0 = NULL;
1207
1208   if (!t || t == error_mark_node)
1209     return t;
1210
1211   if (TREE_CODE (t) == TREE_LIST)
1212     {
1213       bool changed = false;
1214       vec<tree,va_gc> *vec = make_tree_vector ();
1215       for (; t; t = TREE_CHAIN (t))
1216         {
1217           gcc_assert (!TREE_PURPOSE (t));
1218           tree elt = strip_typedefs (TREE_VALUE (t));
1219           if (elt != TREE_VALUE (t))
1220             changed = true;
1221           vec_safe_push (vec, elt);
1222         }
1223       tree r = t;
1224       if (changed)
1225         r = build_tree_list_vec (vec);
1226       release_tree_vector (vec);
1227       return r;
1228     }
1229
1230   gcc_assert (TYPE_P (t));
1231
1232   if (t == TYPE_CANONICAL (t))
1233     return t;
1234
1235   switch (TREE_CODE (t))
1236     {
1237     case POINTER_TYPE:
1238       type = strip_typedefs (TREE_TYPE (t));
1239       result = build_pointer_type (type);
1240       break;
1241     case REFERENCE_TYPE:
1242       type = strip_typedefs (TREE_TYPE (t));
1243       result = cp_build_reference_type (type, TYPE_REF_IS_RVALUE (t));
1244       break;
1245     case OFFSET_TYPE:
1246       t0 = strip_typedefs (TYPE_OFFSET_BASETYPE (t));
1247       type = strip_typedefs (TREE_TYPE (t));
1248       result = build_offset_type (t0, type);
1249       break;
1250     case RECORD_TYPE:
1251       if (TYPE_PTRMEMFUNC_P (t))
1252         {
1253           t0 = strip_typedefs (TYPE_PTRMEMFUNC_FN_TYPE (t));
1254           result = build_ptrmemfunc_type (t0);
1255         }
1256       break;
1257     case ARRAY_TYPE:
1258       type = strip_typedefs (TREE_TYPE (t));
1259       t0  = strip_typedefs (TYPE_DOMAIN (t));;
1260       result = build_cplus_array_type (type, t0);
1261       break;
1262     case FUNCTION_TYPE:
1263     case METHOD_TYPE:
1264       {
1265         tree arg_types = NULL, arg_node, arg_type;
1266         for (arg_node = TYPE_ARG_TYPES (t);
1267              arg_node;
1268              arg_node = TREE_CHAIN (arg_node))
1269           {
1270             if (arg_node == void_list_node)
1271               break;
1272             arg_type = strip_typedefs (TREE_VALUE (arg_node));
1273             gcc_assert (arg_type);
1274
1275             arg_types =
1276               tree_cons (TREE_PURPOSE (arg_node), arg_type, arg_types);
1277           }
1278
1279         if (arg_types)
1280           arg_types = nreverse (arg_types);
1281
1282         /* A list of parameters not ending with an ellipsis
1283            must end with void_list_node.  */
1284         if (arg_node)
1285           arg_types = chainon (arg_types, void_list_node);
1286
1287         type = strip_typedefs (TREE_TYPE (t));
1288         if (TREE_CODE (t) == METHOD_TYPE)
1289           {
1290             tree class_type = TREE_TYPE (TREE_VALUE (arg_types));
1291             gcc_assert (class_type);
1292             result =
1293               build_method_type_directly (class_type, type,
1294                                           TREE_CHAIN (arg_types));
1295             result
1296               = build_ref_qualified_type (result, type_memfn_rqual (t));
1297           }
1298         else
1299           {
1300             result = build_function_type (type,
1301                                           arg_types);
1302             result = apply_memfn_quals (result,
1303                                         type_memfn_quals (t),
1304                                         type_memfn_rqual (t));
1305           }
1306
1307         if (TYPE_RAISES_EXCEPTIONS (t))
1308           result = build_exception_variant (result,
1309                                             TYPE_RAISES_EXCEPTIONS (t));
1310         if (TYPE_HAS_LATE_RETURN_TYPE (t))
1311           TYPE_HAS_LATE_RETURN_TYPE (result) = 1;
1312       }
1313       break;
1314     case TYPENAME_TYPE:
1315       {
1316         tree fullname = TYPENAME_TYPE_FULLNAME (t);
1317         if (TREE_CODE (fullname) == TEMPLATE_ID_EXPR
1318             && TREE_OPERAND (fullname, 1))
1319           {
1320             tree args = TREE_OPERAND (fullname, 1);
1321             tree new_args = copy_node (args);
1322             bool changed = false;
1323             for (int i = 0; i < TREE_VEC_LENGTH (args); ++i)
1324               {
1325                 tree arg = TREE_VEC_ELT (args, i);
1326                 tree strip_arg;
1327                 if (TYPE_P (arg))
1328                   strip_arg = strip_typedefs (arg);
1329                 else
1330                   strip_arg = strip_typedefs_expr (arg);
1331                 TREE_VEC_ELT (new_args, i) = strip_arg;
1332                 if (strip_arg != arg)
1333                   changed = true;
1334               }
1335             if (changed)
1336               {
1337                 NON_DEFAULT_TEMPLATE_ARGS_COUNT (new_args)
1338                   = NON_DEFAULT_TEMPLATE_ARGS_COUNT (args);
1339                 fullname
1340                   = lookup_template_function (TREE_OPERAND (fullname, 0),
1341                                               new_args);
1342               }
1343             else
1344               ggc_free (new_args);
1345           }
1346         result = make_typename_type (strip_typedefs (TYPE_CONTEXT (t)),
1347                                      fullname, typename_type, tf_none);
1348       }
1349       break;
1350     case DECLTYPE_TYPE:
1351       result = strip_typedefs_expr (DECLTYPE_TYPE_EXPR (t));
1352       if (result == DECLTYPE_TYPE_EXPR (t))
1353         return t;
1354       else
1355         result = (finish_decltype_type
1356                   (result,
1357                    DECLTYPE_TYPE_ID_EXPR_OR_MEMBER_ACCESS_P (t),
1358                    tf_none));
1359       break;
1360     default:
1361       break;
1362     }
1363
1364   if (!result)
1365       result = TYPE_MAIN_VARIANT (t);
1366   if (TYPE_USER_ALIGN (t) != TYPE_USER_ALIGN (result)
1367       || TYPE_ALIGN (t) != TYPE_ALIGN (result))
1368     {
1369       gcc_assert (TYPE_USER_ALIGN (t));
1370       if (TYPE_ALIGN (t) == TYPE_ALIGN (result))
1371         result = build_variant_type_copy (result);
1372       else
1373         result = build_aligned_type (result, TYPE_ALIGN (t));
1374       TYPE_USER_ALIGN (result) = true;
1375     }
1376   if (TYPE_ATTRIBUTES (t))
1377     result = cp_build_type_attribute_variant (result, TYPE_ATTRIBUTES (t));
1378   return cp_build_qualified_type (result, cp_type_quals (t));
1379 }
1380
1381 /* Like strip_typedefs above, but works on expressions, so that in
1382
1383    template<class T> struct A
1384    {
1385      typedef T TT;
1386      B<sizeof(TT)> b;
1387    };
1388
1389    sizeof(TT) is replaced by sizeof(T).  */
1390
1391 tree
1392 strip_typedefs_expr (tree t)
1393 {
1394   unsigned i,n;
1395   tree r, type, *ops;
1396   enum tree_code code;
1397
1398   if (t == NULL_TREE || t == error_mark_node)
1399     return t;
1400
1401   if (DECL_P (t) || CONSTANT_CLASS_P (t))
1402     return t;
1403
1404   /* Some expressions have type operands, so let's handle types here rather
1405      than check TYPE_P in multiple places below.  */
1406   if (TYPE_P (t))
1407     return strip_typedefs (t);
1408
1409   code = TREE_CODE (t);
1410   switch (code)
1411     {
1412     case IDENTIFIER_NODE:
1413     case TEMPLATE_PARM_INDEX:
1414     case OVERLOAD:
1415     case BASELINK:
1416     case ARGUMENT_PACK_SELECT:
1417       return t;
1418
1419     case TRAIT_EXPR:
1420       {
1421         tree type1 = strip_typedefs (TRAIT_EXPR_TYPE1 (t));
1422         tree type2 = strip_typedefs (TRAIT_EXPR_TYPE2 (t));
1423         if (type1 == TRAIT_EXPR_TYPE1 (t)
1424             && type2 == TRAIT_EXPR_TYPE2 (t))
1425           return t;
1426         r = copy_node (t);
1427         TRAIT_EXPR_TYPE1 (t) = type1;
1428         TRAIT_EXPR_TYPE2 (t) = type2;
1429         return r;
1430       }
1431
1432     case TREE_LIST:
1433       {
1434         vec<tree, va_gc> *vec = make_tree_vector ();
1435         bool changed = false;
1436         tree it;
1437         for (it = t; it; it = TREE_CHAIN (it))
1438           {
1439             tree val = strip_typedefs_expr (TREE_VALUE (t));
1440             vec_safe_push (vec, val);
1441             if (val != TREE_VALUE (t))
1442               changed = true;
1443             gcc_assert (TREE_PURPOSE (it) == NULL_TREE);
1444           }
1445         if (changed)
1446           {
1447             r = NULL_TREE;
1448             FOR_EACH_VEC_ELT_REVERSE (*vec, i, it)
1449               r = tree_cons (NULL_TREE, it, r);
1450           }
1451         else
1452           r = t;
1453         release_tree_vector (vec);
1454         return r;
1455       }
1456
1457     case TREE_VEC:
1458       {
1459         bool changed = false;
1460         vec<tree, va_gc> *vec = make_tree_vector ();
1461         n = TREE_VEC_LENGTH (t);
1462         vec_safe_reserve (vec, n);
1463         for (i = 0; i < n; ++i)
1464           {
1465             tree op = strip_typedefs_expr (TREE_VEC_ELT (t, i));
1466             vec->quick_push (op);
1467             if (op != TREE_VEC_ELT (t, i))
1468               changed = true;
1469           }
1470         if (changed)
1471           {
1472             r = copy_node (t);
1473             for (i = 0; i < n; ++i)
1474               TREE_VEC_ELT (r, i) = (*vec)[i];
1475             NON_DEFAULT_TEMPLATE_ARGS_COUNT (r)
1476               = NON_DEFAULT_TEMPLATE_ARGS_COUNT (t);
1477           }
1478         else
1479           r = t;
1480         release_tree_vector (vec);
1481         return r;
1482       }
1483
1484     case CONSTRUCTOR:
1485       {
1486         bool changed = false;
1487         vec<constructor_elt, va_gc> *vec
1488           = vec_safe_copy (CONSTRUCTOR_ELTS (t));
1489         n = CONSTRUCTOR_NELTS (t);
1490         type = strip_typedefs (TREE_TYPE (t));
1491         for (i = 0; i < n; ++i)
1492           {
1493             constructor_elt *e = &(*vec)[i];
1494             tree op = strip_typedefs_expr (e->value);
1495             if (op != e->value)
1496               {
1497                 changed = true;
1498                 e->value = op;
1499               }
1500             gcc_checking_assert (e->index == strip_typedefs_expr (e->index));
1501           }
1502
1503         if (!changed && type == TREE_TYPE (t))
1504           {
1505             vec_free (vec);
1506             return t;
1507           }
1508         else
1509           {
1510             r = copy_node (t);
1511             TREE_TYPE (r) = type;
1512             CONSTRUCTOR_ELTS (r) = vec;
1513             return r;
1514           }
1515       }
1516
1517     case LAMBDA_EXPR:
1518       error ("lambda-expression in a constant expression");
1519       return error_mark_node;
1520
1521     default:
1522       break;
1523     }
1524
1525   gcc_assert (EXPR_P (t));
1526
1527   n = TREE_OPERAND_LENGTH (t);
1528   ops = XALLOCAVEC (tree, n);
1529   type = TREE_TYPE (t);
1530
1531   switch (code)
1532     {
1533     CASE_CONVERT:
1534     case IMPLICIT_CONV_EXPR:
1535     case DYNAMIC_CAST_EXPR:
1536     case STATIC_CAST_EXPR:
1537     case CONST_CAST_EXPR:
1538     case REINTERPRET_CAST_EXPR:
1539     case CAST_EXPR:
1540     case NEW_EXPR:
1541       type = strip_typedefs (type);
1542       /* fallthrough */
1543
1544     default:
1545       for (i = 0; i < n; ++i)
1546         ops[i] = strip_typedefs_expr (TREE_OPERAND (t, i));
1547       break;
1548     }
1549
1550   /* If nothing changed, return t.  */
1551   for (i = 0; i < n; ++i)
1552     if (ops[i] != TREE_OPERAND (t, i))
1553       break;
1554   if (i == n && type == TREE_TYPE (t))
1555     return t;
1556
1557   r = copy_node (t);
1558   TREE_TYPE (r) = type;
1559   for (i = 0; i < n; ++i)
1560     TREE_OPERAND (r, i) = ops[i];
1561   return r;
1562 }
1563
1564 /* Makes a copy of BINFO and TYPE, which is to be inherited into a
1565    graph dominated by T.  If BINFO is NULL, TYPE is a dependent base,
1566    and we do a shallow copy.  If BINFO is non-NULL, we do a deep copy.
1567    VIRT indicates whether TYPE is inherited virtually or not.
1568    IGO_PREV points at the previous binfo of the inheritance graph
1569    order chain.  The newly copied binfo's TREE_CHAIN forms this
1570    ordering.
1571
1572    The CLASSTYPE_VBASECLASSES vector of T is constructed in the
1573    correct order. That is in the order the bases themselves should be
1574    constructed in.
1575
1576    The BINFO_INHERITANCE of a virtual base class points to the binfo
1577    of the most derived type. ??? We could probably change this so that
1578    BINFO_INHERITANCE becomes synonymous with BINFO_PRIMARY, and hence
1579    remove a field.  They currently can only differ for primary virtual
1580    virtual bases.  */
1581
1582 tree
1583 copy_binfo (tree binfo, tree type, tree t, tree *igo_prev, int virt)
1584 {
1585   tree new_binfo;
1586
1587   if (virt)
1588     {
1589       /* See if we've already made this virtual base.  */
1590       new_binfo = binfo_for_vbase (type, t);
1591       if (new_binfo)
1592         return new_binfo;
1593     }
1594
1595   new_binfo = make_tree_binfo (binfo ? BINFO_N_BASE_BINFOS (binfo) : 0);
1596   BINFO_TYPE (new_binfo) = type;
1597
1598   /* Chain it into the inheritance graph.  */
1599   TREE_CHAIN (*igo_prev) = new_binfo;
1600   *igo_prev = new_binfo;
1601
1602   if (binfo && !BINFO_DEPENDENT_BASE_P (binfo))
1603     {
1604       int ix;
1605       tree base_binfo;
1606
1607       gcc_assert (SAME_BINFO_TYPE_P (BINFO_TYPE (binfo), type));
1608
1609       BINFO_OFFSET (new_binfo) = BINFO_OFFSET (binfo);
1610       BINFO_VIRTUALS (new_binfo) = BINFO_VIRTUALS (binfo);
1611
1612       /* We do not need to copy the accesses, as they are read only.  */
1613       BINFO_BASE_ACCESSES (new_binfo) = BINFO_BASE_ACCESSES (binfo);
1614
1615       /* Recursively copy base binfos of BINFO.  */
1616       for (ix = 0; BINFO_BASE_ITERATE (binfo, ix, base_binfo); ix++)
1617         {
1618           tree new_base_binfo;
1619           new_base_binfo = copy_binfo (base_binfo, BINFO_TYPE (base_binfo),
1620                                        t, igo_prev,
1621                                        BINFO_VIRTUAL_P (base_binfo));
1622
1623           if (!BINFO_INHERITANCE_CHAIN (new_base_binfo))
1624             BINFO_INHERITANCE_CHAIN (new_base_binfo) = new_binfo;
1625           BINFO_BASE_APPEND (new_binfo, new_base_binfo);
1626         }
1627     }
1628   else
1629     BINFO_DEPENDENT_BASE_P (new_binfo) = 1;
1630
1631   if (virt)
1632     {
1633       /* Push it onto the list after any virtual bases it contains
1634          will have been pushed.  */
1635       CLASSTYPE_VBASECLASSES (t)->quick_push (new_binfo);
1636       BINFO_VIRTUAL_P (new_binfo) = 1;
1637       BINFO_INHERITANCE_CHAIN (new_binfo) = TYPE_BINFO (t);
1638     }
1639
1640   return new_binfo;
1641 }
1642 \f
1643 /* Hashing of lists so that we don't make duplicates.
1644    The entry point is `list_hash_canon'.  */
1645
1646 struct list_proxy
1647 {
1648   tree purpose;
1649   tree value;
1650   tree chain;
1651 };
1652
1653 struct list_hasher : ggc_hasher<tree>
1654 {
1655   typedef list_proxy *compare_type;
1656
1657   static hashval_t hash (tree);
1658   static bool equal (tree, list_proxy *);
1659 };
1660
1661 /* Now here is the hash table.  When recording a list, it is added
1662    to the slot whose index is the hash code mod the table size.
1663    Note that the hash table is used for several kinds of lists.
1664    While all these live in the same table, they are completely independent,
1665    and the hash code is computed differently for each of these.  */
1666
1667 static GTY (()) hash_table<list_hasher> *list_hash_table;
1668
1669 /* Compare ENTRY (an entry in the hash table) with DATA (a list_proxy
1670    for a node we are thinking about adding).  */
1671
1672 bool
1673 list_hasher::equal (tree t, list_proxy *proxy)
1674 {
1675   return (TREE_VALUE (t) == proxy->value
1676           && TREE_PURPOSE (t) == proxy->purpose
1677           && TREE_CHAIN (t) == proxy->chain);
1678 }
1679
1680 /* Compute a hash code for a list (chain of TREE_LIST nodes
1681    with goodies in the TREE_PURPOSE, TREE_VALUE, and bits of the
1682    TREE_COMMON slots), by adding the hash codes of the individual entries.  */
1683
1684 static hashval_t
1685 list_hash_pieces (tree purpose, tree value, tree chain)
1686 {
1687   hashval_t hashcode = 0;
1688
1689   if (chain)
1690     hashcode += TREE_HASH (chain);
1691
1692   if (value)
1693     hashcode += TREE_HASH (value);
1694   else
1695     hashcode += 1007;
1696   if (purpose)
1697     hashcode += TREE_HASH (purpose);
1698   else
1699     hashcode += 1009;
1700   return hashcode;
1701 }
1702
1703 /* Hash an already existing TREE_LIST.  */
1704
1705 hashval_t
1706 list_hasher::hash (tree t)
1707 {
1708   return list_hash_pieces (TREE_PURPOSE (t),
1709                            TREE_VALUE (t),
1710                            TREE_CHAIN (t));
1711 }
1712
1713 /* Given list components PURPOSE, VALUE, AND CHAIN, return the canonical
1714    object for an identical list if one already exists.  Otherwise, build a
1715    new one, and record it as the canonical object.  */
1716
1717 tree
1718 hash_tree_cons (tree purpose, tree value, tree chain)
1719 {
1720   int hashcode = 0;
1721   tree *slot;
1722   struct list_proxy proxy;
1723
1724   /* Hash the list node.  */
1725   hashcode = list_hash_pieces (purpose, value, chain);
1726   /* Create a proxy for the TREE_LIST we would like to create.  We
1727      don't actually create it so as to avoid creating garbage.  */
1728   proxy.purpose = purpose;
1729   proxy.value = value;
1730   proxy.chain = chain;
1731   /* See if it is already in the table.  */
1732   slot = list_hash_table->find_slot_with_hash (&proxy, hashcode, INSERT);
1733   /* If not, create a new node.  */
1734   if (!*slot)
1735     *slot = tree_cons (purpose, value, chain);
1736   return (tree) *slot;
1737 }
1738
1739 /* Constructor for hashed lists.  */
1740
1741 tree
1742 hash_tree_chain (tree value, tree chain)
1743 {
1744   return hash_tree_cons (NULL_TREE, value, chain);
1745 }
1746 \f
1747 void
1748 debug_binfo (tree elem)
1749 {
1750   HOST_WIDE_INT n;
1751   tree virtuals;
1752
1753   fprintf (stderr, "type \"%s\", offset = " HOST_WIDE_INT_PRINT_DEC
1754            "\nvtable type:\n",
1755            TYPE_NAME_STRING (BINFO_TYPE (elem)),
1756            TREE_INT_CST_LOW (BINFO_OFFSET (elem)));
1757   debug_tree (BINFO_TYPE (elem));
1758   if (BINFO_VTABLE (elem))
1759     fprintf (stderr, "vtable decl \"%s\"\n",
1760              IDENTIFIER_POINTER (DECL_NAME (get_vtbl_decl_for_binfo (elem))));
1761   else
1762     fprintf (stderr, "no vtable decl yet\n");
1763   fprintf (stderr, "virtuals:\n");
1764   virtuals = BINFO_VIRTUALS (elem);
1765   n = 0;
1766
1767   while (virtuals)
1768     {
1769       tree fndecl = TREE_VALUE (virtuals);
1770       fprintf (stderr, "%s [%ld =? %ld]\n",
1771                IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (fndecl)),
1772                (long) n, (long) TREE_INT_CST_LOW (DECL_VINDEX (fndecl)));
1773       ++n;
1774       virtuals = TREE_CHAIN (virtuals);
1775     }
1776 }
1777
1778 /* Build a representation for the qualified name SCOPE::NAME.  TYPE is
1779    the type of the result expression, if known, or NULL_TREE if the
1780    resulting expression is type-dependent.  If TEMPLATE_P is true,
1781    NAME is known to be a template because the user explicitly used the
1782    "template" keyword after the "::".
1783
1784    All SCOPE_REFs should be built by use of this function.  */
1785
1786 tree
1787 build_qualified_name (tree type, tree scope, tree name, bool template_p)
1788 {
1789   tree t;
1790   if (type == error_mark_node
1791       || scope == error_mark_node
1792       || name == error_mark_node)
1793     return error_mark_node;
1794   t = build2 (SCOPE_REF, type, scope, name);
1795   QUALIFIED_NAME_IS_TEMPLATE (t) = template_p;
1796   PTRMEM_OK_P (t) = true;
1797   if (type)
1798     t = convert_from_reference (t);
1799   return t;
1800 }
1801
1802 /* Like check_qualified_type, but also check ref-qualifier and exception
1803    specification.  */
1804
1805 static bool
1806 cp_check_qualified_type (const_tree cand, const_tree base, int type_quals,
1807                          cp_ref_qualifier rqual, tree raises)
1808 {
1809   return (check_qualified_type (cand, base, type_quals, NULL_TREE)
1810           && comp_except_specs (raises, TYPE_RAISES_EXCEPTIONS (cand),
1811                                 ce_exact)
1812           && type_memfn_rqual (cand) == rqual);
1813 }
1814
1815 /* Build the FUNCTION_TYPE or METHOD_TYPE with the ref-qualifier RQUAL.  */
1816
1817 tree
1818 build_ref_qualified_type (tree type, cp_ref_qualifier rqual)
1819 {
1820   tree t;
1821
1822   if (rqual == type_memfn_rqual (type))
1823     return type;
1824
1825   int type_quals = TYPE_QUALS (type);
1826   tree raises = TYPE_RAISES_EXCEPTIONS (type);
1827   for (t = TYPE_MAIN_VARIANT (type); t; t = TYPE_NEXT_VARIANT (t))
1828     if (cp_check_qualified_type (t, type, type_quals, rqual, raises))
1829       return t;
1830
1831   t = build_variant_type_copy (type);
1832   switch (rqual)
1833     {
1834     case REF_QUAL_RVALUE:
1835       FUNCTION_RVALUE_QUALIFIED (t) = 1;
1836       FUNCTION_REF_QUALIFIED (t) = 1;
1837       break;
1838     case REF_QUAL_LVALUE:
1839       FUNCTION_RVALUE_QUALIFIED (t) = 0;
1840       FUNCTION_REF_QUALIFIED (t) = 1;
1841       break;
1842     default:
1843       FUNCTION_REF_QUALIFIED (t) = 0;
1844       break;
1845     }
1846
1847   if (TYPE_STRUCTURAL_EQUALITY_P (type))
1848     /* Propagate structural equality. */
1849     SET_TYPE_STRUCTURAL_EQUALITY (t);
1850   else if (TYPE_CANONICAL (type) != type)
1851     /* Build the underlying canonical type, since it is different
1852        from TYPE. */
1853     TYPE_CANONICAL (t) = build_ref_qualified_type (TYPE_CANONICAL (type),
1854                                                    rqual);
1855   else
1856     /* T is its own canonical type. */
1857     TYPE_CANONICAL (t) = t;
1858
1859   return t;
1860 }
1861
1862 /* Returns nonzero if X is an expression for a (possibly overloaded)
1863    function.  If "f" is a function or function template, "f", "c->f",
1864    "c.f", "C::f", and "f<int>" will all be considered possibly
1865    overloaded functions.  Returns 2 if the function is actually
1866    overloaded, i.e., if it is impossible to know the type of the
1867    function without performing overload resolution.  */
1868
1869 int
1870 is_overloaded_fn (tree x)
1871 {
1872   /* A baselink is also considered an overloaded function.  */
1873   if (TREE_CODE (x) == OFFSET_REF
1874       || TREE_CODE (x) == COMPONENT_REF)
1875     x = TREE_OPERAND (x, 1);
1876   if (BASELINK_P (x))
1877     x = BASELINK_FUNCTIONS (x);
1878   if (TREE_CODE (x) == TEMPLATE_ID_EXPR)
1879     x = TREE_OPERAND (x, 0);
1880   if (DECL_FUNCTION_TEMPLATE_P (OVL_CURRENT (x))
1881       || (TREE_CODE (x) == OVERLOAD && OVL_CHAIN (x)))
1882     return 2;
1883   return  (TREE_CODE (x) == FUNCTION_DECL
1884            || TREE_CODE (x) == OVERLOAD);
1885 }
1886
1887 /* X is the CALL_EXPR_FN of a CALL_EXPR.  If X represents a dependent name
1888    (14.6.2), return the IDENTIFIER_NODE for that name.  Otherwise, return
1889    NULL_TREE.  */
1890
1891 tree
1892 dependent_name (tree x)
1893 {
1894   if (identifier_p (x))
1895     return x;
1896   if (TREE_CODE (x) != COMPONENT_REF
1897       && TREE_CODE (x) != OFFSET_REF
1898       && TREE_CODE (x) != BASELINK
1899       && is_overloaded_fn (x))
1900     return DECL_NAME (get_first_fn (x));
1901   return NULL_TREE;
1902 }
1903
1904 /* Returns true iff X is an expression for an overloaded function
1905    whose type cannot be known without performing overload
1906    resolution.  */
1907
1908 bool
1909 really_overloaded_fn (tree x)
1910 {
1911   return is_overloaded_fn (x) == 2;
1912 }
1913
1914 tree
1915 get_fns (tree from)
1916 {
1917   gcc_assert (is_overloaded_fn (from));
1918   /* A baselink is also considered an overloaded function.  */
1919   if (TREE_CODE (from) == OFFSET_REF
1920       || TREE_CODE (from) == COMPONENT_REF)
1921     from = TREE_OPERAND (from, 1);
1922   if (BASELINK_P (from))
1923     from = BASELINK_FUNCTIONS (from);
1924   if (TREE_CODE (from) == TEMPLATE_ID_EXPR)
1925     from = TREE_OPERAND (from, 0);
1926   return from;
1927 }
1928
1929 tree
1930 get_first_fn (tree from)
1931 {
1932   return OVL_CURRENT (get_fns (from));
1933 }
1934
1935 /* Return a new OVL node, concatenating it with the old one.  */
1936
1937 tree
1938 ovl_cons (tree decl, tree chain)
1939 {
1940   tree result = make_node (OVERLOAD);
1941   TREE_TYPE (result) = unknown_type_node;
1942   OVL_FUNCTION (result) = decl;
1943   TREE_CHAIN (result) = chain;
1944
1945   return result;
1946 }
1947
1948 /* Build a new overloaded function. If this is the first one,
1949    just return it; otherwise, ovl_cons the _DECLs */
1950
1951 tree
1952 build_overload (tree decl, tree chain)
1953 {
1954   if (! chain && TREE_CODE (decl) != TEMPLATE_DECL)
1955     return decl;
1956   return ovl_cons (decl, chain);
1957 }
1958
1959 /* Return the scope where the overloaded functions OVL were found.  */
1960
1961 tree
1962 ovl_scope (tree ovl)
1963 {
1964   if (TREE_CODE (ovl) == OFFSET_REF
1965       || TREE_CODE (ovl) == COMPONENT_REF)
1966     ovl = TREE_OPERAND (ovl, 1);
1967   if (TREE_CODE (ovl) == BASELINK)
1968     return BINFO_TYPE (BASELINK_BINFO (ovl));
1969   if (TREE_CODE (ovl) == TEMPLATE_ID_EXPR)
1970     ovl = TREE_OPERAND (ovl, 0);
1971   /* Skip using-declarations.  */
1972   while (TREE_CODE (ovl) == OVERLOAD && OVL_USED (ovl) && OVL_CHAIN (ovl))
1973     ovl = OVL_CHAIN (ovl);
1974   return CP_DECL_CONTEXT (OVL_CURRENT (ovl));
1975 }
1976
1977 /* Return TRUE if FN is a non-static member function, FALSE otherwise.
1978    This function looks into BASELINK and OVERLOAD nodes.  */
1979
1980 bool
1981 non_static_member_function_p (tree fn)
1982 {
1983   if (fn == NULL_TREE)
1984     return false;
1985
1986   if (is_overloaded_fn (fn))
1987     fn = get_first_fn (fn);
1988
1989   return (DECL_P (fn)
1990           && DECL_NONSTATIC_MEMBER_FUNCTION_P (fn));
1991 }
1992
1993 \f
1994 #define PRINT_RING_SIZE 4
1995
1996 static const char *
1997 cxx_printable_name_internal (tree decl, int v, bool translate)
1998 {
1999   static unsigned int uid_ring[PRINT_RING_SIZE];
2000   static char *print_ring[PRINT_RING_SIZE];
2001   static bool trans_ring[PRINT_RING_SIZE];
2002   static int ring_counter;
2003   int i;
2004
2005   /* Only cache functions.  */
2006   if (v < 2
2007       || TREE_CODE (decl) != FUNCTION_DECL
2008       || DECL_LANG_SPECIFIC (decl) == 0)
2009     return lang_decl_name (decl, v, translate);
2010
2011   /* See if this print name is lying around.  */
2012   for (i = 0; i < PRINT_RING_SIZE; i++)
2013     if (uid_ring[i] == DECL_UID (decl) && translate == trans_ring[i])
2014       /* yes, so return it.  */
2015       return print_ring[i];
2016
2017   if (++ring_counter == PRINT_RING_SIZE)
2018     ring_counter = 0;
2019
2020   if (current_function_decl != NULL_TREE)
2021     {
2022       /* There may be both translated and untranslated versions of the
2023          name cached.  */
2024       for (i = 0; i < 2; i++)
2025         {
2026           if (uid_ring[ring_counter] == DECL_UID (current_function_decl))
2027             ring_counter += 1;
2028           if (ring_counter == PRINT_RING_SIZE)
2029             ring_counter = 0;
2030         }
2031       gcc_assert (uid_ring[ring_counter] != DECL_UID (current_function_decl));
2032     }
2033
2034   free (print_ring[ring_counter]);
2035
2036   print_ring[ring_counter] = xstrdup (lang_decl_name (decl, v, translate));
2037   uid_ring[ring_counter] = DECL_UID (decl);
2038   trans_ring[ring_counter] = translate;
2039   return print_ring[ring_counter];
2040 }
2041
2042 const char *
2043 cxx_printable_name (tree decl, int v)
2044 {
2045   return cxx_printable_name_internal (decl, v, false);
2046 }
2047
2048 const char *
2049 cxx_printable_name_translate (tree decl, int v)
2050 {
2051   return cxx_printable_name_internal (decl, v, true);
2052 }
2053 \f
2054 /* Build the FUNCTION_TYPE or METHOD_TYPE which may throw exceptions
2055    listed in RAISES.  */
2056
2057 tree
2058 build_exception_variant (tree type, tree raises)
2059 {
2060   tree v;
2061   int type_quals;
2062
2063   if (comp_except_specs (raises, TYPE_RAISES_EXCEPTIONS (type), ce_exact))
2064     return type;
2065
2066   type_quals = TYPE_QUALS (type);
2067   cp_ref_qualifier rqual = type_memfn_rqual (type);
2068   for (v = TYPE_MAIN_VARIANT (type); v; v = TYPE_NEXT_VARIANT (v))
2069     if (cp_check_qualified_type (v, type, type_quals, rqual, raises))
2070       return v;
2071
2072   /* Need to build a new variant.  */
2073   v = build_variant_type_copy (type);
2074   TYPE_RAISES_EXCEPTIONS (v) = raises;
2075   return v;
2076 }
2077
2078 /* Given a TEMPLATE_TEMPLATE_PARM node T, create a new
2079    BOUND_TEMPLATE_TEMPLATE_PARM bound with NEWARGS as its template
2080    arguments.  */
2081
2082 tree
2083 bind_template_template_parm (tree t, tree newargs)
2084 {
2085   tree decl = TYPE_NAME (t);
2086   tree t2;
2087
2088   t2 = cxx_make_type (BOUND_TEMPLATE_TEMPLATE_PARM);
2089   decl = build_decl (input_location,
2090                      TYPE_DECL, DECL_NAME (decl), NULL_TREE);
2091
2092   /* These nodes have to be created to reflect new TYPE_DECL and template
2093      arguments.  */
2094   TEMPLATE_TYPE_PARM_INDEX (t2) = copy_node (TEMPLATE_TYPE_PARM_INDEX (t));
2095   TEMPLATE_PARM_DECL (TEMPLATE_TYPE_PARM_INDEX (t2)) = decl;
2096   TEMPLATE_TEMPLATE_PARM_TEMPLATE_INFO (t2)
2097     = build_template_info (TEMPLATE_TEMPLATE_PARM_TEMPLATE_DECL (t), newargs);
2098
2099   TREE_TYPE (decl) = t2;
2100   TYPE_NAME (t2) = decl;
2101   TYPE_STUB_DECL (t2) = decl;
2102   TYPE_SIZE (t2) = 0;
2103   SET_TYPE_STRUCTURAL_EQUALITY (t2);
2104
2105   return t2;
2106 }
2107
2108 /* Called from count_trees via walk_tree.  */
2109
2110 static tree
2111 count_trees_r (tree *tp, int *walk_subtrees, void *data)
2112 {
2113   ++*((int *) data);
2114
2115   if (TYPE_P (*tp))
2116     *walk_subtrees = 0;
2117
2118   return NULL_TREE;
2119 }
2120
2121 /* Debugging function for measuring the rough complexity of a tree
2122    representation.  */
2123
2124 int
2125 count_trees (tree t)
2126 {
2127   int n_trees = 0;
2128   cp_walk_tree_without_duplicates (&t, count_trees_r, &n_trees);
2129   return n_trees;
2130 }
2131
2132 /* Called from verify_stmt_tree via walk_tree.  */
2133
2134 static tree
2135 verify_stmt_tree_r (tree* tp, int * /*walk_subtrees*/, void* data)
2136 {
2137   tree t = *tp;
2138   hash_table<pointer_hash <tree_node> > *statements
2139       = static_cast <hash_table<pointer_hash <tree_node> > *> (data);
2140   tree_node **slot;
2141
2142   if (!STATEMENT_CODE_P (TREE_CODE (t)))
2143     return NULL_TREE;
2144
2145   /* If this statement is already present in the hash table, then
2146      there is a circularity in the statement tree.  */
2147   gcc_assert (!statements->find (t));
2148
2149   slot = statements->find_slot (t, INSERT);
2150   *slot = t;
2151
2152   return NULL_TREE;
2153 }
2154
2155 /* Debugging function to check that the statement T has not been
2156    corrupted.  For now, this function simply checks that T contains no
2157    circularities.  */
2158
2159 void
2160 verify_stmt_tree (tree t)
2161 {
2162   hash_table<pointer_hash <tree_node> > statements (37);
2163   cp_walk_tree (&t, verify_stmt_tree_r, &statements, NULL);
2164 }
2165
2166 /* Check if the type T depends on a type with no linkage and if so, return
2167    it.  If RELAXED_P then do not consider a class type declared within
2168    a vague-linkage function to have no linkage.  */
2169
2170 tree
2171 no_linkage_check (tree t, bool relaxed_p)
2172 {
2173   tree r;
2174
2175   /* There's no point in checking linkage on template functions; we
2176      can't know their complete types.  */
2177   if (processing_template_decl)
2178     return NULL_TREE;
2179
2180   switch (TREE_CODE (t))
2181     {
2182     case RECORD_TYPE:
2183       if (TYPE_PTRMEMFUNC_P (t))
2184         goto ptrmem;
2185       /* Lambda types that don't have mangling scope have no linkage.  We
2186          check CLASSTYPE_LAMBDA_EXPR for error_mark_node because
2187          when we get here from pushtag none of the lambda information is
2188          set up yet, so we want to assume that the lambda has linkage and
2189          fix it up later if not.  */
2190       if (CLASSTYPE_LAMBDA_EXPR (t)
2191           && CLASSTYPE_LAMBDA_EXPR (t) != error_mark_node
2192           && LAMBDA_TYPE_EXTRA_SCOPE (t) == NULL_TREE)
2193         return t;
2194       /* Fall through.  */
2195     case UNION_TYPE:
2196       if (!CLASS_TYPE_P (t))
2197         return NULL_TREE;
2198       /* Fall through.  */
2199     case ENUMERAL_TYPE:
2200       /* Only treat anonymous types as having no linkage if they're at
2201          namespace scope.  This is core issue 966.  */
2202       if (TYPE_ANONYMOUS_P (t) && TYPE_NAMESPACE_SCOPE_P (t))
2203         return t;
2204
2205       for (r = CP_TYPE_CONTEXT (t); ; )
2206         {
2207           /* If we're a nested type of a !TREE_PUBLIC class, we might not
2208              have linkage, or we might just be in an anonymous namespace.
2209              If we're in a TREE_PUBLIC class, we have linkage.  */
2210           if (TYPE_P (r) && !TREE_PUBLIC (TYPE_NAME (r)))
2211             return no_linkage_check (TYPE_CONTEXT (t), relaxed_p);
2212           else if (TREE_CODE (r) == FUNCTION_DECL)
2213             {
2214               if (!relaxed_p || !vague_linkage_p (r))
2215                 return t;
2216               else
2217                 r = CP_DECL_CONTEXT (r);
2218             }
2219           else
2220             break;
2221         }
2222
2223       return NULL_TREE;
2224
2225     case ARRAY_TYPE:
2226     case POINTER_TYPE:
2227     case REFERENCE_TYPE:
2228     case VECTOR_TYPE:
2229       return no_linkage_check (TREE_TYPE (t), relaxed_p);
2230
2231     case OFFSET_TYPE:
2232     ptrmem:
2233       r = no_linkage_check (TYPE_PTRMEM_POINTED_TO_TYPE (t),
2234                             relaxed_p);
2235       if (r)
2236         return r;
2237       return no_linkage_check (TYPE_PTRMEM_CLASS_TYPE (t), relaxed_p);
2238
2239     case METHOD_TYPE:
2240       r = no_linkage_check (TYPE_METHOD_BASETYPE (t), relaxed_p);
2241       if (r)
2242         return r;
2243       /* Fall through.  */
2244     case FUNCTION_TYPE:
2245       {
2246         tree parm;
2247         for (parm = TYPE_ARG_TYPES (t);
2248              parm && parm != void_list_node;
2249              parm = TREE_CHAIN (parm))
2250           {
2251             r = no_linkage_check (TREE_VALUE (parm), relaxed_p);
2252             if (r)
2253               return r;
2254           }
2255         return no_linkage_check (TREE_TYPE (t), relaxed_p);
2256       }
2257
2258     default:
2259       return NULL_TREE;
2260     }
2261 }
2262
2263 extern int depth_reached;
2264
2265 void
2266 cxx_print_statistics (void)
2267 {
2268   print_search_statistics ();
2269   print_class_statistics ();
2270   print_template_statistics ();
2271   if (GATHER_STATISTICS)
2272     fprintf (stderr, "maximum template instantiation depth reached: %d\n",
2273              depth_reached);
2274 }
2275
2276 /* Return, as an INTEGER_CST node, the number of elements for TYPE
2277    (which is an ARRAY_TYPE).  This counts only elements of the top
2278    array.  */
2279
2280 tree
2281 array_type_nelts_top (tree type)
2282 {
2283   return fold_build2_loc (input_location,
2284                       PLUS_EXPR, sizetype,
2285                       array_type_nelts (type),
2286                       size_one_node);
2287 }
2288
2289 /* Return, as an INTEGER_CST node, the number of elements for TYPE
2290    (which is an ARRAY_TYPE).  This one is a recursive count of all
2291    ARRAY_TYPEs that are clumped together.  */
2292
2293 tree
2294 array_type_nelts_total (tree type)
2295 {
2296   tree sz = array_type_nelts_top (type);
2297   type = TREE_TYPE (type);
2298   while (TREE_CODE (type) == ARRAY_TYPE)
2299     {
2300       tree n = array_type_nelts_top (type);
2301       sz = fold_build2_loc (input_location,
2302                         MULT_EXPR, sizetype, sz, n);
2303       type = TREE_TYPE (type);
2304     }
2305   return sz;
2306 }
2307
2308 /* Called from break_out_target_exprs via mapcar.  */
2309
2310 static tree
2311 bot_manip (tree* tp, int* walk_subtrees, void* data)
2312 {
2313   splay_tree target_remap = ((splay_tree) data);
2314   tree t = *tp;
2315
2316   if (!TYPE_P (t) && TREE_CONSTANT (t) && !TREE_SIDE_EFFECTS (t))
2317     {
2318       /* There can't be any TARGET_EXPRs or their slot variables below this
2319          point.  But we must make a copy, in case subsequent processing
2320          alters any part of it.  For example, during gimplification a cast
2321          of the form (T) &X::f (where "f" is a member function) will lead
2322          to replacing the PTRMEM_CST for &X::f with a VAR_DECL.  */
2323       *walk_subtrees = 0;
2324       *tp = unshare_expr (t);
2325       return NULL_TREE;
2326     }
2327   if (TREE_CODE (t) == TARGET_EXPR)
2328     {
2329       tree u;
2330
2331       if (TREE_CODE (TREE_OPERAND (t, 1)) == AGGR_INIT_EXPR)
2332         {
2333           u = build_cplus_new (TREE_TYPE (t), TREE_OPERAND (t, 1),
2334                                tf_warning_or_error);
2335           if (AGGR_INIT_ZERO_FIRST (TREE_OPERAND (t, 1)))
2336             AGGR_INIT_ZERO_FIRST (TREE_OPERAND (u, 1)) = true;
2337         }
2338       else
2339         u = build_target_expr_with_type (TREE_OPERAND (t, 1), TREE_TYPE (t),
2340                                          tf_warning_or_error);
2341
2342       TARGET_EXPR_IMPLICIT_P (u) = TARGET_EXPR_IMPLICIT_P (t);
2343       TARGET_EXPR_LIST_INIT_P (u) = TARGET_EXPR_LIST_INIT_P (t);
2344       TARGET_EXPR_DIRECT_INIT_P (u) = TARGET_EXPR_DIRECT_INIT_P (t);
2345
2346       /* Map the old variable to the new one.  */
2347       splay_tree_insert (target_remap,
2348                          (splay_tree_key) TREE_OPERAND (t, 0),
2349                          (splay_tree_value) TREE_OPERAND (u, 0));
2350
2351       TREE_OPERAND (u, 1) = break_out_target_exprs (TREE_OPERAND (u, 1));
2352
2353       /* Replace the old expression with the new version.  */
2354       *tp = u;
2355       /* We don't have to go below this point; the recursive call to
2356          break_out_target_exprs will have handled anything below this
2357          point.  */
2358       *walk_subtrees = 0;
2359       return NULL_TREE;
2360     }
2361
2362   /* Make a copy of this node.  */
2363   t = copy_tree_r (tp, walk_subtrees, NULL);
2364   if (TREE_CODE (*tp) == CALL_EXPR)
2365     {
2366       set_flags_from_callee (*tp);
2367
2368       /* builtin_LINE and builtin_FILE get the location where the default
2369          argument is expanded, not where the call was written.  */
2370       tree callee = get_callee_fndecl (*tp);
2371       if (callee && DECL_BUILT_IN (callee))
2372         switch (DECL_FUNCTION_CODE (callee))
2373           {
2374           case BUILT_IN_FILE:
2375           case BUILT_IN_LINE:
2376             SET_EXPR_LOCATION (*tp, input_location);
2377           default:
2378             break;
2379           }
2380     }
2381   return t;
2382 }
2383
2384 /* Replace all remapped VAR_DECLs in T with their new equivalents.
2385    DATA is really a splay-tree mapping old variables to new
2386    variables.  */
2387
2388 static tree
2389 bot_replace (tree* t, int* /*walk_subtrees*/, void* data)
2390 {
2391   splay_tree target_remap = ((splay_tree) data);
2392
2393   if (VAR_P (*t))
2394     {
2395       splay_tree_node n = splay_tree_lookup (target_remap,
2396                                              (splay_tree_key) *t);
2397       if (n)
2398         *t = (tree) n->value;
2399     }
2400   else if (TREE_CODE (*t) == PARM_DECL
2401            && DECL_NAME (*t) == this_identifier
2402            && !DECL_CONTEXT (*t))
2403     {
2404       /* In an NSDMI we need to replace the 'this' parameter we used for
2405          parsing with the real one for this function.  */
2406       *t = current_class_ptr;
2407     }
2408   else if (TREE_CODE (*t) == CONVERT_EXPR
2409            && CONVERT_EXPR_VBASE_PATH (*t))
2410     {
2411       /* In an NSDMI build_base_path defers building conversions to virtual
2412          bases, and we handle it here.  */
2413       tree basetype = TYPE_MAIN_VARIANT (TREE_TYPE (TREE_TYPE (*t)));
2414       vec<tree, va_gc> *vbases = CLASSTYPE_VBASECLASSES (current_class_type);
2415       int i; tree binfo;
2416       FOR_EACH_VEC_SAFE_ELT (vbases, i, binfo)
2417         if (BINFO_TYPE (binfo) == basetype)
2418           break;
2419       *t = build_base_path (PLUS_EXPR, TREE_OPERAND (*t, 0), binfo, true,
2420                             tf_warning_or_error);
2421     }
2422
2423   return NULL_TREE;
2424 }
2425
2426 /* When we parse a default argument expression, we may create
2427    temporary variables via TARGET_EXPRs.  When we actually use the
2428    default-argument expression, we make a copy of the expression
2429    and replace the temporaries with appropriate local versions.  */
2430
2431 tree
2432 break_out_target_exprs (tree t)
2433 {
2434   static int target_remap_count;
2435   static splay_tree target_remap;
2436
2437   if (!target_remap_count++)
2438     target_remap = splay_tree_new (splay_tree_compare_pointers,
2439                                    /*splay_tree_delete_key_fn=*/NULL,
2440                                    /*splay_tree_delete_value_fn=*/NULL);
2441   cp_walk_tree (&t, bot_manip, target_remap, NULL);
2442   cp_walk_tree (&t, bot_replace, target_remap, NULL);
2443
2444   if (!--target_remap_count)
2445     {
2446       splay_tree_delete (target_remap);
2447       target_remap = NULL;
2448     }
2449
2450   return t;
2451 }
2452
2453 /* Similar to `build_nt', but for template definitions of dependent
2454    expressions  */
2455
2456 tree
2457 build_min_nt_loc (location_t loc, enum tree_code code, ...)
2458 {
2459   tree t;
2460   int length;
2461   int i;
2462   va_list p;
2463
2464   gcc_assert (TREE_CODE_CLASS (code) != tcc_vl_exp);
2465
2466   va_start (p, code);
2467
2468   t = make_node (code);
2469   SET_EXPR_LOCATION (t, loc);
2470   length = TREE_CODE_LENGTH (code);
2471
2472   for (i = 0; i < length; i++)
2473     {
2474       tree x = va_arg (p, tree);
2475       TREE_OPERAND (t, i) = x;
2476     }
2477
2478   va_end (p);
2479   return t;
2480 }
2481
2482
2483 /* Similar to `build', but for template definitions.  */
2484
2485 tree
2486 build_min (enum tree_code code, tree tt, ...)
2487 {
2488   tree t;
2489   int length;
2490   int i;
2491   va_list p;
2492
2493   gcc_assert (TREE_CODE_CLASS (code) != tcc_vl_exp);
2494
2495   va_start (p, tt);
2496
2497   t = make_node (code);
2498   length = TREE_CODE_LENGTH (code);
2499   TREE_TYPE (t) = tt;
2500
2501   for (i = 0; i < length; i++)
2502     {
2503       tree x = va_arg (p, tree);
2504       TREE_OPERAND (t, i) = x;
2505       if (x && !TYPE_P (x) && TREE_SIDE_EFFECTS (x))
2506         TREE_SIDE_EFFECTS (t) = 1;
2507     }
2508
2509   va_end (p);
2510   return t;
2511 }
2512
2513 /* Similar to `build', but for template definitions of non-dependent
2514    expressions. NON_DEP is the non-dependent expression that has been
2515    built.  */
2516
2517 tree
2518 build_min_non_dep (enum tree_code code, tree non_dep, ...)
2519 {
2520   tree t;
2521   int length;
2522   int i;
2523   va_list p;
2524
2525   gcc_assert (TREE_CODE_CLASS (code) != tcc_vl_exp);
2526
2527   va_start (p, non_dep);
2528
2529   if (REFERENCE_REF_P (non_dep))
2530     non_dep = TREE_OPERAND (non_dep, 0);
2531
2532   t = make_node (code);
2533   length = TREE_CODE_LENGTH (code);
2534   TREE_TYPE (t) = TREE_TYPE (non_dep);
2535   TREE_SIDE_EFFECTS (t) = TREE_SIDE_EFFECTS (non_dep);
2536
2537   for (i = 0; i < length; i++)
2538     {
2539       tree x = va_arg (p, tree);
2540       TREE_OPERAND (t, i) = x;
2541     }
2542
2543   if (code == COMPOUND_EXPR && TREE_CODE (non_dep) != COMPOUND_EXPR)
2544     /* This should not be considered a COMPOUND_EXPR, because it
2545        resolves to an overload.  */
2546     COMPOUND_EXPR_OVERLOADED (t) = 1;
2547
2548   va_end (p);
2549   return convert_from_reference (t);
2550 }
2551
2552 /* Similar to `build_nt_call_vec', but for template definitions of
2553    non-dependent expressions. NON_DEP is the non-dependent expression
2554    that has been built.  */
2555
2556 tree
2557 build_min_non_dep_call_vec (tree non_dep, tree fn, vec<tree, va_gc> *argvec)
2558 {
2559   tree t = build_nt_call_vec (fn, argvec);
2560   if (REFERENCE_REF_P (non_dep))
2561     non_dep = TREE_OPERAND (non_dep, 0);
2562   TREE_TYPE (t) = TREE_TYPE (non_dep);
2563   TREE_SIDE_EFFECTS (t) = TREE_SIDE_EFFECTS (non_dep);
2564   return convert_from_reference (t);
2565 }
2566
2567 tree
2568 get_type_decl (tree t)
2569 {
2570   if (TREE_CODE (t) == TYPE_DECL)
2571     return t;
2572   if (TYPE_P (t))
2573     return TYPE_STUB_DECL (t);
2574   gcc_assert (t == error_mark_node);
2575   return t;
2576 }
2577
2578 /* Returns the namespace that contains DECL, whether directly or
2579    indirectly.  */
2580
2581 tree
2582 decl_namespace_context (tree decl)
2583 {
2584   while (1)
2585     {
2586       if (TREE_CODE (decl) == NAMESPACE_DECL)
2587         return decl;
2588       else if (TYPE_P (decl))
2589         decl = CP_DECL_CONTEXT (TYPE_MAIN_DECL (decl));
2590       else
2591         decl = CP_DECL_CONTEXT (decl);
2592     }
2593 }
2594
2595 /* Returns true if decl is within an anonymous namespace, however deeply
2596    nested, or false otherwise.  */
2597
2598 bool
2599 decl_anon_ns_mem_p (const_tree decl)
2600 {
2601   while (1)
2602     {
2603       if (decl == NULL_TREE || decl == error_mark_node)
2604         return false;
2605       if (TREE_CODE (decl) == NAMESPACE_DECL
2606           && DECL_NAME (decl) == NULL_TREE)
2607         return true;
2608       /* Classes and namespaces inside anonymous namespaces have
2609          TREE_PUBLIC == 0, so we can shortcut the search.  */
2610       else if (TYPE_P (decl))
2611         return (TREE_PUBLIC (TYPE_MAIN_DECL (decl)) == 0);
2612       else if (TREE_CODE (decl) == NAMESPACE_DECL)
2613         return (TREE_PUBLIC (decl) == 0);
2614       else
2615         decl = DECL_CONTEXT (decl);
2616     }
2617 }
2618
2619 /* Subroutine of cp_tree_equal: t1 and t2 are the CALL_EXPR_FNs of two
2620    CALL_EXPRS.  Return whether they are equivalent.  */
2621
2622 static bool
2623 called_fns_equal (tree t1, tree t2)
2624 {
2625   /* Core 1321: dependent names are equivalent even if the overload sets
2626      are different.  But do compare explicit template arguments.  */
2627   tree name1 = dependent_name (t1);
2628   tree name2 = dependent_name (t2);
2629   if (name1 || name2)
2630     {
2631       tree targs1 = NULL_TREE, targs2 = NULL_TREE;
2632
2633       if (name1 != name2)
2634         return false;
2635
2636       if (TREE_CODE (t1) == TEMPLATE_ID_EXPR)
2637         targs1 = TREE_OPERAND (t1, 1);
2638       if (TREE_CODE (t2) == TEMPLATE_ID_EXPR)
2639         targs2 = TREE_OPERAND (t2, 1);
2640       return cp_tree_equal (targs1, targs2);
2641     }
2642   else
2643     return cp_tree_equal (t1, t2);
2644 }
2645
2646 /* Return truthvalue of whether T1 is the same tree structure as T2.
2647    Return 1 if they are the same. Return 0 if they are different.  */
2648
2649 bool
2650 cp_tree_equal (tree t1, tree t2)
2651 {
2652   enum tree_code code1, code2;
2653
2654   if (t1 == t2)
2655     return true;
2656   if (!t1 || !t2)
2657     return false;
2658
2659   for (code1 = TREE_CODE (t1);
2660        CONVERT_EXPR_CODE_P (code1)
2661          || code1 == NON_LVALUE_EXPR;
2662        code1 = TREE_CODE (t1))
2663     t1 = TREE_OPERAND (t1, 0);
2664   for (code2 = TREE_CODE (t2);
2665        CONVERT_EXPR_CODE_P (code2)
2666          || code2 == NON_LVALUE_EXPR;
2667        code2 = TREE_CODE (t2))
2668     t2 = TREE_OPERAND (t2, 0);
2669
2670   /* They might have become equal now.  */
2671   if (t1 == t2)
2672     return true;
2673
2674   if (code1 != code2)
2675     return false;
2676
2677   switch (code1)
2678     {
2679     case VOID_CST:
2680       /* There's only a single VOID_CST node, so we should never reach
2681          here.  */
2682       gcc_unreachable ();
2683
2684     case INTEGER_CST:
2685       return tree_int_cst_equal (t1, t2);
2686
2687     case REAL_CST:
2688       return REAL_VALUES_EQUAL (TREE_REAL_CST (t1), TREE_REAL_CST (t2));
2689
2690     case STRING_CST:
2691       return TREE_STRING_LENGTH (t1) == TREE_STRING_LENGTH (t2)
2692         && !memcmp (TREE_STRING_POINTER (t1), TREE_STRING_POINTER (t2),
2693                     TREE_STRING_LENGTH (t1));
2694
2695     case FIXED_CST:
2696       return FIXED_VALUES_IDENTICAL (TREE_FIXED_CST (t1),
2697                                      TREE_FIXED_CST (t2));
2698
2699     case COMPLEX_CST:
2700       return cp_tree_equal (TREE_REALPART (t1), TREE_REALPART (t2))
2701         && cp_tree_equal (TREE_IMAGPART (t1), TREE_IMAGPART (t2));
2702
2703     case VECTOR_CST:
2704       return operand_equal_p (t1, t2, OEP_ONLY_CONST);
2705
2706     case CONSTRUCTOR:
2707       /* We need to do this when determining whether or not two
2708          non-type pointer to member function template arguments
2709          are the same.  */
2710       if (!same_type_p (TREE_TYPE (t1), TREE_TYPE (t2))
2711           || CONSTRUCTOR_NELTS (t1) != CONSTRUCTOR_NELTS (t2))
2712         return false;
2713       {
2714         tree field, value;
2715         unsigned int i;
2716         FOR_EACH_CONSTRUCTOR_ELT (CONSTRUCTOR_ELTS (t1), i, field, value)
2717           {
2718             constructor_elt *elt2 = CONSTRUCTOR_ELT (t2, i);
2719             if (!cp_tree_equal (field, elt2->index)
2720                 || !cp_tree_equal (value, elt2->value))
2721               return false;
2722           }
2723       }
2724       return true;
2725
2726     case TREE_LIST:
2727       if (!cp_tree_equal (TREE_PURPOSE (t1), TREE_PURPOSE (t2)))
2728         return false;
2729       if (!cp_tree_equal (TREE_VALUE (t1), TREE_VALUE (t2)))
2730         return false;
2731       return cp_tree_equal (TREE_CHAIN (t1), TREE_CHAIN (t2));
2732
2733     case SAVE_EXPR:
2734       return cp_tree_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
2735
2736     case CALL_EXPR:
2737       {
2738         tree arg1, arg2;
2739         call_expr_arg_iterator iter1, iter2;
2740         if (!called_fns_equal (CALL_EXPR_FN (t1), CALL_EXPR_FN (t2)))
2741           return false;
2742         for (arg1 = first_call_expr_arg (t1, &iter1),
2743                arg2 = first_call_expr_arg (t2, &iter2);
2744              arg1 && arg2;
2745              arg1 = next_call_expr_arg (&iter1),
2746                arg2 = next_call_expr_arg (&iter2))
2747           if (!cp_tree_equal (arg1, arg2))
2748             return false;
2749         if (arg1 || arg2)
2750           return false;
2751         return true;
2752       }
2753
2754     case TARGET_EXPR:
2755       {
2756         tree o1 = TREE_OPERAND (t1, 0);
2757         tree o2 = TREE_OPERAND (t2, 0);
2758
2759         /* Special case: if either target is an unallocated VAR_DECL,
2760            it means that it's going to be unified with whatever the
2761            TARGET_EXPR is really supposed to initialize, so treat it
2762            as being equivalent to anything.  */
2763         if (VAR_P (o1) && DECL_NAME (o1) == NULL_TREE
2764             && !DECL_RTL_SET_P (o1))
2765           /*Nop*/;
2766         else if (VAR_P (o2) && DECL_NAME (o2) == NULL_TREE
2767                  && !DECL_RTL_SET_P (o2))
2768           /*Nop*/;
2769         else if (!cp_tree_equal (o1, o2))
2770           return false;
2771
2772         return cp_tree_equal (TREE_OPERAND (t1, 1), TREE_OPERAND (t2, 1));
2773       }
2774
2775     case WITH_CLEANUP_EXPR:
2776       if (!cp_tree_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0)))
2777         return false;
2778       return cp_tree_equal (TREE_OPERAND (t1, 1), TREE_OPERAND (t1, 1));
2779
2780     case COMPONENT_REF:
2781       if (TREE_OPERAND (t1, 1) != TREE_OPERAND (t2, 1))
2782         return false;
2783       return cp_tree_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
2784
2785     case PARM_DECL:
2786       /* For comparing uses of parameters in late-specified return types
2787          with an out-of-class definition of the function, but can also come
2788          up for expressions that involve 'this' in a member function
2789          template.  */
2790
2791       if (comparing_specializations)
2792         /* When comparing hash table entries, only an exact match is
2793            good enough; we don't want to replace 'this' with the
2794            version from another function.  */
2795         return false;
2796
2797       if (same_type_p (TREE_TYPE (t1), TREE_TYPE (t2)))
2798         {
2799           if (DECL_ARTIFICIAL (t1) ^ DECL_ARTIFICIAL (t2))
2800             return false;
2801           if (DECL_ARTIFICIAL (t1)
2802               || (DECL_PARM_LEVEL (t1) == DECL_PARM_LEVEL (t2)
2803                   && DECL_PARM_INDEX (t1) == DECL_PARM_INDEX (t2)))
2804             return true;
2805         }
2806       return false;
2807
2808     case VAR_DECL:
2809     case CONST_DECL:
2810     case FIELD_DECL:
2811     case FUNCTION_DECL:
2812     case TEMPLATE_DECL:
2813     case IDENTIFIER_NODE:
2814     case SSA_NAME:
2815       return false;
2816
2817     case BASELINK:
2818       return (BASELINK_BINFO (t1) == BASELINK_BINFO (t2)
2819               && BASELINK_ACCESS_BINFO (t1) == BASELINK_ACCESS_BINFO (t2)
2820               && BASELINK_QUALIFIED_P (t1) == BASELINK_QUALIFIED_P (t2)
2821               && cp_tree_equal (BASELINK_FUNCTIONS (t1),
2822                                 BASELINK_FUNCTIONS (t2)));
2823
2824     case TEMPLATE_PARM_INDEX:
2825       return (TEMPLATE_PARM_IDX (t1) == TEMPLATE_PARM_IDX (t2)
2826               && TEMPLATE_PARM_LEVEL (t1) == TEMPLATE_PARM_LEVEL (t2)
2827               && (TEMPLATE_PARM_PARAMETER_PACK (t1)
2828                   == TEMPLATE_PARM_PARAMETER_PACK (t2))
2829               && same_type_p (TREE_TYPE (TEMPLATE_PARM_DECL (t1)),
2830                               TREE_TYPE (TEMPLATE_PARM_DECL (t2))));
2831
2832     case TEMPLATE_ID_EXPR:
2833       return (cp_tree_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0))
2834               && cp_tree_equal (TREE_OPERAND (t1, 1), TREE_OPERAND (t2, 1)));
2835
2836     case TREE_VEC:
2837       {
2838         unsigned ix;
2839         if (TREE_VEC_LENGTH (t1) != TREE_VEC_LENGTH (t2))
2840           return false;
2841         for (ix = TREE_VEC_LENGTH (t1); ix--;)
2842           if (!cp_tree_equal (TREE_VEC_ELT (t1, ix),
2843                               TREE_VEC_ELT (t2, ix)))
2844             return false;
2845         return true;
2846       }
2847
2848     case SIZEOF_EXPR:
2849     case ALIGNOF_EXPR:
2850       {
2851         tree o1 = TREE_OPERAND (t1, 0);
2852         tree o2 = TREE_OPERAND (t2, 0);
2853
2854         if (code1 == SIZEOF_EXPR)
2855           {
2856             if (SIZEOF_EXPR_TYPE_P (t1))
2857               o1 = TREE_TYPE (o1);
2858             if (SIZEOF_EXPR_TYPE_P (t2))
2859               o2 = TREE_TYPE (o2);
2860           }
2861         if (TREE_CODE (o1) != TREE_CODE (o2))
2862           return false;
2863         if (TYPE_P (o1))
2864           return same_type_p (o1, o2);
2865         else
2866           return cp_tree_equal (o1, o2);
2867       }
2868
2869     case MODOP_EXPR:
2870       {
2871         tree t1_op1, t2_op1;
2872
2873         if (!cp_tree_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0)))
2874           return false;
2875
2876         t1_op1 = TREE_OPERAND (t1, 1);
2877         t2_op1 = TREE_OPERAND (t2, 1);
2878         if (TREE_CODE (t1_op1) != TREE_CODE (t2_op1))
2879           return false;
2880
2881         return cp_tree_equal (TREE_OPERAND (t1, 2), TREE_OPERAND (t2, 2));
2882       }
2883
2884     case PTRMEM_CST:
2885       /* Two pointer-to-members are the same if they point to the same
2886          field or function in the same class.  */
2887       if (PTRMEM_CST_MEMBER (t1) != PTRMEM_CST_MEMBER (t2))
2888         return false;
2889
2890       return same_type_p (PTRMEM_CST_CLASS (t1), PTRMEM_CST_CLASS (t2));
2891
2892     case OVERLOAD:
2893       if (OVL_FUNCTION (t1) != OVL_FUNCTION (t2))
2894         return false;
2895       return cp_tree_equal (OVL_CHAIN (t1), OVL_CHAIN (t2));
2896
2897     case TRAIT_EXPR:
2898       if (TRAIT_EXPR_KIND (t1) != TRAIT_EXPR_KIND (t2))
2899         return false;
2900       return same_type_p (TRAIT_EXPR_TYPE1 (t1), TRAIT_EXPR_TYPE1 (t2))
2901         && cp_tree_equal (TRAIT_EXPR_TYPE2 (t1), TRAIT_EXPR_TYPE2 (t2));
2902
2903     case CAST_EXPR:
2904     case STATIC_CAST_EXPR:
2905     case REINTERPRET_CAST_EXPR:
2906     case CONST_CAST_EXPR:
2907     case DYNAMIC_CAST_EXPR:
2908     case IMPLICIT_CONV_EXPR:
2909     case NEW_EXPR:
2910       if (!same_type_p (TREE_TYPE (t1), TREE_TYPE (t2)))
2911         return false;
2912       /* Now compare operands as usual.  */
2913       break;
2914
2915     case DEFERRED_NOEXCEPT:
2916       return (cp_tree_equal (DEFERRED_NOEXCEPT_PATTERN (t1),
2917                              DEFERRED_NOEXCEPT_PATTERN (t2))
2918               && comp_template_args (DEFERRED_NOEXCEPT_ARGS (t1),
2919                                      DEFERRED_NOEXCEPT_ARGS (t2)));
2920       break;
2921
2922     default:
2923       break;
2924     }
2925
2926   switch (TREE_CODE_CLASS (code1))
2927     {
2928     case tcc_unary:
2929     case tcc_binary:
2930     case tcc_comparison:
2931     case tcc_expression:
2932     case tcc_vl_exp:
2933     case tcc_reference:
2934     case tcc_statement:
2935       {
2936         int i, n;
2937
2938         n = cp_tree_operand_length (t1);
2939         if (TREE_CODE_CLASS (code1) == tcc_vl_exp
2940             && n != TREE_OPERAND_LENGTH (t2))
2941           return false;
2942
2943         for (i = 0; i < n; ++i)
2944           if (!cp_tree_equal (TREE_OPERAND (t1, i), TREE_OPERAND (t2, i)))
2945             return false;
2946
2947         return true;
2948       }
2949
2950     case tcc_type:
2951       return same_type_p (t1, t2);
2952     default:
2953       gcc_unreachable ();
2954     }
2955   /* We can get here with --disable-checking.  */
2956   return false;
2957 }
2958
2959 /* The type of ARG when used as an lvalue.  */
2960
2961 tree
2962 lvalue_type (tree arg)
2963 {
2964   tree type = TREE_TYPE (arg);
2965   return type;
2966 }
2967
2968 /* The type of ARG for printing error messages; denote lvalues with
2969    reference types.  */
2970
2971 tree
2972 error_type (tree arg)
2973 {
2974   tree type = TREE_TYPE (arg);
2975
2976   if (TREE_CODE (type) == ARRAY_TYPE)
2977     ;
2978   else if (TREE_CODE (type) == ERROR_MARK)
2979     ;
2980   else if (real_lvalue_p (arg))
2981     type = build_reference_type (lvalue_type (arg));
2982   else if (MAYBE_CLASS_TYPE_P (type))
2983     type = lvalue_type (arg);
2984
2985   return type;
2986 }
2987
2988 /* Does FUNCTION use a variable-length argument list?  */
2989
2990 int
2991 varargs_function_p (const_tree function)
2992 {
2993   return stdarg_p (TREE_TYPE (function));
2994 }
2995
2996 /* Returns 1 if decl is a member of a class.  */
2997
2998 int
2999 member_p (const_tree decl)
3000 {
3001   const_tree const ctx = DECL_CONTEXT (decl);
3002   return (ctx && TYPE_P (ctx));
3003 }
3004
3005 /* Create a placeholder for member access where we don't actually have an
3006    object that the access is against.  */
3007
3008 tree
3009 build_dummy_object (tree type)
3010 {
3011   tree decl = build1 (CONVERT_EXPR, build_pointer_type (type), void_node);
3012   return cp_build_indirect_ref (decl, RO_NULL, tf_warning_or_error);
3013 }
3014
3015 /* We've gotten a reference to a member of TYPE.  Return *this if appropriate,
3016    or a dummy object otherwise.  If BINFOP is non-0, it is filled with the
3017    binfo path from current_class_type to TYPE, or 0.  */
3018
3019 tree
3020 maybe_dummy_object (tree type, tree* binfop)
3021 {
3022   tree decl, context;
3023   tree binfo;
3024   tree current = current_nonlambda_class_type ();
3025
3026   if (current
3027       && (binfo = lookup_base (current, type, ba_any, NULL,
3028                                tf_warning_or_error)))
3029     context = current;
3030   else
3031     {
3032       /* Reference from a nested class member function.  */
3033       context = type;
3034       binfo = TYPE_BINFO (type);
3035     }
3036
3037   if (binfop)
3038     *binfop = binfo;
3039
3040   if (current_class_ref
3041       /* current_class_ref might not correspond to current_class_type if
3042          we're in tsubst_default_argument or a lambda-declarator; in either
3043          case, we want to use current_class_ref if it matches CONTEXT.  */
3044       && (same_type_ignoring_top_level_qualifiers_p
3045           (TREE_TYPE (current_class_ref), context)))
3046     decl = current_class_ref;
3047   else
3048     decl = build_dummy_object (context);
3049
3050   return decl;
3051 }
3052
3053 /* Returns 1 if OB is a placeholder object, or a pointer to one.  */
3054
3055 int
3056 is_dummy_object (const_tree ob)
3057 {
3058   if (INDIRECT_REF_P (ob))
3059     ob = TREE_OPERAND (ob, 0);
3060   return (TREE_CODE (ob) == CONVERT_EXPR
3061           && TREE_OPERAND (ob, 0) == void_node);
3062 }
3063
3064 /* Returns 1 iff type T is something we want to treat as a scalar type for
3065    the purpose of deciding whether it is trivial/POD/standard-layout.  */
3066
3067 bool
3068 scalarish_type_p (const_tree t)
3069 {
3070   if (t == error_mark_node)
3071     return 1;
3072
3073   return (SCALAR_TYPE_P (t)
3074           || TREE_CODE (t) == VECTOR_TYPE);
3075 }
3076
3077 /* Returns true iff T requires non-trivial default initialization.  */
3078
3079 bool
3080 type_has_nontrivial_default_init (const_tree t)
3081 {
3082   t = strip_array_types (CONST_CAST_TREE (t));
3083
3084   if (CLASS_TYPE_P (t))
3085     return TYPE_HAS_COMPLEX_DFLT (t);
3086   else
3087     return 0;
3088 }
3089
3090 /* Returns true iff copying an object of type T (including via move
3091    constructor) is non-trivial.  That is, T has no non-trivial copy
3092    constructors and no non-trivial move constructors.  */
3093
3094 bool
3095 type_has_nontrivial_copy_init (const_tree t)
3096 {
3097   t = strip_array_types (CONST_CAST_TREE (t));
3098
3099   if (CLASS_TYPE_P (t))
3100     {
3101       gcc_assert (COMPLETE_TYPE_P (t));
3102       return ((TYPE_HAS_COPY_CTOR (t)
3103                && TYPE_HAS_COMPLEX_COPY_CTOR (t))
3104               || TYPE_HAS_COMPLEX_MOVE_CTOR (t));
3105     }
3106   else
3107     return 0;
3108 }
3109
3110 /* Returns 1 iff type T is a trivially copyable type, as defined in
3111    [basic.types] and [class].  */
3112
3113 bool
3114 trivially_copyable_p (const_tree t)
3115 {
3116   t = strip_array_types (CONST_CAST_TREE (t));
3117
3118   if (CLASS_TYPE_P (t))
3119     return ((!TYPE_HAS_COPY_CTOR (t)
3120              || !TYPE_HAS_COMPLEX_COPY_CTOR (t))
3121             && !TYPE_HAS_COMPLEX_MOVE_CTOR (t)
3122             && (!TYPE_HAS_COPY_ASSIGN (t)
3123                 || !TYPE_HAS_COMPLEX_COPY_ASSIGN (t))
3124             && !TYPE_HAS_COMPLEX_MOVE_ASSIGN (t)
3125             && TYPE_HAS_TRIVIAL_DESTRUCTOR (t));
3126   else
3127     return scalarish_type_p (t);
3128 }
3129
3130 /* Returns 1 iff type T is a trivial type, as defined in [basic.types] and
3131    [class].  */
3132
3133 bool
3134 trivial_type_p (const_tree t)
3135 {
3136   t = strip_array_types (CONST_CAST_TREE (t));
3137
3138   if (CLASS_TYPE_P (t))
3139     return (TYPE_HAS_TRIVIAL_DFLT (t)
3140             && trivially_copyable_p (t));
3141   else
3142     return scalarish_type_p (t);
3143 }
3144
3145 /* Returns 1 iff type T is a POD type, as defined in [basic.types].  */
3146
3147 bool
3148 pod_type_p (const_tree t)
3149 {
3150   /* This CONST_CAST is okay because strip_array_types returns its
3151      argument unmodified and we assign it to a const_tree.  */
3152   t = strip_array_types (CONST_CAST_TREE(t));
3153
3154   if (!CLASS_TYPE_P (t))
3155     return scalarish_type_p (t);
3156   else if (cxx_dialect > cxx98)
3157     /* [class]/10: A POD struct is a class that is both a trivial class and a
3158        standard-layout class, and has no non-static data members of type
3159        non-POD struct, non-POD union (or array of such types).
3160
3161        We don't need to check individual members because if a member is
3162        non-std-layout or non-trivial, the class will be too.  */
3163     return (std_layout_type_p (t) && trivial_type_p (t));
3164   else
3165     /* The C++98 definition of POD is different.  */
3166     return !CLASSTYPE_NON_LAYOUT_POD_P (t);
3167 }
3168
3169 /* Returns true iff T is POD for the purpose of layout, as defined in the
3170    C++ ABI.  */
3171
3172 bool
3173 layout_pod_type_p (const_tree t)
3174 {
3175   t = strip_array_types (CONST_CAST_TREE (t));
3176
3177   if (CLASS_TYPE_P (t))
3178     return !CLASSTYPE_NON_LAYOUT_POD_P (t);
3179   else
3180     return scalarish_type_p (t);
3181 }
3182
3183 /* Returns true iff T is a standard-layout type, as defined in
3184    [basic.types].  */
3185
3186 bool
3187 std_layout_type_p (const_tree t)
3188 {
3189   t = strip_array_types (CONST_CAST_TREE (t));
3190
3191   if (CLASS_TYPE_P (t))
3192     return !CLASSTYPE_NON_STD_LAYOUT (t);
3193   else
3194     return scalarish_type_p (t);
3195 }
3196
3197 /* Nonzero iff type T is a class template implicit specialization.  */
3198
3199 bool
3200 class_tmpl_impl_spec_p (const_tree t)
3201 {
3202   return CLASS_TYPE_P (t) && CLASSTYPE_TEMPLATE_INSTANTIATION (t);
3203 }
3204
3205 /* Returns 1 iff zero initialization of type T means actually storing
3206    zeros in it.  */
3207
3208 int
3209 zero_init_p (const_tree t)
3210 {
3211   /* This CONST_CAST is okay because strip_array_types returns its
3212      argument unmodified and we assign it to a const_tree.  */
3213   t = strip_array_types (CONST_CAST_TREE(t));
3214
3215   if (t == error_mark_node)
3216     return 1;
3217
3218   /* NULL pointers to data members are initialized with -1.  */
3219   if (TYPE_PTRDATAMEM_P (t))
3220     return 0;
3221
3222   /* Classes that contain types that can't be zero-initialized, cannot
3223      be zero-initialized themselves.  */
3224   if (CLASS_TYPE_P (t) && CLASSTYPE_NON_ZERO_INIT_P (t))
3225     return 0;
3226
3227   return 1;
3228 }
3229
3230 /* Table of valid C++ attributes.  */
3231 const struct attribute_spec cxx_attribute_table[] =
3232 {
3233   /* { name, min_len, max_len, decl_req, type_req, fn_type_req, handler,
3234        affects_type_identity } */
3235   { "java_interface", 0, 0, false, false, false,
3236     handle_java_interface_attribute, false },
3237   { "com_interface",  0, 0, false, false, false,
3238     handle_com_interface_attribute, false },
3239   { "init_priority",  1, 1, true,  false, false,
3240     handle_init_priority_attribute, false },
3241   { "abi_tag", 1, -1, false, false, false,
3242     handle_abi_tag_attribute, true },
3243   { NULL,             0, 0, false, false, false, NULL, false }
3244 };
3245
3246 /* Handle a "java_interface" attribute; arguments as in
3247    struct attribute_spec.handler.  */
3248 static tree
3249 handle_java_interface_attribute (tree* node,
3250                                  tree name,
3251                                  tree /*args*/,
3252                                  int flags,
3253                                  bool* no_add_attrs)
3254 {
3255   if (DECL_P (*node)
3256       || !CLASS_TYPE_P (*node)
3257       || !TYPE_FOR_JAVA (*node))
3258     {
3259       error ("%qE attribute can only be applied to Java class definitions",
3260              name);
3261       *no_add_attrs = true;
3262       return NULL_TREE;
3263     }
3264   if (!(flags & (int) ATTR_FLAG_TYPE_IN_PLACE))
3265     *node = build_variant_type_copy (*node);
3266   TYPE_JAVA_INTERFACE (*node) = 1;
3267
3268   return NULL_TREE;
3269 }
3270
3271 /* Handle a "com_interface" attribute; arguments as in
3272    struct attribute_spec.handler.  */
3273 static tree
3274 handle_com_interface_attribute (tree* node,
3275                                 tree name,
3276                                 tree /*args*/,
3277                                 int /*flags*/,
3278                                 bool* no_add_attrs)
3279 {
3280   static int warned;
3281
3282   *no_add_attrs = true;
3283
3284   if (DECL_P (*node)
3285       || !CLASS_TYPE_P (*node)
3286       || *node != TYPE_MAIN_VARIANT (*node))
3287     {
3288       warning (OPT_Wattributes, "%qE attribute can only be applied "
3289                "to class definitions", name);
3290       return NULL_TREE;
3291     }
3292
3293   if (!warned++)
3294     warning (0, "%qE is obsolete; g++ vtables are now COM-compatible by default",
3295              name);
3296
3297   return NULL_TREE;
3298 }
3299
3300 /* Handle an "init_priority" attribute; arguments as in
3301    struct attribute_spec.handler.  */
3302 static tree
3303 handle_init_priority_attribute (tree* node,
3304                                 tree name,
3305                                 tree args,
3306                                 int /*flags*/,
3307                                 bool* no_add_attrs)
3308 {
3309   tree initp_expr = TREE_VALUE (args);
3310   tree decl = *node;
3311   tree type = TREE_TYPE (decl);
3312   int pri;
3313
3314   STRIP_NOPS (initp_expr);
3315   initp_expr = default_conversion (initp_expr);
3316
3317   if (!initp_expr || TREE_CODE (initp_expr) != INTEGER_CST)
3318     {
3319       error ("requested init_priority is not an integer constant");
3320       *no_add_attrs = true;
3321       return NULL_TREE;
3322     }
3323
3324   pri = TREE_INT_CST_LOW (initp_expr);
3325
3326   type = strip_array_types (type);
3327
3328   if (decl == NULL_TREE
3329       || !VAR_P (decl)
3330       || !TREE_STATIC (decl)
3331       || DECL_EXTERNAL (decl)
3332       || (TREE_CODE (type) != RECORD_TYPE
3333           && TREE_CODE (type) != UNION_TYPE)
3334       /* Static objects in functions are initialized the
3335          first time control passes through that
3336          function. This is not precise enough to pin down an
3337          init_priority value, so don't allow it.  */
3338       || current_function_decl)
3339     {
3340       error ("can only use %qE attribute on file-scope definitions "
3341              "of objects of class type", name);
3342       *no_add_attrs = true;
3343       return NULL_TREE;
3344     }
3345
3346   if (pri > MAX_INIT_PRIORITY || pri <= 0)
3347     {
3348       error ("requested init_priority is out of range");
3349       *no_add_attrs = true;
3350       return NULL_TREE;
3351     }
3352
3353   /* Check for init_priorities that are reserved for
3354      language and runtime support implementations.*/
3355   if (pri <= MAX_RESERVED_INIT_PRIORITY)
3356     {
3357       warning
3358         (0, "requested init_priority is reserved for internal use");
3359     }
3360
3361   if (SUPPORTS_INIT_PRIORITY)
3362     {
3363       SET_DECL_INIT_PRIORITY (decl, pri);
3364       DECL_HAS_INIT_PRIORITY_P (decl) = 1;
3365       return NULL_TREE;
3366     }
3367   else
3368     {
3369       error ("%qE attribute is not supported on this platform", name);
3370       *no_add_attrs = true;
3371       return NULL_TREE;
3372     }
3373 }
3374
3375 /* DECL is being redeclared; the old declaration had the abi tags in OLD,
3376    and the new one has the tags in NEW_.  Give an error if there are tags
3377    in NEW_ that weren't in OLD.  */
3378
3379 bool
3380 check_abi_tag_redeclaration (const_tree decl, const_tree old, const_tree new_)
3381 {
3382   if (old && TREE_CODE (TREE_VALUE (old)) == TREE_LIST)
3383     old = TREE_VALUE (old);
3384   if (new_ && TREE_CODE (TREE_VALUE (new_)) == TREE_LIST)
3385     new_ = TREE_VALUE (new_);
3386   bool err = false;
3387   for (const_tree t = new_; t; t = TREE_CHAIN (t))
3388     {
3389       tree str = TREE_VALUE (t);
3390       for (const_tree in = old; in; in = TREE_CHAIN (in))
3391         {
3392           tree ostr = TREE_VALUE (in);
3393           if (cp_tree_equal (str, ostr))
3394             goto found;
3395         }
3396       error ("redeclaration of %qD adds abi tag %E", decl, str);
3397       err = true;
3398     found:;
3399     }
3400   if (err)
3401     {
3402       inform (DECL_SOURCE_LOCATION (decl), "previous declaration here");
3403       return false;
3404     }
3405   return true;
3406 }
3407
3408 /* Handle an "abi_tag" attribute; arguments as in
3409    struct attribute_spec.handler.  */
3410
3411 static tree
3412 handle_abi_tag_attribute (tree* node, tree name, tree args,
3413                           int flags, bool* no_add_attrs)
3414 {
3415   if (TYPE_P (*node))
3416     {
3417       if (!OVERLOAD_TYPE_P (*node))
3418         {
3419           error ("%qE attribute applied to non-class, non-enum type %qT",
3420                  name, *node);
3421           goto fail;
3422         }
3423       else if (!(flags & (int)ATTR_FLAG_TYPE_IN_PLACE))
3424         {
3425           error ("%qE attribute applied to %qT after its definition",
3426                  name, *node);
3427           goto fail;
3428         }
3429       else if (CLASSTYPE_TEMPLATE_INSTANTIATION (*node))
3430         {
3431           warning (OPT_Wattributes, "ignoring %qE attribute applied to "
3432                    "template instantiation %qT", name, *node);
3433           goto fail;
3434         }
3435       else if (CLASSTYPE_TEMPLATE_SPECIALIZATION (*node))
3436         {
3437           warning (OPT_Wattributes, "ignoring %qE attribute applied to "
3438                    "template specialization %qT", name, *node);
3439           goto fail;
3440         }
3441
3442       tree attributes = TYPE_ATTRIBUTES (*node);
3443       tree decl = TYPE_NAME (*node);
3444
3445       /* Make sure all declarations have the same abi tags.  */
3446       if (DECL_SOURCE_LOCATION (decl) != input_location)
3447         {
3448           if (!check_abi_tag_redeclaration (decl,
3449                                             lookup_attribute ("abi_tag",
3450                                                               attributes),
3451                                             args))
3452             goto fail;
3453         }
3454     }
3455   else
3456     {
3457       if (TREE_CODE (*node) != FUNCTION_DECL)
3458         {
3459           error ("%qE attribute applied to non-function %qD", name, *node);
3460           goto fail;
3461         }
3462       else if (DECL_LANGUAGE (*node) == lang_c)
3463         {
3464           error ("%qE attribute applied to extern \"C\" function %qD",
3465                  name, *node);
3466           goto fail;
3467         }
3468     }
3469
3470   return NULL_TREE;
3471
3472  fail:
3473   *no_add_attrs = true;
3474   return NULL_TREE;
3475 }
3476
3477 /* Return a new PTRMEM_CST of the indicated TYPE.  The MEMBER is the
3478    thing pointed to by the constant.  */
3479
3480 tree
3481 make_ptrmem_cst (tree type, tree member)
3482 {
3483   tree ptrmem_cst = make_node (PTRMEM_CST);
3484   TREE_TYPE (ptrmem_cst) = type;
3485   PTRMEM_CST_MEMBER (ptrmem_cst) = member;
3486   return ptrmem_cst;
3487 }
3488
3489 /* Build a variant of TYPE that has the indicated ATTRIBUTES.  May
3490    return an existing type if an appropriate type already exists.  */
3491
3492 tree
3493 cp_build_type_attribute_variant (tree type, tree attributes)
3494 {
3495   tree new_type;
3496
3497   new_type = build_type_attribute_variant (type, attributes);
3498   if (TREE_CODE (new_type) == FUNCTION_TYPE
3499       || TREE_CODE (new_type) == METHOD_TYPE)
3500     {
3501       new_type = build_exception_variant (new_type,
3502                                           TYPE_RAISES_EXCEPTIONS (type));
3503       new_type = build_ref_qualified_type (new_type,
3504                                            type_memfn_rqual (type));
3505     }
3506
3507   /* Making a new main variant of a class type is broken.  */
3508   gcc_assert (!CLASS_TYPE_P (type) || new_type == type);
3509
3510   return new_type;
3511 }
3512
3513 /* Return TRUE if TYPE1 and TYPE2 are identical for type hashing purposes.
3514    Called only after doing all language independent checks.  Only
3515    to check TYPE_RAISES_EXCEPTIONS for FUNCTION_TYPE, the rest is already
3516    compared in type_hash_eq.  */
3517
3518 bool
3519 cxx_type_hash_eq (const_tree typea, const_tree typeb)
3520 {
3521   gcc_assert (TREE_CODE (typea) == FUNCTION_TYPE
3522               || TREE_CODE (typea) == METHOD_TYPE);
3523
3524   return comp_except_specs (TYPE_RAISES_EXCEPTIONS (typea),
3525                             TYPE_RAISES_EXCEPTIONS (typeb), ce_exact);
3526 }
3527
3528 /* Apply FUNC to all language-specific sub-trees of TP in a pre-order
3529    traversal.  Called from walk_tree.  */
3530
3531 tree
3532 cp_walk_subtrees (tree *tp, int *walk_subtrees_p, walk_tree_fn func,
3533                   void *data, hash_set<tree> *pset)
3534 {
3535   enum tree_code code = TREE_CODE (*tp);
3536   tree result;
3537
3538 #define WALK_SUBTREE(NODE)                              \
3539   do                                                    \
3540     {                                                   \
3541       result = cp_walk_tree (&(NODE), func, data, pset);        \
3542       if (result) goto out;                             \
3543     }                                                   \
3544   while (0)
3545
3546   /* Not one of the easy cases.  We must explicitly go through the
3547      children.  */
3548   result = NULL_TREE;
3549   switch (code)
3550     {
3551     case DEFAULT_ARG:
3552     case TEMPLATE_TEMPLATE_PARM:
3553     case BOUND_TEMPLATE_TEMPLATE_PARM:
3554     case UNBOUND_CLASS_TEMPLATE:
3555     case TEMPLATE_PARM_INDEX:
3556     case TEMPLATE_TYPE_PARM:
3557     case TYPENAME_TYPE:
3558     case TYPEOF_TYPE:
3559     case UNDERLYING_TYPE:
3560       /* None of these have subtrees other than those already walked
3561          above.  */
3562       *walk_subtrees_p = 0;
3563       break;
3564
3565     case BASELINK:
3566       WALK_SUBTREE (BASELINK_FUNCTIONS (*tp));
3567       *walk_subtrees_p = 0;
3568       break;
3569
3570     case PTRMEM_CST:
3571       WALK_SUBTREE (TREE_TYPE (*tp));
3572       *walk_subtrees_p = 0;
3573       break;
3574
3575     case TREE_LIST:
3576       WALK_SUBTREE (TREE_PURPOSE (*tp));
3577       break;
3578
3579     case OVERLOAD:
3580       WALK_SUBTREE (OVL_FUNCTION (*tp));
3581       WALK_SUBTREE (OVL_CHAIN (*tp));
3582       *walk_subtrees_p = 0;
3583       break;
3584
3585     case USING_DECL:
3586       WALK_SUBTREE (DECL_NAME (*tp));
3587       WALK_SUBTREE (USING_DECL_SCOPE (*tp));
3588       WALK_SUBTREE (USING_DECL_DECLS (*tp));
3589       *walk_subtrees_p = 0;
3590       break;
3591
3592     case RECORD_TYPE:
3593       if (TYPE_PTRMEMFUNC_P (*tp))
3594         WALK_SUBTREE (TYPE_PTRMEMFUNC_FN_TYPE (*tp));
3595       break;
3596
3597     case TYPE_ARGUMENT_PACK:
3598     case NONTYPE_ARGUMENT_PACK:
3599       {
3600         tree args = ARGUMENT_PACK_ARGS (*tp);
3601         int i, len = TREE_VEC_LENGTH (args);
3602         for (i = 0; i < len; i++)
3603           WALK_SUBTREE (TREE_VEC_ELT (args, i));
3604       }
3605       break;
3606
3607     case TYPE_PACK_EXPANSION:
3608       WALK_SUBTREE (TREE_TYPE (*tp));
3609       WALK_SUBTREE (PACK_EXPANSION_EXTRA_ARGS (*tp));
3610       *walk_subtrees_p = 0;
3611       break;
3612
3613     case EXPR_PACK_EXPANSION:
3614       WALK_SUBTREE (TREE_OPERAND (*tp, 0));
3615       WALK_SUBTREE (PACK_EXPANSION_EXTRA_ARGS (*tp));
3616       *walk_subtrees_p = 0;
3617       break;
3618
3619     case CAST_EXPR:
3620     case REINTERPRET_CAST_EXPR:
3621     case STATIC_CAST_EXPR:
3622     case CONST_CAST_EXPR:
3623     case DYNAMIC_CAST_EXPR:
3624     case IMPLICIT_CONV_EXPR:
3625       if (TREE_TYPE (*tp))
3626         WALK_SUBTREE (TREE_TYPE (*tp));
3627
3628       {
3629         int i;
3630         for (i = 0; i < TREE_CODE_LENGTH (TREE_CODE (*tp)); ++i)
3631           WALK_SUBTREE (TREE_OPERAND (*tp, i));
3632       }
3633       *walk_subtrees_p = 0;
3634       break;
3635
3636     case TRAIT_EXPR:
3637       WALK_SUBTREE (TRAIT_EXPR_TYPE1 (*tp));
3638       WALK_SUBTREE (TRAIT_EXPR_TYPE2 (*tp));
3639       *walk_subtrees_p = 0;
3640       break;
3641
3642     case DECLTYPE_TYPE:
3643       WALK_SUBTREE (DECLTYPE_TYPE_EXPR (*tp));
3644       *walk_subtrees_p = 0;
3645       break;
3646
3647
3648     default:
3649       return NULL_TREE;
3650     }
3651
3652   /* We didn't find what we were looking for.  */
3653  out:
3654   return result;
3655
3656 #undef WALK_SUBTREE
3657 }
3658
3659 /* Like save_expr, but for C++.  */
3660
3661 tree
3662 cp_save_expr (tree expr)
3663 {
3664   /* There is no reason to create a SAVE_EXPR within a template; if
3665      needed, we can create the SAVE_EXPR when instantiating the
3666      template.  Furthermore, the middle-end cannot handle C++-specific
3667      tree codes.  */
3668   if (processing_template_decl)
3669     return expr;
3670   return save_expr (expr);
3671 }
3672
3673 /* Initialize tree.c.  */
3674
3675 void
3676 init_tree (void)
3677 {
3678   list_hash_table = hash_table<list_hasher>::create_ggc (61);
3679 }
3680
3681 /* Returns the kind of special function that DECL (a FUNCTION_DECL)
3682    is.  Note that sfk_none is zero, so this function can be used as a
3683    predicate to test whether or not DECL is a special function.  */
3684
3685 special_function_kind
3686 special_function_p (const_tree decl)
3687 {
3688   /* Rather than doing all this stuff with magic names, we should
3689      probably have a field of type `special_function_kind' in
3690      DECL_LANG_SPECIFIC.  */
3691   if (DECL_INHERITED_CTOR_BASE (decl))
3692     return sfk_inheriting_constructor;
3693   if (DECL_COPY_CONSTRUCTOR_P (decl))
3694     return sfk_copy_constructor;
3695   if (DECL_MOVE_CONSTRUCTOR_P (decl))
3696     return sfk_move_constructor;
3697   if (DECL_CONSTRUCTOR_P (decl))
3698     return sfk_constructor;
3699   if (DECL_OVERLOADED_OPERATOR_P (decl) == NOP_EXPR)
3700     {
3701       if (copy_fn_p (decl))
3702         return sfk_copy_assignment;
3703       if (move_fn_p (decl))
3704         return sfk_move_assignment;
3705     }
3706   if (DECL_MAYBE_IN_CHARGE_DESTRUCTOR_P (decl))
3707     return sfk_destructor;
3708   if (DECL_COMPLETE_DESTRUCTOR_P (decl))
3709     return sfk_complete_destructor;
3710   if (DECL_BASE_DESTRUCTOR_P (decl))
3711     return sfk_base_destructor;
3712   if (DECL_DELETING_DESTRUCTOR_P (decl))
3713     return sfk_deleting_destructor;
3714   if (DECL_CONV_FN_P (decl))
3715     return sfk_conversion;
3716
3717   return sfk_none;
3718 }
3719
3720 /* Returns nonzero if TYPE is a character type, including wchar_t.  */
3721
3722 int
3723 char_type_p (tree type)
3724 {
3725   return (same_type_p (type, char_type_node)
3726           || same_type_p (type, unsigned_char_type_node)
3727           || same_type_p (type, signed_char_type_node)
3728           || same_type_p (type, char16_type_node)
3729           || same_type_p (type, char32_type_node)
3730           || same_type_p (type, wchar_type_node));
3731 }
3732
3733 /* Returns the kind of linkage associated with the indicated DECL.  Th
3734    value returned is as specified by the language standard; it is
3735    independent of implementation details regarding template
3736    instantiation, etc.  For example, it is possible that a declaration
3737    to which this function assigns external linkage would not show up
3738    as a global symbol when you run `nm' on the resulting object file.  */
3739
3740 linkage_kind
3741 decl_linkage (tree decl)
3742 {
3743   /* This function doesn't attempt to calculate the linkage from first
3744      principles as given in [basic.link].  Instead, it makes use of
3745      the fact that we have already set TREE_PUBLIC appropriately, and
3746      then handles a few special cases.  Ideally, we would calculate
3747      linkage first, and then transform that into a concrete
3748      implementation.  */
3749
3750   /* Things that don't have names have no linkage.  */
3751   if (!DECL_NAME (decl))
3752     return lk_none;
3753
3754   /* Fields have no linkage.  */
3755   if (TREE_CODE (decl) == FIELD_DECL)
3756     return lk_none;
3757
3758   /* Things that are TREE_PUBLIC have external linkage.  */
3759   if (TREE_PUBLIC (decl))
3760     return lk_external;
3761
3762   if (TREE_CODE (decl) == NAMESPACE_DECL)
3763     return lk_external;
3764
3765   /* Linkage of a CONST_DECL depends on the linkage of the enumeration
3766      type.  */
3767   if (TREE_CODE (decl) == CONST_DECL)
3768     return decl_linkage (TYPE_NAME (DECL_CONTEXT (decl)));
3769
3770   /* Things in local scope do not have linkage, if they don't have
3771      TREE_PUBLIC set.  */
3772   if (decl_function_context (decl))
3773     return lk_none;
3774
3775   /* Members of the anonymous namespace also have TREE_PUBLIC unset, but
3776      are considered to have external linkage for language purposes, as do
3777      template instantiations on targets without weak symbols.  DECLs really
3778      meant to have internal linkage have DECL_THIS_STATIC set.  */
3779   if (TREE_CODE (decl) == TYPE_DECL)
3780     return lk_external;
3781   if (VAR_OR_FUNCTION_DECL_P (decl))
3782     {
3783       if (!DECL_THIS_STATIC (decl))
3784         return lk_external;
3785
3786       /* Static data members and static member functions from classes
3787          in anonymous namespace also don't have TREE_PUBLIC set.  */
3788       if (DECL_CLASS_CONTEXT (decl))
3789         return lk_external;
3790     }
3791
3792   /* Everything else has internal linkage.  */
3793   return lk_internal;
3794 }
3795
3796 /* Returns the storage duration of the object or reference associated with
3797    the indicated DECL, which should be a VAR_DECL or PARM_DECL.  */
3798
3799 duration_kind
3800 decl_storage_duration (tree decl)
3801 {
3802   if (TREE_CODE (decl) == PARM_DECL)
3803     return dk_auto;
3804   if (TREE_CODE (decl) == FUNCTION_DECL)
3805     return dk_static;
3806   gcc_assert (VAR_P (decl));
3807   if (!TREE_STATIC (decl)
3808       && !DECL_EXTERNAL (decl))
3809     return dk_auto;
3810   if (DECL_THREAD_LOCAL_P (decl))
3811     return dk_thread;
3812   return dk_static;
3813 }
3814 \f
3815 /* EXP is an expression that we want to pre-evaluate.  Returns (in
3816    *INITP) an expression that will perform the pre-evaluation.  The
3817    value returned by this function is a side-effect free expression
3818    equivalent to the pre-evaluated expression.  Callers must ensure
3819    that *INITP is evaluated before EXP.  */
3820
3821 tree
3822 stabilize_expr (tree exp, tree* initp)
3823 {
3824   tree init_expr;
3825
3826   if (!TREE_SIDE_EFFECTS (exp))
3827     init_expr = NULL_TREE;
3828   else if (VOID_TYPE_P (TREE_TYPE (exp)))
3829     {
3830       init_expr = exp;
3831       exp = void_node;
3832     }
3833   /* There are no expressions with REFERENCE_TYPE, but there can be call
3834      arguments with such a type; just treat it as a pointer.  */
3835   else if (TREE_CODE (TREE_TYPE (exp)) == REFERENCE_TYPE
3836            || SCALAR_TYPE_P (TREE_TYPE (exp))
3837            || !lvalue_or_rvalue_with_address_p (exp))
3838     {
3839       init_expr = get_target_expr (exp);
3840       exp = TARGET_EXPR_SLOT (init_expr);
3841       if (CLASS_TYPE_P (TREE_TYPE (exp)))
3842         exp = move (exp);
3843       else
3844         exp = rvalue (exp);
3845     }
3846   else
3847     {
3848       bool xval = !real_lvalue_p (exp);
3849       exp = cp_build_addr_expr (exp, tf_warning_or_error);
3850       init_expr = get_target_expr (exp);
3851       exp = TARGET_EXPR_SLOT (init_expr);
3852       exp = cp_build_indirect_ref (exp, RO_NULL, tf_warning_or_error);
3853       if (xval)
3854         exp = move (exp);
3855     }
3856   *initp = init_expr;
3857
3858   gcc_assert (!TREE_SIDE_EFFECTS (exp));
3859   return exp;
3860 }
3861
3862 /* Add NEW_EXPR, an expression whose value we don't care about, after the
3863    similar expression ORIG.  */
3864
3865 tree
3866 add_stmt_to_compound (tree orig, tree new_expr)
3867 {
3868   if (!new_expr || !TREE_SIDE_EFFECTS (new_expr))
3869     return orig;
3870   if (!orig || !TREE_SIDE_EFFECTS (orig))
3871     return new_expr;
3872   return build2 (COMPOUND_EXPR, void_type_node, orig, new_expr);
3873 }
3874
3875 /* Like stabilize_expr, but for a call whose arguments we want to
3876    pre-evaluate.  CALL is modified in place to use the pre-evaluated
3877    arguments, while, upon return, *INITP contains an expression to
3878    compute the arguments.  */
3879
3880 void
3881 stabilize_call (tree call, tree *initp)
3882 {
3883   tree inits = NULL_TREE;
3884   int i;
3885   int nargs = call_expr_nargs (call);
3886
3887   if (call == error_mark_node || processing_template_decl)
3888     {
3889       *initp = NULL_TREE;
3890       return;
3891     }
3892
3893   gcc_assert (TREE_CODE (call) == CALL_EXPR);
3894
3895   for (i = 0; i < nargs; i++)
3896     {
3897       tree init;
3898       CALL_EXPR_ARG (call, i) =
3899         stabilize_expr (CALL_EXPR_ARG (call, i), &init);
3900       inits = add_stmt_to_compound (inits, init);
3901     }
3902
3903   *initp = inits;
3904 }
3905
3906 /* Like stabilize_expr, but for an AGGR_INIT_EXPR whose arguments we want
3907    to pre-evaluate.  CALL is modified in place to use the pre-evaluated
3908    arguments, while, upon return, *INITP contains an expression to
3909    compute the arguments.  */
3910
3911 static void
3912 stabilize_aggr_init (tree call, tree *initp)
3913 {
3914   tree inits = NULL_TREE;
3915   int i;
3916   int nargs = aggr_init_expr_nargs (call);
3917
3918   if (call == error_mark_node)
3919     return;
3920
3921   gcc_assert (TREE_CODE (call) == AGGR_INIT_EXPR);
3922
3923   for (i = 0; i < nargs; i++)
3924     {
3925       tree init;
3926       AGGR_INIT_EXPR_ARG (call, i) =
3927         stabilize_expr (AGGR_INIT_EXPR_ARG (call, i), &init);
3928       inits = add_stmt_to_compound (inits, init);
3929     }
3930
3931   *initp = inits;
3932 }
3933
3934 /* Like stabilize_expr, but for an initialization.
3935
3936    If the initialization is for an object of class type, this function
3937    takes care not to introduce additional temporaries.
3938
3939    Returns TRUE iff the expression was successfully pre-evaluated,
3940    i.e., if INIT is now side-effect free, except for, possibly, a
3941    single call to a constructor.  */
3942
3943 bool
3944 stabilize_init (tree init, tree *initp)
3945 {
3946   tree t = init;
3947
3948   *initp = NULL_TREE;
3949
3950   if (t == error_mark_node || processing_template_decl)
3951     return true;
3952
3953   if (TREE_CODE (t) == INIT_EXPR)
3954     t = TREE_OPERAND (t, 1);
3955   if (TREE_CODE (t) == TARGET_EXPR)
3956     t = TARGET_EXPR_INITIAL (t);
3957
3958   /* If the RHS can be stabilized without breaking copy elision, stabilize
3959      it.  We specifically don't stabilize class prvalues here because that
3960      would mean an extra copy, but they might be stabilized below.  */
3961   if (TREE_CODE (init) == INIT_EXPR
3962       && TREE_CODE (t) != CONSTRUCTOR
3963       && TREE_CODE (t) != AGGR_INIT_EXPR
3964       && (SCALAR_TYPE_P (TREE_TYPE (t))
3965           || lvalue_or_rvalue_with_address_p (t)))
3966     {
3967       TREE_OPERAND (init, 1) = stabilize_expr (t, initp);
3968       return true;
3969     }
3970
3971   if (TREE_CODE (t) == COMPOUND_EXPR
3972       && TREE_CODE (init) == INIT_EXPR)
3973     {
3974       tree last = expr_last (t);
3975       /* Handle stabilizing the EMPTY_CLASS_EXPR pattern.  */
3976       if (!TREE_SIDE_EFFECTS (last))
3977         {
3978           *initp = t;
3979           TREE_OPERAND (init, 1) = last;
3980           return true;
3981         }
3982     }
3983
3984   if (TREE_CODE (t) == CONSTRUCTOR)
3985     {
3986       /* Aggregate initialization: stabilize each of the field
3987          initializers.  */
3988       unsigned i;
3989       constructor_elt *ce;
3990       bool good = true;
3991       vec<constructor_elt, va_gc> *v = CONSTRUCTOR_ELTS (t);
3992       for (i = 0; vec_safe_iterate (v, i, &ce); ++i)
3993         {
3994           tree type = TREE_TYPE (ce->value);
3995           tree subinit;
3996           if (TREE_CODE (type) == REFERENCE_TYPE
3997               || SCALAR_TYPE_P (type))
3998             ce->value = stabilize_expr (ce->value, &subinit);
3999           else if (!stabilize_init (ce->value, &subinit))
4000             good = false;
4001           *initp = add_stmt_to_compound (*initp, subinit);
4002         }
4003       return good;
4004     }
4005
4006   if (TREE_CODE (t) == CALL_EXPR)
4007     {
4008       stabilize_call (t, initp);
4009       return true;
4010     }
4011
4012   if (TREE_CODE (t) == AGGR_INIT_EXPR)
4013     {
4014       stabilize_aggr_init (t, initp);
4015       return true;
4016     }
4017
4018   /* The initialization is being performed via a bitwise copy -- and
4019      the item copied may have side effects.  */
4020   return !TREE_SIDE_EFFECTS (init);
4021 }
4022
4023 /* Like "fold", but should be used whenever we might be processing the
4024    body of a template.  */
4025
4026 tree
4027 fold_if_not_in_template (tree expr)
4028 {
4029   /* In the body of a template, there is never any need to call
4030      "fold".  We will call fold later when actually instantiating the
4031      template.  Integral constant expressions in templates will be
4032      evaluated via fold_non_dependent_expr, as necessary.  */
4033   if (processing_template_decl)
4034     return expr;
4035
4036   /* Fold C++ front-end specific tree codes.  */
4037   if (TREE_CODE (expr) == UNARY_PLUS_EXPR)
4038     return fold_convert (TREE_TYPE (expr), TREE_OPERAND (expr, 0));
4039
4040   return fold (expr);
4041 }
4042
4043 /* Returns true if a cast to TYPE may appear in an integral constant
4044    expression.  */
4045
4046 bool
4047 cast_valid_in_integral_constant_expression_p (tree type)
4048 {
4049   return (INTEGRAL_OR_ENUMERATION_TYPE_P (type)
4050           || cxx_dialect >= cxx11
4051           || dependent_type_p (type)
4052           || type == error_mark_node);
4053 }
4054
4055 /* Return true if we need to fix linkage information of DECL.  */
4056
4057 static bool
4058 cp_fix_function_decl_p (tree decl)
4059 {
4060   /* Skip if DECL is not externally visible.  */
4061   if (!TREE_PUBLIC (decl))
4062     return false;
4063
4064   /* We need to fix DECL if it a appears to be exported but with no
4065      function body.  Thunks do not have CFGs and we may need to
4066      handle them specially later.   */
4067   if (!gimple_has_body_p (decl)
4068       && !DECL_THUNK_P (decl)
4069       && !DECL_EXTERNAL (decl))
4070     {
4071       struct cgraph_node *node = cgraph_node::get (decl);
4072
4073       /* Don't fix same_body aliases.  Although they don't have their own
4074          CFG, they share it with what they alias to.  */
4075       if (!node || !node->alias
4076           || !vec_safe_length (node->ref_list.references))
4077         return true;
4078     }
4079
4080   return false;
4081 }
4082
4083 /* Clean the C++ specific parts of the tree T. */
4084
4085 void
4086 cp_free_lang_data (tree t)
4087 {
4088   if (TREE_CODE (t) == METHOD_TYPE
4089       || TREE_CODE (t) == FUNCTION_TYPE)
4090     {
4091       /* Default args are not interesting anymore.  */
4092       tree argtypes = TYPE_ARG_TYPES (t);
4093       while (argtypes)
4094         {
4095           TREE_PURPOSE (argtypes) = 0;
4096           argtypes = TREE_CHAIN (argtypes);
4097         }
4098     }
4099   else if (TREE_CODE (t) == FUNCTION_DECL
4100            && cp_fix_function_decl_p (t))
4101     {
4102       /* If T is used in this translation unit at all,  the definition
4103          must exist somewhere else since we have decided to not emit it
4104          in this TU.  So make it an external reference.  */
4105       DECL_EXTERNAL (t) = 1;
4106       TREE_STATIC (t) = 0;
4107     }
4108   if (TREE_CODE (t) == NAMESPACE_DECL)
4109     {
4110       /* The list of users of a namespace isn't useful for the middle-end
4111          or debug generators.  */
4112       DECL_NAMESPACE_USERS (t) = NULL_TREE;
4113       /* Neither do we need the leftover chaining of namespaces
4114          from the binding level.  */
4115       DECL_CHAIN (t) = NULL_TREE;
4116     }
4117 }
4118
4119 /* Stub for c-common.  Please keep in sync with c-decl.c.
4120    FIXME: If address space support is target specific, then this
4121    should be a C target hook.  But currently this is not possible,
4122    because this function is called via REGISTER_TARGET_PRAGMAS.  */
4123 void
4124 c_register_addr_space (const char * /*word*/, addr_space_t /*as*/)
4125 {
4126 }
4127
4128 /* Return the number of operands in T that we care about for things like
4129    mangling.  */
4130
4131 int
4132 cp_tree_operand_length (const_tree t)
4133 {
4134   enum tree_code code = TREE_CODE (t);
4135
4136   switch (code)
4137     {
4138     case PREINCREMENT_EXPR:
4139     case PREDECREMENT_EXPR:
4140     case POSTINCREMENT_EXPR:
4141     case POSTDECREMENT_EXPR:
4142       return 1;
4143
4144     case ARRAY_REF:
4145       return 2;
4146
4147     case EXPR_PACK_EXPANSION:
4148       return 1;
4149
4150     default:
4151       return TREE_OPERAND_LENGTH (t);
4152     }
4153 }
4154
4155 /* Implement -Wzero_as_null_pointer_constant.  Return true if the
4156    conditions for the warning hold, false otherwise.  */
4157 bool
4158 maybe_warn_zero_as_null_pointer_constant (tree expr, location_t loc)
4159 {
4160   if (c_inhibit_evaluation_warnings == 0
4161       && !NULLPTR_TYPE_P (TREE_TYPE (expr)))
4162     {
4163       warning_at (loc, OPT_Wzero_as_null_pointer_constant,
4164                   "zero as null pointer constant");
4165       return true;
4166     }
4167   return false;
4168 }
4169 \f
4170 #if defined ENABLE_TREE_CHECKING && (GCC_VERSION >= 2007)
4171 /* Complain that some language-specific thing hanging off a tree
4172    node has been accessed improperly.  */
4173
4174 void
4175 lang_check_failed (const char* file, int line, const char* function)
4176 {
4177   internal_error ("lang_* check: failed in %s, at %s:%d",
4178                   function, trim_filename (file), line);
4179 }
4180 #endif /* ENABLE_TREE_CHECKING */
4181
4182 #include "gt-cp-tree.h"