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