gcc/cp/tree.c

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