gcc/cp/tree.c

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