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 (EXPR_HAS_LOCATION (value))
 483     SET_EXPR_LOCATION (t, EXPR_LOCATION (value));
 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 (t), remove_attributes);
1739             vec_safe_push (vec, val);
1740             if (val != TREE_VALUE (t))
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 /* Cache of free ovl nodes.  Uses OVL_FUNCTION for chaining.  */
2135 static GTY((deletable)) tree ovl_cache;
2136
2137 /* Make a raw overload node containing FN.  */
2138
2139 tree
2140 ovl_make (tree fn, tree next)
2141 {
2142   tree result = ovl_cache;
2143
2144   if (result)
2145     {
2146       ovl_cache = OVL_FUNCTION (result);
2147       /* Zap the flags.  */
2148       memset (result, 0, sizeof (tree_base));
2149       TREE_SET_CODE (result, OVERLOAD);
2150     }
2151   else
2152     result = make_node (OVERLOAD);
2153
2154   if (TREE_CODE (fn) == OVERLOAD)
2155     OVL_NESTED_P (result) = true;
2156
2157   TREE_TYPE (result) = (next || TREE_CODE (fn) == TEMPLATE_DECL
2158                         ? unknown_type_node : TREE_TYPE (fn));
2159   OVL_FUNCTION (result) = fn;
2160   OVL_CHAIN (result) = next;
2161   return result;
2162 }
2163
2164 static tree
2165 ovl_copy (tree ovl)
2166 {
2167   tree result = ovl_cache;
2168
2169   if (result)
2170     {
2171       ovl_cache = OVL_FUNCTION (result);
2172       /* Zap the flags.  */
2173       memset (result, 0, sizeof (tree_base));
2174       TREE_SET_CODE (result, OVERLOAD);
2175     }
2176   else
2177     result = make_node (OVERLOAD);
2178
2179   gcc_checking_assert (!OVL_NESTED_P (ovl) && OVL_USED_P (ovl));
2180   TREE_TYPE (result) = TREE_TYPE (ovl);
2181   OVL_FUNCTION (result) = OVL_FUNCTION (ovl);
2182   OVL_CHAIN (result) = OVL_CHAIN (ovl);
2183   OVL_HIDDEN_P (result) = OVL_HIDDEN_P (ovl);
2184   OVL_USING_P (result) = OVL_USING_P (ovl);
2185   OVL_LOOKUP_P (result) = OVL_LOOKUP_P (ovl);
2186
2187   return result;
2188 }
2189
2190 /* Add FN to the (potentially NULL) overload set OVL.  USING_P is
2191    true, if FN is via a using declaration.  We also pay attention to
2192    DECL_HIDDEN.  Overloads are ordered as hidden, using, regular.  */
2193
2194 tree
2195 ovl_insert (tree fn, tree maybe_ovl, bool using_p)
2196 {
2197   bool copying = false; /* Checking use only.  */
2198   bool hidden_p = DECL_HIDDEN_P (fn);
2199   int weight = (hidden_p << 1) | (using_p << 0);
2200
2201   tree result = NULL_TREE;
2202   tree insert_after = NULL_TREE;
2203
2204   /* Find insertion point.  */
2205   while (maybe_ovl && TREE_CODE (maybe_ovl) == OVERLOAD
2206          && (weight < ((OVL_HIDDEN_P (maybe_ovl) << 1)
2207                        | (OVL_USING_P (maybe_ovl) << 0))))
2208     {
2209       gcc_checking_assert (!OVL_LOOKUP_P (maybe_ovl)
2210                            && (!copying || OVL_USED_P (maybe_ovl)));
2211       if (OVL_USED_P (maybe_ovl))
2212         {
2213           copying = true;
2214           maybe_ovl = ovl_copy (maybe_ovl);
2215           if (insert_after)
2216             OVL_CHAIN (insert_after) = maybe_ovl;
2217         }
2218       if (!result)
2219         result = maybe_ovl;
2220       insert_after = maybe_ovl;
2221       maybe_ovl = OVL_CHAIN (maybe_ovl);
2222     }
2223
2224   tree trail = fn;
2225   if (maybe_ovl || using_p || hidden_p || TREE_CODE (fn) == TEMPLATE_DECL)
2226     {
2227       trail = ovl_make (fn, maybe_ovl);
2228       if (hidden_p)
2229         OVL_HIDDEN_P (trail) = true;
2230       if (using_p)
2231         OVL_USING_P (trail) = true;
2232     }
2233
2234   if (insert_after)
2235     {
2236       OVL_CHAIN (insert_after) = trail;
2237       TREE_TYPE (insert_after) = unknown_type_node;
2238     }
2239   else
2240     result = trail;
2241
2242   return result;
2243 }
2244
2245 /* Skip any hidden names at the beginning of OVL.   */
2246
2247 tree
2248 ovl_skip_hidden (tree ovl)
2249 {
2250   for (;
2251        ovl && TREE_CODE (ovl) == OVERLOAD && OVL_HIDDEN_P (ovl);
2252        ovl = OVL_CHAIN (ovl))
2253     gcc_checking_assert (DECL_HIDDEN_P (OVL_FUNCTION (ovl)));
2254
2255   if (ovl && TREE_CODE (ovl) != OVERLOAD && DECL_HIDDEN_P (ovl))
2256     {
2257       /* Any hidden functions should have been wrapped in an
2258          overload, but injected friend classes will not.  */
2259       gcc_checking_assert (!DECL_DECLARES_FUNCTION_P (ovl));
2260       ovl = NULL_TREE;
2261     }
2262
2263   return ovl;
2264 }
2265
2266 /* NODE is an OVL_HIDDEN_P node which is now revealed.  */
2267
2268 tree
2269 ovl_iterator::reveal_node (tree overload, tree node)
2270 {
2271   /* We cannot have returned NODE as part of a lookup overload, so it
2272      cannot be USED.  */
2273   gcc_checking_assert (!OVL_USED_P (node));
2274
2275   OVL_HIDDEN_P (node) = false;
2276   if (tree chain = OVL_CHAIN (node))
2277     if (TREE_CODE (chain) == OVERLOAD
2278         && (OVL_USING_P (chain) || OVL_HIDDEN_P (chain)))
2279       {
2280         /* The node needs moving, and the simplest way is to remove it
2281            and reinsert.  */
2282         overload = remove_node (overload, node);
2283         overload = ovl_insert (OVL_FUNCTION (node), overload);
2284       }
2285   return overload;
2286 }
2287
2288 /* NODE is on the overloads of OVL.  Remove it.  If a predecessor is
2289    OVL_USED_P we must copy OVL nodes, because those are immutable.
2290    The removed node is unaltered and may continue to be iterated
2291    from (i.e. it is safe to remove a node from an overload one is
2292    currently iterating over).  */
2293
2294 tree
2295 ovl_iterator::remove_node (tree overload, tree node)
2296 {
2297   bool copying = false; /* Checking use only.  */
2298
2299   tree *slot = &overload;
2300   while (*slot != node)
2301     {
2302       tree probe = *slot;
2303       gcc_checking_assert (!OVL_LOOKUP_P (probe)
2304                            && (!copying || OVL_USED_P (probe)));
2305       if (OVL_USED_P (probe))
2306         {
2307           copying = true;
2308           probe = ovl_copy (probe);
2309           *slot = probe;
2310         }
2311
2312       slot = &OVL_CHAIN (probe);
2313     }
2314
2315   /* Stitch out NODE.  We don't have to worry about now making a
2316      singleton overload (and consequently maybe setting its type),
2317      because all uses of this function will be followed by inserting a
2318      new node that must follow the place we've cut this out from.  */
2319   if (TREE_CODE (node) != OVERLOAD)
2320     /* Cloned inherited ctors don't mark themselves as via_using.  */
2321     *slot = NULL_TREE;
2322   else
2323     *slot = OVL_CHAIN (node);
2324
2325   return overload;
2326 }
2327
2328 /* Mark or unmark a lookup set. */
2329
2330 void
2331 lookup_mark (tree ovl, bool val)
2332 {
2333   for (lkp_iterator iter (ovl); iter; ++iter)
2334     {
2335       gcc_checking_assert (LOOKUP_SEEN_P (*iter) != val);
2336       LOOKUP_SEEN_P (*iter) = val;
2337     }
2338 }
2339
2340 /* Add a set of new FNS into a lookup.  */
2341
2342 tree
2343 lookup_add (tree fns, tree lookup)
2344 {
2345   if (lookup || TREE_CODE (fns) == TEMPLATE_DECL)
2346     {
2347       lookup = ovl_make (fns, lookup);
2348       OVL_LOOKUP_P (lookup) = true;
2349     }
2350   else
2351     lookup = fns;
2352
2353   return lookup;
2354 }
2355
2356 /* FNS is a new overload set, add them to LOOKUP, if they are not
2357    already present there.  */
2358
2359 tree
2360 lookup_maybe_add (tree fns, tree lookup, bool deduping)
2361 {
2362   if (deduping)
2363     for (tree next, probe = fns; probe; probe = next)
2364       {
2365         tree fn = probe;
2366         next = NULL_TREE;
2367
2368         if (TREE_CODE (probe) == OVERLOAD)
2369           {
2370             fn = OVL_FUNCTION (probe);
2371             next = OVL_CHAIN (probe);
2372           }
2373
2374         if (!LOOKUP_SEEN_P (fn))
2375           LOOKUP_SEEN_P (fn) = true;
2376         else
2377           {
2378             /* This function was already seen.  Insert all the
2379                predecessors onto the lookup.  */
2380             for (; fns != probe; fns = OVL_CHAIN (fns))
2381               {
2382                 lookup = lookup_add (OVL_FUNCTION (fns), lookup);
2383                 /* Propagate OVL_USING, but OVL_HIDDEN doesn't matter.  */
2384                 if (OVL_USING_P (fns))
2385                   OVL_USING_P (lookup) = true;
2386               }
2387
2388             /* And now skip this function.  */
2389             fns = next;
2390           }
2391       }
2392
2393   if (fns)
2394     /* We ended in a set of new functions.  Add them all in one go.  */
2395     lookup = lookup_add (fns, lookup);
2396
2397   return lookup;
2398 }
2399
2400 /* Regular overload OVL is part of a kept lookup.  Mark the nodes on
2401    it as immutable.  */
2402
2403 static void
2404 ovl_used (tree ovl)
2405 {
2406   for (;
2407        ovl && TREE_CODE (ovl) == OVERLOAD
2408          && !OVL_USED_P (ovl);
2409        ovl = OVL_CHAIN (ovl))
2410     {
2411       gcc_checking_assert (!OVL_LOOKUP_P (ovl));
2412       OVL_USED_P (ovl) = true;
2413     }
2414 }
2415
2416 /* If KEEP is true, preserve the contents of a lookup so that it is
2417    available for a later instantiation.  Otherwise release the LOOKUP
2418    nodes for reuse.  */
2419
2420 void
2421 lookup_keep (tree lookup, bool keep)
2422 {
2423   for (;
2424        lookup && TREE_CODE (lookup) == OVERLOAD
2425          && OVL_LOOKUP_P (lookup) && !OVL_USED_P (lookup);
2426        lookup = OVL_CHAIN (lookup))
2427     if (keep)
2428       {
2429         OVL_USED_P (lookup) = true;
2430         ovl_used (OVL_FUNCTION (lookup));
2431       }
2432     else
2433       {
2434         OVL_FUNCTION (lookup) = ovl_cache;
2435         ovl_cache = lookup;
2436       }
2437
2438   if (keep)
2439     ovl_used (lookup);
2440 }
2441
2442 /* LIST is a TREE_LIST whose TREE_VALUEs may be OVERLOADS that need
2443    keeping, or may be ignored.  */
2444
2445 void
2446 lookup_list_keep (tree list, bool keep)
2447 {
2448   for (; list; list = TREE_CHAIN (list))
2449     {
2450       tree v = TREE_VALUE (list);
2451       if (TREE_CODE (v) == OVERLOAD)
2452         lookup_keep (v, keep);
2453     }
2454 }
2455
2456 /* Returns nonzero if X is an expression for a (possibly overloaded)
2457    function.  If "f" is a function or function template, "f", "c->f",
2458    "c.f", "C::f", and "f<int>" will all be considered possibly
2459    overloaded functions.  Returns 2 if the function is actually
2460    overloaded, i.e., if it is impossible to know the type of the
2461    function without performing overload resolution.  */
2462
2463 int
2464 is_overloaded_fn (tree x)
2465 {
2466   /* A baselink is also considered an overloaded function.  */
2467   if (TREE_CODE (x) == OFFSET_REF
2468       || TREE_CODE (x) == COMPONENT_REF)
2469     x = TREE_OPERAND (x, 1);
2470   x = MAYBE_BASELINK_FUNCTIONS (x);
2471   if (TREE_CODE (x) == TEMPLATE_ID_EXPR)
2472     x = TREE_OPERAND (x, 0);
2473
2474   if (DECL_FUNCTION_TEMPLATE_P (OVL_FIRST (x))
2475       || (TREE_CODE (x) == OVERLOAD && !OVL_SINGLE_P (x)))
2476     return 2;
2477
2478   return (TREE_CODE (x) == FUNCTION_DECL
2479           || TREE_CODE (x) == OVERLOAD);
2480 }
2481
2482 /* X is the CALL_EXPR_FN of a CALL_EXPR.  If X represents a dependent name
2483    (14.6.2), return the IDENTIFIER_NODE for that name.  Otherwise, return
2484    NULL_TREE.  */
2485
2486 tree
2487 dependent_name (tree x)
2488 {
2489   if (identifier_p (x))
2490     return x;
2491   if (TREE_CODE (x) == TEMPLATE_ID_EXPR)
2492     x = TREE_OPERAND (x, 0);
2493   if (TREE_CODE (x) == OVERLOAD || TREE_CODE (x) == FUNCTION_DECL)
2494     return OVL_NAME (x);
2495   return NULL_TREE;
2496 }
2497
2498 /* Returns true iff X is an expression for an overloaded function
2499    whose type cannot be known without performing overload
2500    resolution.  */
2501
2502 bool
2503 really_overloaded_fn (tree x)
2504 {
2505   return is_overloaded_fn (x) == 2;
2506 }
2507
2508 /* Get the overload set FROM refers to.  */
2509
2510 tree
2511 get_fns (tree from)
2512 {
2513   /* A baselink is also considered an overloaded function.  */
2514   if (TREE_CODE (from) == OFFSET_REF
2515       || TREE_CODE (from) == COMPONENT_REF)
2516     from = TREE_OPERAND (from, 1);
2517   if (BASELINK_P (from))
2518     from = BASELINK_FUNCTIONS (from);
2519   if (TREE_CODE (from) == TEMPLATE_ID_EXPR)
2520     from = TREE_OPERAND (from, 0);
2521   gcc_assert (TREE_CODE (from) == OVERLOAD
2522               || TREE_CODE (from) == FUNCTION_DECL);
2523   return from;
2524 }
2525
2526 /* Return the first function of the overload set FROM refers to.  */
2527
2528 tree
2529 get_first_fn (tree from)
2530 {
2531   return OVL_FIRST (get_fns (from));
2532 }
2533
2534 /* Return the scope where the overloaded functions OVL were found.  */
2535
2536 tree
2537 ovl_scope (tree ovl)
2538 {
2539   if (TREE_CODE (ovl) == OFFSET_REF
2540       || TREE_CODE (ovl) == COMPONENT_REF)
2541     ovl = TREE_OPERAND (ovl, 1);
2542   if (TREE_CODE (ovl) == BASELINK)
2543     return BINFO_TYPE (BASELINK_BINFO (ovl));
2544   if (TREE_CODE (ovl) == TEMPLATE_ID_EXPR)
2545     ovl = TREE_OPERAND (ovl, 0);
2546   /* Skip using-declarations.  */
2547   lkp_iterator iter (ovl);
2548   do
2549     ovl = *iter;
2550   while (iter.using_p () && ++iter);
2551
2552   return CP_DECL_CONTEXT (ovl);
2553 }
2554 \f
2555 #define PRINT_RING_SIZE 4
2556
2557 static const char *
2558 cxx_printable_name_internal (tree decl, int v, bool translate)
2559 {
2560   static unsigned int uid_ring[PRINT_RING_SIZE];
2561   static char *print_ring[PRINT_RING_SIZE];
2562   static bool trans_ring[PRINT_RING_SIZE];
2563   static int ring_counter;
2564   int i;
2565
2566   /* Only cache functions.  */
2567   if (v < 2
2568       || TREE_CODE (decl) != FUNCTION_DECL
2569       || DECL_LANG_SPECIFIC (decl) == 0)
2570     return lang_decl_name (decl, v, translate);
2571
2572   /* See if this print name is lying around.  */
2573   for (i = 0; i < PRINT_RING_SIZE; i++)
2574     if (uid_ring[i] == DECL_UID (decl) && translate == trans_ring[i])
2575       /* yes, so return it.  */
2576       return print_ring[i];
2577
2578   if (++ring_counter == PRINT_RING_SIZE)
2579     ring_counter = 0;
2580
2581   if (current_function_decl != NULL_TREE)
2582     {
2583       /* There may be both translated and untranslated versions of the
2584          name cached.  */
2585       for (i = 0; i < 2; i++)
2586         {
2587           if (uid_ring[ring_counter] == DECL_UID (current_function_decl))
2588             ring_counter += 1;
2589           if (ring_counter == PRINT_RING_SIZE)
2590             ring_counter = 0;
2591         }
2592       gcc_assert (uid_ring[ring_counter] != DECL_UID (current_function_decl));
2593     }
2594
2595   free (print_ring[ring_counter]);
2596
2597   print_ring[ring_counter] = xstrdup (lang_decl_name (decl, v, translate));
2598   uid_ring[ring_counter] = DECL_UID (decl);
2599   trans_ring[ring_counter] = translate;
2600   return print_ring[ring_counter];
2601 }
2602
2603 const char *
2604 cxx_printable_name (tree decl, int v)
2605 {
2606   return cxx_printable_name_internal (decl, v, false);
2607 }
2608
2609 const char *
2610 cxx_printable_name_translate (tree decl, int v)
2611 {
2612   return cxx_printable_name_internal (decl, v, true);
2613 }
2614 \f
2615 /* Return the canonical version of exception-specification RAISES for a C++17
2616    function type, for use in type comparison and building TYPE_CANONICAL.  */
2617
2618 tree
2619 canonical_eh_spec (tree raises)
2620 {
2621   if (raises == NULL_TREE)
2622     return raises;
2623   else if (DEFERRED_NOEXCEPT_SPEC_P (raises)
2624            || uses_template_parms (raises)
2625            || uses_template_parms (TREE_PURPOSE (raises)))
2626     /* Keep a dependent or deferred exception specification.  */
2627     return raises;
2628   else if (nothrow_spec_p (raises))
2629     /* throw() -> noexcept.  */
2630     return noexcept_true_spec;
2631   else
2632     /* For C++17 type matching, anything else -> nothing.  */
2633     return NULL_TREE;
2634 }
2635
2636 tree
2637 build_cp_fntype_variant (tree type, cp_ref_qualifier rqual,
2638                          tree raises, bool late)
2639 {
2640   cp_cv_quals type_quals = TYPE_QUALS (type);
2641
2642   if (cp_check_qualified_type (type, type, type_quals, rqual, raises, late))
2643     return type;
2644
2645   tree v = TYPE_MAIN_VARIANT (type);
2646   for (; v; v = TYPE_NEXT_VARIANT (v))
2647     if (cp_check_qualified_type (v, type, type_quals, rqual, raises, late))
2648       return v;
2649
2650   /* Need to build a new variant.  */
2651   v = build_variant_type_copy (type);
2652   TYPE_RAISES_EXCEPTIONS (v) = raises;
2653   TYPE_HAS_LATE_RETURN_TYPE (v) = late;
2654   switch (rqual)
2655     {
2656     case REF_QUAL_RVALUE:
2657       FUNCTION_RVALUE_QUALIFIED (v) = 1;
2658       FUNCTION_REF_QUALIFIED (v) = 1;
2659       break;
2660     case REF_QUAL_LVALUE:
2661       FUNCTION_RVALUE_QUALIFIED (v) = 0;
2662       FUNCTION_REF_QUALIFIED (v) = 1;
2663       break;
2664     default:
2665       FUNCTION_REF_QUALIFIED (v) = 0;
2666       break;
2667     }
2668
2669   /* Canonicalize the exception specification.  */
2670   tree cr = flag_noexcept_type ? canonical_eh_spec (raises) : NULL_TREE;
2671
2672   if (TYPE_STRUCTURAL_EQUALITY_P (type))
2673     /* Propagate structural equality. */
2674     SET_TYPE_STRUCTURAL_EQUALITY (v);
2675   else if (TYPE_CANONICAL (type) != type || cr != raises || late)
2676     /* Build the underlying canonical type, since it is different
2677        from TYPE. */
2678     TYPE_CANONICAL (v) = build_cp_fntype_variant (TYPE_CANONICAL (type),
2679                                                   rqual, cr, false);
2680   else
2681     /* T is its own canonical type. */
2682     TYPE_CANONICAL (v) = v;
2683
2684   return v;
2685 }
2686
2687 /* Build the FUNCTION_TYPE or METHOD_TYPE which may throw exceptions
2688    listed in RAISES.  */
2689
2690 tree
2691 build_exception_variant (tree type, tree raises)
2692 {
2693   cp_ref_qualifier rqual = type_memfn_rqual (type);
2694   bool late = TYPE_HAS_LATE_RETURN_TYPE (type);
2695   return build_cp_fntype_variant (type, rqual, raises, late);
2696 }
2697
2698 /* Given a TEMPLATE_TEMPLATE_PARM node T, create a new
2699    BOUND_TEMPLATE_TEMPLATE_PARM bound with NEWARGS as its template
2700    arguments.  */
2701
2702 tree
2703 bind_template_template_parm (tree t, tree newargs)
2704 {
2705   tree decl = TYPE_NAME (t);
2706   tree t2;
2707
2708   t2 = cxx_make_type (BOUND_TEMPLATE_TEMPLATE_PARM);
2709   decl = build_decl (input_location,
2710                      TYPE_DECL, DECL_NAME (decl), NULL_TREE);
2711
2712   /* These nodes have to be created to reflect new TYPE_DECL and template
2713      arguments.  */
2714   TEMPLATE_TYPE_PARM_INDEX (t2) = copy_node (TEMPLATE_TYPE_PARM_INDEX (t));
2715   TEMPLATE_PARM_DECL (TEMPLATE_TYPE_PARM_INDEX (t2)) = decl;
2716   TEMPLATE_TEMPLATE_PARM_TEMPLATE_INFO (t2)
2717     = build_template_info (TEMPLATE_TEMPLATE_PARM_TEMPLATE_DECL (t), newargs);
2718
2719   TREE_TYPE (decl) = t2;
2720   TYPE_NAME (t2) = decl;
2721   TYPE_STUB_DECL (t2) = decl;
2722   TYPE_SIZE (t2) = 0;
2723   SET_TYPE_STRUCTURAL_EQUALITY (t2);
2724
2725   return t2;
2726 }
2727
2728 /* Called from count_trees via walk_tree.  */
2729
2730 static tree
2731 count_trees_r (tree *tp, int *walk_subtrees, void *data)
2732 {
2733   ++*((int *) data);
2734
2735   if (TYPE_P (*tp))
2736     *walk_subtrees = 0;
2737
2738   return NULL_TREE;
2739 }
2740
2741 /* Debugging function for measuring the rough complexity of a tree
2742    representation.  */
2743
2744 int
2745 count_trees (tree t)
2746 {
2747   int n_trees = 0;
2748   cp_walk_tree_without_duplicates (&t, count_trees_r, &n_trees);
2749   return n_trees;
2750 }
2751
2752 /* Called from verify_stmt_tree via walk_tree.  */
2753
2754 static tree
2755 verify_stmt_tree_r (tree* tp, int * /*walk_subtrees*/, void* data)
2756 {
2757   tree t = *tp;
2758   hash_table<nofree_ptr_hash <tree_node> > *statements
2759       = static_cast <hash_table<nofree_ptr_hash <tree_node> > *> (data);
2760   tree_node **slot;
2761
2762   if (!STATEMENT_CODE_P (TREE_CODE (t)))
2763     return NULL_TREE;
2764
2765   /* If this statement is already present in the hash table, then
2766      there is a circularity in the statement tree.  */
2767   gcc_assert (!statements->find (t));
2768
2769   slot = statements->find_slot (t, INSERT);
2770   *slot = t;
2771
2772   return NULL_TREE;
2773 }
2774
2775 /* Debugging function to check that the statement T has not been
2776    corrupted.  For now, this function simply checks that T contains no
2777    circularities.  */
2778
2779 void
2780 verify_stmt_tree (tree t)
2781 {
2782   hash_table<nofree_ptr_hash <tree_node> > statements (37);
2783   cp_walk_tree (&t, verify_stmt_tree_r, &statements, NULL);
2784 }
2785
2786 /* Check if the type T depends on a type with no linkage and if so, return
2787    it.  If RELAXED_P then do not consider a class type declared within
2788    a vague-linkage function to have no linkage.  */
2789
2790 tree
2791 no_linkage_check (tree t, bool relaxed_p)
2792 {
2793   tree r;
2794
2795   /* There's no point in checking linkage on template functions; we
2796      can't know their complete types.  */
2797   if (processing_template_decl)
2798     return NULL_TREE;
2799
2800   switch (TREE_CODE (t))
2801     {
2802     case RECORD_TYPE:
2803       if (TYPE_PTRMEMFUNC_P (t))
2804         goto ptrmem;
2805       /* Lambda types that don't have mangling scope have no linkage.  We
2806          check CLASSTYPE_LAMBDA_EXPR for error_mark_node because
2807          when we get here from pushtag none of the lambda information is
2808          set up yet, so we want to assume that the lambda has linkage and
2809          fix it up later if not.  */
2810       if (CLASSTYPE_LAMBDA_EXPR (t)
2811           && CLASSTYPE_LAMBDA_EXPR (t) != error_mark_node
2812           && LAMBDA_TYPE_EXTRA_SCOPE (t) == NULL_TREE)
2813         return t;
2814       /* Fall through.  */
2815     case UNION_TYPE:
2816       if (!CLASS_TYPE_P (t))
2817         return NULL_TREE;
2818       /* Fall through.  */
2819     case ENUMERAL_TYPE:
2820       /* Only treat unnamed types as having no linkage if they're at
2821          namespace scope.  This is core issue 966.  */
2822       if (TYPE_UNNAMED_P (t) && TYPE_NAMESPACE_SCOPE_P (t))
2823         return t;
2824
2825       for (r = CP_TYPE_CONTEXT (t); ; )
2826         {
2827           /* If we're a nested type of a !TREE_PUBLIC class, we might not
2828              have linkage, or we might just be in an anonymous namespace.
2829              If we're in a TREE_PUBLIC class, we have linkage.  */
2830           if (TYPE_P (r) && !TREE_PUBLIC (TYPE_NAME (r)))
2831             return no_linkage_check (TYPE_CONTEXT (t), relaxed_p);
2832           else if (TREE_CODE (r) == FUNCTION_DECL)
2833             {
2834               if (!relaxed_p || !vague_linkage_p (r))
2835                 return t;
2836               else
2837                 r = CP_DECL_CONTEXT (r);
2838             }
2839           else
2840             break;
2841         }
2842
2843       return NULL_TREE;
2844
2845     case ARRAY_TYPE:
2846     case POINTER_TYPE:
2847     case REFERENCE_TYPE:
2848     case VECTOR_TYPE:
2849       return no_linkage_check (TREE_TYPE (t), relaxed_p);
2850
2851     case OFFSET_TYPE:
2852     ptrmem:
2853       r = no_linkage_check (TYPE_PTRMEM_POINTED_TO_TYPE (t),
2854                             relaxed_p);
2855       if (r)
2856         return r;
2857       return no_linkage_check (TYPE_PTRMEM_CLASS_TYPE (t), relaxed_p);
2858
2859     case METHOD_TYPE:
2860     case FUNCTION_TYPE:
2861       {
2862         tree parm = TYPE_ARG_TYPES (t);
2863         if (TREE_CODE (t) == METHOD_TYPE)
2864           /* The 'this' pointer isn't interesting; a method has the same
2865              linkage (or lack thereof) as its enclosing class.  */
2866           parm = TREE_CHAIN (parm);
2867         for (;
2868              parm && parm != void_list_node;
2869              parm = TREE_CHAIN (parm))
2870           {
2871             r = no_linkage_check (TREE_VALUE (parm), relaxed_p);
2872             if (r)
2873               return r;
2874           }
2875         return no_linkage_check (TREE_TYPE (t), relaxed_p);
2876       }
2877
2878     default:
2879       return NULL_TREE;
2880     }
2881 }
2882
2883 extern int depth_reached;
2884
2885 void
2886 cxx_print_statistics (void)
2887 {
2888   print_template_statistics ();
2889   if (GATHER_STATISTICS)
2890     fprintf (stderr, "maximum template instantiation depth reached: %d\n",
2891              depth_reached);
2892 }
2893
2894 /* Return, as an INTEGER_CST node, the number of elements for TYPE
2895    (which is an ARRAY_TYPE).  This counts only elements of the top
2896    array.  */
2897
2898 tree
2899 array_type_nelts_top (tree type)
2900 {
2901   return fold_build2_loc (input_location,
2902                       PLUS_EXPR, sizetype,
2903                       array_type_nelts (type),
2904                       size_one_node);
2905 }
2906
2907 /* Return, as an INTEGER_CST node, the number of elements for TYPE
2908    (which is an ARRAY_TYPE).  This one is a recursive count of all
2909    ARRAY_TYPEs that are clumped together.  */
2910
2911 tree
2912 array_type_nelts_total (tree type)
2913 {
2914   tree sz = array_type_nelts_top (type);
2915   type = TREE_TYPE (type);
2916   while (TREE_CODE (type) == ARRAY_TYPE)
2917     {
2918       tree n = array_type_nelts_top (type);
2919       sz = fold_build2_loc (input_location,
2920                         MULT_EXPR, sizetype, sz, n);
2921       type = TREE_TYPE (type);
2922     }
2923   return sz;
2924 }
2925
2926 struct bot_data
2927 {
2928   splay_tree target_remap;
2929   bool clear_location;
2930 };
2931
2932 /* Called from break_out_target_exprs via mapcar.  */
2933
2934 static tree
2935 bot_manip (tree* tp, int* walk_subtrees, void* data_)
2936 {
2937   bot_data &data = *(bot_data*)data_;
2938   splay_tree target_remap = data.target_remap;
2939   tree t = *tp;
2940
2941   if (!TYPE_P (t) && TREE_CONSTANT (t) && !TREE_SIDE_EFFECTS (t))
2942     {
2943       /* There can't be any TARGET_EXPRs or their slot variables below this
2944          point.  But we must make a copy, in case subsequent processing
2945          alters any part of it.  For example, during gimplification a cast
2946          of the form (T) &X::f (where "f" is a member function) will lead
2947          to replacing the PTRMEM_CST for &X::f with a VAR_DECL.  */
2948       *walk_subtrees = 0;
2949       *tp = unshare_expr (t);
2950       return NULL_TREE;
2951     }
2952   if (TREE_CODE (t) == TARGET_EXPR)
2953     {
2954       tree u;
2955
2956       if (TREE_CODE (TREE_OPERAND (t, 1)) == AGGR_INIT_EXPR)
2957         {
2958           u = build_cplus_new (TREE_TYPE (t), TREE_OPERAND (t, 1),
2959                                tf_warning_or_error);
2960           if (u == error_mark_node)
2961             return u;
2962           if (AGGR_INIT_ZERO_FIRST (TREE_OPERAND (t, 1)))
2963             AGGR_INIT_ZERO_FIRST (TREE_OPERAND (u, 1)) = true;
2964         }
2965       else
2966         u = build_target_expr_with_type (TREE_OPERAND (t, 1), TREE_TYPE (t),
2967                                          tf_warning_or_error);
2968
2969       TARGET_EXPR_IMPLICIT_P (u) = TARGET_EXPR_IMPLICIT_P (t);
2970       TARGET_EXPR_LIST_INIT_P (u) = TARGET_EXPR_LIST_INIT_P (t);
2971       TARGET_EXPR_DIRECT_INIT_P (u) = TARGET_EXPR_DIRECT_INIT_P (t);
2972
2973       /* Map the old variable to the new one.  */
2974       splay_tree_insert (target_remap,
2975                          (splay_tree_key) TREE_OPERAND (t, 0),
2976                          (splay_tree_value) TREE_OPERAND (u, 0));
2977
2978       TREE_OPERAND (u, 1) = break_out_target_exprs (TREE_OPERAND (u, 1),
2979                                                     data.clear_location);
2980       if (TREE_OPERAND (u, 1) == error_mark_node)
2981         return error_mark_node;
2982
2983       /* Replace the old expression with the new version.  */
2984       *tp = u;
2985       /* We don't have to go below this point; the recursive call to
2986          break_out_target_exprs will have handled anything below this
2987          point.  */
2988       *walk_subtrees = 0;
2989       return NULL_TREE;
2990     }
2991   if (TREE_CODE (*tp) == SAVE_EXPR)
2992     {
2993       t = *tp;
2994       splay_tree_node n = splay_tree_lookup (target_remap,
2995                                              (splay_tree_key) t);
2996       if (n)
2997         {
2998           *tp = (tree)n->value;
2999           *walk_subtrees = 0;
3000         }
3001       else
3002         {
3003           copy_tree_r (tp, walk_subtrees, NULL);
3004           splay_tree_insert (target_remap,
3005                              (splay_tree_key)t,
3006                              (splay_tree_value)*tp);
3007           /* Make sure we don't remap an already-remapped SAVE_EXPR.  */
3008           splay_tree_insert (target_remap,
3009                              (splay_tree_key)*tp,
3010                              (splay_tree_value)*tp);
3011         }
3012       return NULL_TREE;
3013     }
3014
3015   /* Make a copy of this node.  */
3016   t = copy_tree_r (tp, walk_subtrees, NULL);
3017   if (TREE_CODE (*tp) == CALL_EXPR || TREE_CODE (*tp) == AGGR_INIT_EXPR)
3018     if (!processing_template_decl)
3019       set_flags_from_callee (*tp);
3020   if (data.clear_location && EXPR_HAS_LOCATION (*tp))
3021     SET_EXPR_LOCATION (*tp, input_location);
3022   return t;
3023 }
3024
3025 /* Replace all remapped VAR_DECLs in T with their new equivalents.
3026    DATA is really a splay-tree mapping old variables to new
3027    variables.  */
3028
3029 static tree
3030 bot_replace (tree* t, int* /*walk_subtrees*/, void* data_)
3031 {
3032   bot_data &data = *(bot_data*)data_;
3033   splay_tree target_remap = data.target_remap;
3034
3035   if (VAR_P (*t))
3036     {
3037       splay_tree_node n = splay_tree_lookup (target_remap,
3038                                              (splay_tree_key) *t);
3039       if (n)
3040         *t = (tree) n->value;
3041     }
3042   else if (TREE_CODE (*t) == PARM_DECL
3043            && DECL_NAME (*t) == this_identifier
3044            && !DECL_CONTEXT (*t))
3045     {
3046       /* In an NSDMI we need to replace the 'this' parameter we used for
3047          parsing with the real one for this function.  */
3048       *t = current_class_ptr;
3049     }
3050   else if (TREE_CODE (*t) == CONVERT_EXPR
3051            && CONVERT_EXPR_VBASE_PATH (*t))
3052     {
3053       /* In an NSDMI build_base_path defers building conversions to virtual
3054          bases, and we handle it here.  */
3055       tree basetype = TYPE_MAIN_VARIANT (TREE_TYPE (TREE_TYPE (*t)));
3056       vec<tree, va_gc> *vbases = CLASSTYPE_VBASECLASSES (current_class_type);
3057       int i; tree binfo;
3058       FOR_EACH_VEC_SAFE_ELT (vbases, i, binfo)
3059         if (BINFO_TYPE (binfo) == basetype)
3060           break;
3061       *t = build_base_path (PLUS_EXPR, TREE_OPERAND (*t, 0), binfo, true,
3062                             tf_warning_or_error);
3063     }
3064
3065   return NULL_TREE;
3066 }
3067
3068 /* When we parse a default argument expression, we may create
3069    temporary variables via TARGET_EXPRs.  When we actually use the
3070    default-argument expression, we make a copy of the expression
3071    and replace the temporaries with appropriate local versions.
3072
3073    If CLEAR_LOCATION is true, override any EXPR_LOCATION with
3074    input_location.  */
3075
3076 tree
3077 break_out_target_exprs (tree t, bool clear_location /* = false */)
3078 {
3079   static int target_remap_count;
3080   static splay_tree target_remap;
3081
3082   if (!target_remap_count++)
3083     target_remap = splay_tree_new (splay_tree_compare_pointers,
3084                                    /*splay_tree_delete_key_fn=*/NULL,
3085                                    /*splay_tree_delete_value_fn=*/NULL);
3086   bot_data data = { target_remap, clear_location };
3087   if (cp_walk_tree (&t, bot_manip, &data, NULL) == error_mark_node)
3088     t = error_mark_node;
3089   cp_walk_tree (&t, bot_replace, &data, NULL);
3090
3091   if (!--target_remap_count)
3092     {
3093       splay_tree_delete (target_remap);
3094       target_remap = NULL;
3095     }
3096
3097   return t;
3098 }
3099
3100 /* Build an expression for the subobject of OBJ at CONSTRUCTOR index INDEX,
3101    which we expect to have type TYPE.  */
3102
3103 tree
3104 build_ctor_subob_ref (tree index, tree type, tree obj)
3105 {
3106   if (index == NULL_TREE)
3107     /* Can't refer to a particular member of a vector.  */
3108     obj = NULL_TREE;
3109   else if (TREE_CODE (index) == INTEGER_CST)
3110     obj = cp_build_array_ref (input_location, obj, index, tf_none);
3111   else
3112     obj = build_class_member_access_expr (obj, index, NULL_TREE,
3113                                           /*reference*/false, tf_none);
3114   if (obj)
3115     {
3116       tree objtype = TREE_TYPE (obj);
3117       if (TREE_CODE (objtype) == ARRAY_TYPE && !TYPE_DOMAIN (objtype))
3118         {
3119           /* When the destination object refers to a flexible array member
3120              verify that it matches the type of the source object except
3121              for its domain and qualifiers.  */
3122           gcc_assert (comptypes (TYPE_MAIN_VARIANT (type),
3123                                  TYPE_MAIN_VARIANT (objtype),
3124                                  COMPARE_REDECLARATION));
3125         }
3126       else
3127         gcc_assert (same_type_ignoring_top_level_qualifiers_p (type, objtype));
3128     }
3129
3130   return obj;
3131 }
3132
3133 struct replace_placeholders_t
3134 {
3135   tree obj;         /* The object to be substituted for a PLACEHOLDER_EXPR.  */
3136   tree exp;         /* The outermost exp.  */
3137   bool seen;        /* Whether we've encountered a PLACEHOLDER_EXPR.  */
3138   hash_set<tree> *pset; /* To avoid walking same trees multiple times.  */
3139 };
3140
3141 /* Like substitute_placeholder_in_expr, but handle C++ tree codes and
3142    build up subexpressions as we go deeper.  */
3143
3144 static tree
3145 replace_placeholders_r (tree* t, int* walk_subtrees, void* data_)
3146 {
3147   replace_placeholders_t *d = static_cast<replace_placeholders_t*>(data_);
3148   tree obj = d->obj;
3149
3150   if (TYPE_P (*t) || TREE_CONSTANT (*t))
3151     {
3152       *walk_subtrees = false;
3153       return NULL_TREE;
3154     }
3155
3156   switch (TREE_CODE (*t))
3157     {
3158     case PLACEHOLDER_EXPR:
3159       {
3160         tree x = obj;
3161         for (; !same_type_ignoring_top_level_qualifiers_p (TREE_TYPE (*t),
3162                                                            TREE_TYPE (x));
3163              x = TREE_OPERAND (x, 0))
3164           gcc_assert (handled_component_p (x));
3165         *t = unshare_expr (x);
3166         *walk_subtrees = false;
3167         d->seen = true;
3168       }
3169       break;
3170
3171     case CONSTRUCTOR:
3172       {
3173         constructor_elt *ce;
3174         vec<constructor_elt,va_gc> *v = CONSTRUCTOR_ELTS (*t);
3175         /* Don't walk into CONSTRUCTOR_PLACEHOLDER_BOUNDARY ctors
3176            other than the d->exp one, those have PLACEHOLDER_EXPRs
3177            related to another object.  */
3178         if ((CONSTRUCTOR_PLACEHOLDER_BOUNDARY (*t)
3179              && *t != d->exp)
3180             || d->pset->add (*t))
3181           {
3182             *walk_subtrees = false;
3183             return NULL_TREE;
3184           }
3185         for (unsigned i = 0; vec_safe_iterate (v, i, &ce); ++i)
3186           {
3187             tree *valp = &ce->value;
3188             tree type = TREE_TYPE (*valp);
3189             tree subob = obj;
3190
3191             if (TREE_CODE (*valp) == CONSTRUCTOR
3192                 && AGGREGATE_TYPE_P (type))
3193               {
3194                 /* If we're looking at the initializer for OBJ, then build
3195                    a sub-object reference.  If we're looking at an
3196                    initializer for another object, just pass OBJ down.  */
3197                 if (same_type_ignoring_top_level_qualifiers_p
3198                     (TREE_TYPE (*t), TREE_TYPE (obj)))
3199                   subob = build_ctor_subob_ref (ce->index, type, obj);
3200                 if (TREE_CODE (*valp) == TARGET_EXPR)
3201                   valp = &TARGET_EXPR_INITIAL (*valp);
3202               }
3203             d->obj = subob;
3204             cp_walk_tree (valp, replace_placeholders_r, data_, NULL);
3205             d->obj = obj;
3206           }
3207         *walk_subtrees = false;
3208         break;
3209       }
3210
3211     default:
3212       if (d->pset->add (*t))
3213         *walk_subtrees = false;
3214       break;
3215     }
3216
3217   return NULL_TREE;
3218 }
3219
3220 /* Replace PLACEHOLDER_EXPRs in EXP with object OBJ.  SEEN_P is set if
3221    a PLACEHOLDER_EXPR has been encountered.  */
3222
3223 tree
3224 replace_placeholders (tree exp, tree obj, bool *seen_p)
3225 {
3226   /* This is only relevant for C++14.  */
3227   if (cxx_dialect < cxx14)
3228     return exp;
3229
3230   /* If the object isn't a (member of a) class, do nothing.  */
3231   tree op0 = obj;
3232   while (TREE_CODE (op0) == COMPONENT_REF)
3233     op0 = TREE_OPERAND (op0, 0);
3234   if (!CLASS_TYPE_P (strip_array_types (TREE_TYPE (op0))))
3235     return exp;
3236
3237   tree *tp = &exp;
3238   if (TREE_CODE (exp) == TARGET_EXPR)
3239     tp = &TARGET_EXPR_INITIAL (exp);
3240   hash_set<tree> pset;
3241   replace_placeholders_t data = { obj, *tp, false, &pset };
3242   cp_walk_tree (tp, replace_placeholders_r, &data, NULL);
3243   if (seen_p)
3244     *seen_p = data.seen;
3245   return exp;
3246 }
3247
3248 /* Callback function for find_placeholders.  */
3249
3250 static tree
3251 find_placeholders_r (tree *t, int *walk_subtrees, void *)
3252 {
3253   if (TYPE_P (*t) || TREE_CONSTANT (*t))
3254     {
3255       *walk_subtrees = false;
3256       return NULL_TREE;
3257     }
3258
3259   switch (TREE_CODE (*t))
3260     {
3261     case PLACEHOLDER_EXPR:
3262       return *t;
3263
3264     case CONSTRUCTOR:
3265       if (CONSTRUCTOR_PLACEHOLDER_BOUNDARY (*t))
3266         *walk_subtrees = false;
3267       break;
3268
3269     default:
3270       break;
3271     }
3272
3273   return NULL_TREE;
3274 }
3275
3276 /* Return true if EXP contains a PLACEHOLDER_EXPR.  Don't walk into
3277    ctors with CONSTRUCTOR_PLACEHOLDER_BOUNDARY flag set.  */
3278
3279 bool
3280 find_placeholders (tree exp)
3281 {
3282   /* This is only relevant for C++14.  */
3283   if (cxx_dialect < cxx14)
3284     return false;
3285
3286   return cp_walk_tree_without_duplicates (&exp, find_placeholders_r, NULL);
3287 }
3288
3289 /* Similar to `build_nt', but for template definitions of dependent
3290    expressions  */
3291
3292 tree
3293 build_min_nt_loc (location_t loc, enum tree_code code, ...)
3294 {
3295   tree t;
3296   int length;
3297   int i;
3298   va_list p;
3299
3300   gcc_assert (TREE_CODE_CLASS (code) != tcc_vl_exp);
3301
3302   va_start (p, code);
3303
3304   t = make_node (code);
3305   SET_EXPR_LOCATION (t, loc);
3306   length = TREE_CODE_LENGTH (code);
3307
3308   for (i = 0; i < length; i++)
3309     {
3310       tree x = va_arg (p, tree);
3311       TREE_OPERAND (t, i) = x;
3312       if (x && TREE_CODE (x) == OVERLOAD)
3313         lookup_keep (x, true);
3314     }
3315
3316   va_end (p);
3317   return t;
3318 }
3319
3320 /* Similar to `build', but for template definitions.  */
3321
3322 tree
3323 build_min (enum tree_code code, tree tt, ...)
3324 {
3325   tree t;
3326   int length;
3327   int i;
3328   va_list p;
3329
3330   gcc_assert (TREE_CODE_CLASS (code) != tcc_vl_exp);
3331
3332   va_start (p, tt);
3333
3334   t = make_node (code);
3335   length = TREE_CODE_LENGTH (code);
3336   TREE_TYPE (t) = tt;
3337
3338   for (i = 0; i < length; i++)
3339     {
3340       tree x = va_arg (p, tree);
3341       TREE_OPERAND (t, i) = x;
3342       if (x)
3343         {
3344           if (!TYPE_P (x) && TREE_SIDE_EFFECTS (x))
3345             TREE_SIDE_EFFECTS (t) = 1;
3346           if (TREE_CODE (x) == OVERLOAD)
3347             lookup_keep (x, true);
3348         }
3349     }
3350
3351   va_end (p);
3352
3353   if (code == CAST_EXPR)
3354     /* The single operand is a TREE_LIST, which we have to check.  */
3355     lookup_list_keep (TREE_OPERAND (t, 0), true);
3356
3357   return t;
3358 }
3359
3360 /* Similar to `build', but for template definitions of non-dependent
3361    expressions. NON_DEP is the non-dependent expression that has been
3362    built.  */
3363
3364 tree
3365 build_min_non_dep (enum tree_code code, tree non_dep, ...)
3366 {
3367   tree t;
3368   int length;
3369   int i;
3370   va_list p;
3371
3372   gcc_assert (TREE_CODE_CLASS (code) != tcc_vl_exp);
3373
3374   va_start (p, non_dep);
3375
3376   if (REFERENCE_REF_P (non_dep))
3377     non_dep = TREE_OPERAND (non_dep, 0);
3378
3379   t = make_node (code);
3380   length = TREE_CODE_LENGTH (code);
3381   TREE_TYPE (t) = unlowered_expr_type (non_dep);
3382   TREE_SIDE_EFFECTS (t) = TREE_SIDE_EFFECTS (non_dep);
3383
3384   for (i = 0; i < length; i++)
3385     {
3386       tree x = va_arg (p, tree);
3387       TREE_OPERAND (t, i) = x;
3388       if (x && TREE_CODE (x) == OVERLOAD)
3389         lookup_keep (x, true);
3390     }
3391
3392   if (code == COMPOUND_EXPR && TREE_CODE (non_dep) != COMPOUND_EXPR)
3393     /* This should not be considered a COMPOUND_EXPR, because it
3394        resolves to an overload.  */
3395     COMPOUND_EXPR_OVERLOADED (t) = 1;
3396
3397   va_end (p);
3398   return convert_from_reference (t);
3399 }
3400
3401 /* Similar to build_min_nt, but call expressions  */
3402
3403 tree
3404 build_min_nt_call_vec (tree fn, vec<tree, va_gc> *args)
3405 {
3406   tree ret, t;
3407   unsigned int ix;
3408
3409   ret = build_vl_exp (CALL_EXPR, vec_safe_length (args) + 3);
3410   CALL_EXPR_FN (ret) = fn;
3411   CALL_EXPR_STATIC_CHAIN (ret) = NULL_TREE;
3412   FOR_EACH_VEC_SAFE_ELT (args, ix, t)
3413     {
3414       CALL_EXPR_ARG (ret, ix) = t;
3415       if (TREE_CODE (t) == OVERLOAD)
3416         lookup_keep (t, true);
3417     }
3418   return ret;
3419 }
3420
3421 /* Similar to `build_min_nt_call_vec', but for template definitions of
3422    non-dependent expressions. NON_DEP is the non-dependent expression
3423    that has been built.  */
3424
3425 tree
3426 build_min_non_dep_call_vec (tree non_dep, tree fn, vec<tree, va_gc> *argvec)
3427 {
3428   tree t = build_min_nt_call_vec (fn, argvec);
3429   if (REFERENCE_REF_P (non_dep))
3430     non_dep = TREE_OPERAND (non_dep, 0);
3431   TREE_TYPE (t) = TREE_TYPE (non_dep);
3432   TREE_SIDE_EFFECTS (t) = TREE_SIDE_EFFECTS (non_dep);
3433   return convert_from_reference (t);
3434 }
3435
3436 /* Similar to build_min_non_dep, but for expressions that have been resolved to
3437    a call to an operator overload.  OP is the operator that has been
3438    overloaded.  NON_DEP is the non-dependent expression that's been built,
3439    which should be a CALL_EXPR or an INDIRECT_REF to a CALL_EXPR.  OVERLOAD is
3440    the overload that NON_DEP is calling.  */
3441
3442 tree
3443 build_min_non_dep_op_overload (enum tree_code op,
3444                                tree non_dep,
3445                                tree overload, ...)
3446 {
3447   va_list p;
3448   int nargs, expected_nargs;
3449   tree fn, call;
3450   vec<tree, va_gc> *args;
3451
3452   non_dep = extract_call_expr (non_dep);
3453
3454   nargs = call_expr_nargs (non_dep);
3455
3456   expected_nargs = cp_tree_code_length (op);
3457   if ((op == POSTINCREMENT_EXPR
3458        || op == POSTDECREMENT_EXPR)
3459       /* With -fpermissive non_dep could be operator++().  */
3460       && (!flag_permissive || nargs != expected_nargs))
3461     expected_nargs += 1;
3462   gcc_assert (nargs == expected_nargs);
3463
3464   args = make_tree_vector ();
3465   va_start (p, overload);
3466
3467   if (TREE_CODE (TREE_TYPE (overload)) == FUNCTION_TYPE)
3468     {
3469       fn = overload;
3470       for (int i = 0; i < nargs; i++)
3471         {
3472           tree arg = va_arg (p, tree);
3473           vec_safe_push (args, arg);
3474         }
3475     }
3476   else if (TREE_CODE (TREE_TYPE (overload)) == METHOD_TYPE)
3477     {
3478       tree object = va_arg (p, tree);
3479       tree binfo = TYPE_BINFO (TREE_TYPE (object));
3480       tree method = build_baselink (binfo, binfo, overload, NULL_TREE);
3481       fn = build_min (COMPONENT_REF, TREE_TYPE (overload),
3482                       object, method, NULL_TREE);
3483       for (int i = 1; i < nargs; i++)
3484         {
3485           tree arg = va_arg (p, tree);
3486           vec_safe_push (args, arg);
3487         }
3488     }
3489   else
3490    gcc_unreachable ();
3491
3492   va_end (p);
3493   call = build_min_non_dep_call_vec (non_dep, fn, args);
3494   release_tree_vector (args);
3495
3496   tree call_expr = extract_call_expr (call);
3497   KOENIG_LOOKUP_P (call_expr) = KOENIG_LOOKUP_P (non_dep);
3498   CALL_EXPR_OPERATOR_SYNTAX (call_expr) = true;
3499   CALL_EXPR_ORDERED_ARGS (call_expr) = CALL_EXPR_ORDERED_ARGS (non_dep);
3500   CALL_EXPR_REVERSE_ARGS (call_expr) = CALL_EXPR_REVERSE_ARGS (non_dep);
3501
3502   return call;
3503 }
3504
3505 /* Return a new tree vec copied from VEC, with ELT inserted at index IDX.  */
3506
3507 vec<tree, va_gc> *
3508 vec_copy_and_insert (vec<tree, va_gc> *old_vec, tree elt, unsigned idx)
3509 {
3510   unsigned len = vec_safe_length (old_vec);
3511   gcc_assert (idx <= len);
3512
3513   vec<tree, va_gc> *new_vec = NULL;
3514   vec_alloc (new_vec, len + 1);
3515
3516   unsigned i;
3517   for (i = 0; i < len; ++i)
3518     {
3519       if (i == idx)
3520         new_vec->quick_push (elt);
3521       new_vec->quick_push ((*old_vec)[i]);
3522     }
3523   if (i == idx)
3524     new_vec->quick_push (elt);
3525
3526   return new_vec;
3527 }
3528
3529 tree
3530 get_type_decl (tree t)
3531 {
3532   if (TREE_CODE (t) == TYPE_DECL)
3533     return t;
3534   if (TYPE_P (t))
3535     return TYPE_STUB_DECL (t);
3536   gcc_assert (t == error_mark_node);
3537   return t;
3538 }
3539
3540 /* Returns the namespace that contains DECL, whether directly or
3541    indirectly.  */
3542
3543 tree
3544 decl_namespace_context (tree decl)
3545 {
3546   while (1)
3547     {
3548       if (TREE_CODE (decl) == NAMESPACE_DECL)
3549         return decl;
3550       else if (TYPE_P (decl))
3551         decl = CP_DECL_CONTEXT (TYPE_MAIN_DECL (decl));
3552       else
3553         decl = CP_DECL_CONTEXT (decl);
3554     }
3555 }
3556
3557 /* Returns true if decl is within an anonymous namespace, however deeply
3558    nested, or false otherwise.  */
3559
3560 bool
3561 decl_anon_ns_mem_p (const_tree decl)
3562 {
3563   while (TREE_CODE (decl) != NAMESPACE_DECL)
3564     {
3565       /* Classes inside anonymous namespaces have TREE_PUBLIC == 0.  */
3566       if (TYPE_P (decl))
3567         return !TREE_PUBLIC (TYPE_MAIN_DECL (decl));
3568
3569       decl = CP_DECL_CONTEXT (decl);
3570     }
3571   return !TREE_PUBLIC (decl);
3572 }
3573
3574 /* Subroutine of cp_tree_equal: t1 and t2 are the CALL_EXPR_FNs of two
3575    CALL_EXPRS.  Return whether they are equivalent.  */
3576
3577 static bool
3578 called_fns_equal (tree t1, tree t2)
3579 {
3580   /* Core 1321: dependent names are equivalent even if the overload sets
3581      are different.  But do compare explicit template arguments.  */
3582   tree name1 = dependent_name (t1);
3583   tree name2 = dependent_name (t2);
3584   if (name1 || name2)
3585     {
3586       tree targs1 = NULL_TREE, targs2 = NULL_TREE;
3587
3588       if (name1 != name2)
3589         return false;
3590
3591       if (TREE_CODE (t1) == TEMPLATE_ID_EXPR)
3592         targs1 = TREE_OPERAND (t1, 1);
3593       if (TREE_CODE (t2) == TEMPLATE_ID_EXPR)
3594         targs2 = TREE_OPERAND (t2, 1);
3595       return cp_tree_equal (targs1, targs2);
3596     }
3597   else
3598     return cp_tree_equal (t1, t2);
3599 }
3600
3601 /* Return truthvalue of whether T1 is the same tree structure as T2.
3602    Return 1 if they are the same. Return 0 if they are different.  */
3603
3604 bool
3605 cp_tree_equal (tree t1, tree t2)
3606 {
3607   enum tree_code code1, code2;
3608
3609   if (t1 == t2)
3610     return true;
3611   if (!t1 || !t2)
3612     return false;
3613
3614   code1 = TREE_CODE (t1);
3615   code2 = TREE_CODE (t2);
3616
3617   if (code1 != code2)
3618     return false;
3619
3620   if (CONSTANT_CLASS_P (t1)
3621       && !same_type_p (TREE_TYPE (t1), TREE_TYPE (t2)))
3622     return false;
3623
3624   switch (code1)
3625     {
3626     case VOID_CST:
3627       /* There's only a single VOID_CST node, so we should never reach
3628          here.  */
3629       gcc_unreachable ();
3630
3631     case INTEGER_CST:
3632       return tree_int_cst_equal (t1, t2);
3633
3634     case REAL_CST:
3635       return real_equal (&TREE_REAL_CST (t1), &TREE_REAL_CST (t2));
3636
3637     case STRING_CST:
3638       return TREE_STRING_LENGTH (t1) == TREE_STRING_LENGTH (t2)
3639         && !memcmp (TREE_STRING_POINTER (t1), TREE_STRING_POINTER (t2),
3640                     TREE_STRING_LENGTH (t1));
3641
3642     case FIXED_CST:
3643       return FIXED_VALUES_IDENTICAL (TREE_FIXED_CST (t1),
3644                                      TREE_FIXED_CST (t2));
3645
3646     case COMPLEX_CST:
3647       return cp_tree_equal (TREE_REALPART (t1), TREE_REALPART (t2))
3648         && cp_tree_equal (TREE_IMAGPART (t1), TREE_IMAGPART (t2));
3649
3650     case VECTOR_CST:
3651       return operand_equal_p (t1, t2, OEP_ONLY_CONST);
3652
3653     case CONSTRUCTOR:
3654       /* We need to do this when determining whether or not two
3655          non-type pointer to member function template arguments
3656          are the same.  */
3657       if (!same_type_p (TREE_TYPE (t1), TREE_TYPE (t2))
3658           || CONSTRUCTOR_NELTS (t1) != CONSTRUCTOR_NELTS (t2))
3659         return false;
3660       {
3661         tree field, value;
3662         unsigned int i;
3663         FOR_EACH_CONSTRUCTOR_ELT (CONSTRUCTOR_ELTS (t1), i, field, value)
3664           {
3665             constructor_elt *elt2 = CONSTRUCTOR_ELT (t2, i);
3666             if (!cp_tree_equal (field, elt2->index)
3667                 || !cp_tree_equal (value, elt2->value))
3668               return false;
3669           }
3670       }
3671       return true;
3672
3673     case TREE_LIST:
3674       if (!cp_tree_equal (TREE_PURPOSE (t1), TREE_PURPOSE (t2)))
3675         return false;
3676       if (!cp_tree_equal (TREE_VALUE (t1), TREE_VALUE (t2)))
3677         return false;
3678       return cp_tree_equal (TREE_CHAIN (t1), TREE_CHAIN (t2));
3679
3680     case SAVE_EXPR:
3681       return cp_tree_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0));
3682
3683     case CALL_EXPR:
3684       {
3685         tree arg1, arg2;
3686         call_expr_arg_iterator iter1, iter2;
3687         if (!called_fns_equal (CALL_EXPR_FN (t1), CALL_EXPR_FN (t2)))
3688           return false;
3689         for (arg1 = first_call_expr_arg (t1, &iter1),
3690                arg2 = first_call_expr_arg (t2, &iter2);
3691              arg1 && arg2;
3692              arg1 = next_call_expr_arg (&iter1),
3693                arg2 = next_call_expr_arg (&iter2))
3694           if (!cp_tree_equal (arg1, arg2))
3695             return false;
3696         if (arg1 || arg2)
3697           return false;
3698         return true;
3699       }
3700
3701     case TARGET_EXPR:
3702       {
3703         tree o1 = TREE_OPERAND (t1, 0);
3704         tree o2 = TREE_OPERAND (t2, 0);
3705
3706         /* Special case: if either target is an unallocated VAR_DECL,
3707            it means that it's going to be unified with whatever the
3708            TARGET_EXPR is really supposed to initialize, so treat it
3709            as being equivalent to anything.  */
3710         if (VAR_P (o1) && DECL_NAME (o1) == NULL_TREE
3711             && !DECL_RTL_SET_P (o1))
3712           /*Nop*/;
3713         else if (VAR_P (o2) && DECL_NAME (o2) == NULL_TREE
3714                  && !DECL_RTL_SET_P (o2))
3715           /*Nop*/;
3716         else if (!cp_tree_equal (o1, o2))
3717           return false;
3718
3719         return cp_tree_equal (TREE_OPERAND (t1, 1), TREE_OPERAND (t2, 1));
3720       }
3721
3722     case PARM_DECL:
3723       /* For comparing uses of parameters in late-specified return types
3724          with an out-of-class definition of the function, but can also come
3725          up for expressions that involve 'this' in a member function
3726          template.  */
3727
3728       if (comparing_specializations && !CONSTRAINT_VAR_P (t1))
3729         /* When comparing hash table entries, only an exact match is
3730            good enough; we don't want to replace 'this' with the
3731            version from another function.  But be more flexible
3732            with local parameters in a requires-expression.  */
3733         return false;
3734
3735       if (same_type_p (TREE_TYPE (t1), TREE_TYPE (t2)))
3736         {
3737           if (DECL_ARTIFICIAL (t1) ^ DECL_ARTIFICIAL (t2))
3738             return false;
3739           if (CONSTRAINT_VAR_P (t1) ^ CONSTRAINT_VAR_P (t2))
3740             return false;
3741           if (DECL_ARTIFICIAL (t1)
3742               || (DECL_PARM_LEVEL (t1) == DECL_PARM_LEVEL (t2)
3743                   && DECL_PARM_INDEX (t1) == DECL_PARM_INDEX (t2)))
3744             return true;
3745         }
3746       return false;
3747
3748     case VAR_DECL:
3749     case CONST_DECL:
3750     case FIELD_DECL:
3751     case FUNCTION_DECL:
3752     case TEMPLATE_DECL:
3753     case IDENTIFIER_NODE:
3754     case SSA_NAME:
3755       return false;
3756
3757     case BASELINK:
3758       return (BASELINK_BINFO (t1) == BASELINK_BINFO (t2)
3759               && BASELINK_ACCESS_BINFO (t1) == BASELINK_ACCESS_BINFO (t2)
3760               && BASELINK_QUALIFIED_P (t1) == BASELINK_QUALIFIED_P (t2)
3761               && cp_tree_equal (BASELINK_FUNCTIONS (t1),
3762                                 BASELINK_FUNCTIONS (t2)));
3763
3764     case TEMPLATE_PARM_INDEX:
3765       return (TEMPLATE_PARM_IDX (t1) == TEMPLATE_PARM_IDX (t2)
3766               && TEMPLATE_PARM_LEVEL (t1) == TEMPLATE_PARM_LEVEL (t2)
3767               && (TEMPLATE_PARM_PARAMETER_PACK (t1)
3768                   == TEMPLATE_PARM_PARAMETER_PACK (t2))
3769               && same_type_p (TREE_TYPE (TEMPLATE_PARM_DECL (t1)),
3770                               TREE_TYPE (TEMPLATE_PARM_DECL (t2))));
3771
3772     case TEMPLATE_ID_EXPR:
3773       return (cp_tree_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0))
3774               && cp_tree_equal (TREE_OPERAND (t1, 1), TREE_OPERAND (t2, 1)));
3775
3776     case CONSTRAINT_INFO:
3777       return cp_tree_equal (CI_ASSOCIATED_CONSTRAINTS (t1),
3778                             CI_ASSOCIATED_CONSTRAINTS (t2));
3779
3780     case CHECK_CONSTR:
3781       return (CHECK_CONSTR_CONCEPT (t1) == CHECK_CONSTR_CONCEPT (t2)
3782               && comp_template_args (CHECK_CONSTR_ARGS (t1),
3783                                      CHECK_CONSTR_ARGS (t2)));
3784
3785     case TREE_VEC:
3786       {
3787         unsigned ix;
3788         if (TREE_VEC_LENGTH (t1) != TREE_VEC_LENGTH (t2))
3789           return false;
3790         for (ix = TREE_VEC_LENGTH (t1); ix--;)
3791           if (!cp_tree_equal (TREE_VEC_ELT (t1, ix),
3792                               TREE_VEC_ELT (t2, ix)))
3793             return false;
3794         return true;
3795       }
3796
3797     case SIZEOF_EXPR:
3798     case ALIGNOF_EXPR:
3799       {
3800         tree o1 = TREE_OPERAND (t1, 0);
3801         tree o2 = TREE_OPERAND (t2, 0);
3802
3803         if (code1 == SIZEOF_EXPR)
3804           {
3805             if (SIZEOF_EXPR_TYPE_P (t1))
3806               o1 = TREE_TYPE (o1);
3807             if (SIZEOF_EXPR_TYPE_P (t2))
3808               o2 = TREE_TYPE (o2);
3809           }
3810         if (TREE_CODE (o1) != TREE_CODE (o2))
3811           return false;
3812         if (TYPE_P (o1))
3813           return same_type_p (o1, o2);
3814         else
3815           return cp_tree_equal (o1, o2);
3816       }
3817
3818     case MODOP_EXPR:
3819       {
3820         tree t1_op1, t2_op1;
3821
3822         if (!cp_tree_equal (TREE_OPERAND (t1, 0), TREE_OPERAND (t2, 0)))
3823           return false;
3824
3825         t1_op1 = TREE_OPERAND (t1, 1);
3826         t2_op1 = TREE_OPERAND (t2, 1);
3827         if (TREE_CODE (t1_op1) != TREE_CODE (t2_op1))
3828           return false;
3829
3830         return cp_tree_equal (TREE_OPERAND (t1, 2), TREE_OPERAND (t2, 2));
3831       }
3832
3833     case PTRMEM_CST:
3834       /* Two pointer-to-members are the same if they point to the same
3835          field or function in the same class.  */
3836       if (PTRMEM_CST_MEMBER (t1) != PTRMEM_CST_MEMBER (t2))
3837         return false;
3838
3839       return same_type_p (PTRMEM_CST_CLASS (t1), PTRMEM_CST_CLASS (t2));
3840
3841     case OVERLOAD:
3842       {
3843         /* Two overloads. Must be exactly the same set of decls.  */
3844         lkp_iterator first (t1);
3845         lkp_iterator second (t2);
3846
3847         for (; first && second; ++first, ++second)
3848           if (*first != *second)
3849             return false;
3850         return !(first || second);
3851       }
3852
3853     case TRAIT_EXPR:
3854       if (TRAIT_EXPR_KIND (t1) != TRAIT_EXPR_KIND (t2))
3855         return false;
3856       return same_type_p (TRAIT_EXPR_TYPE1 (t1), TRAIT_EXPR_TYPE1 (t2))
3857         && cp_tree_equal (TRAIT_EXPR_TYPE2 (t1), TRAIT_EXPR_TYPE2 (t2));
3858
3859     case CAST_EXPR:
3860     case STATIC_CAST_EXPR:
3861     case REINTERPRET_CAST_EXPR:
3862     case CONST_CAST_EXPR:
3863     case DYNAMIC_CAST_EXPR:
3864     case IMPLICIT_CONV_EXPR:
3865     case NEW_EXPR:
3866     CASE_CONVERT:
3867     case NON_LVALUE_EXPR:
3868     case VIEW_CONVERT_EXPR:
3869       if (!same_type_p (TREE_TYPE (t1), TREE_TYPE (t2)))
3870         return false;
3871       /* Now compare operands as usual.  */
3872       break;
3873
3874     case DEFERRED_NOEXCEPT:
3875       return (cp_tree_equal (DEFERRED_NOEXCEPT_PATTERN (t1),
3876                              DEFERRED_NOEXCEPT_PATTERN (t2))
3877               && comp_template_args (DEFERRED_NOEXCEPT_ARGS (t1),
3878                                      DEFERRED_NOEXCEPT_ARGS (t2)));
3879       break;
3880
3881     case USING_DECL:
3882       if (DECL_DEPENDENT_P (t1) && DECL_DEPENDENT_P (t2))
3883         return (cp_tree_equal (USING_DECL_SCOPE (t1),
3884                                USING_DECL_SCOPE (t2))
3885                 && cp_tree_equal (DECL_NAME (t1),
3886                                   DECL_NAME (t2)));
3887       return false;
3888
3889     default:
3890       break;
3891     }
3892
3893   switch (TREE_CODE_CLASS (code1))
3894     {
3895     case tcc_unary:
3896     case tcc_binary:
3897     case tcc_comparison:
3898     case tcc_expression:
3899     case tcc_vl_exp:
3900     case tcc_reference:
3901     case tcc_statement:
3902       {
3903         int i, n;
3904
3905         n = cp_tree_operand_length (t1);
3906         if (TREE_CODE_CLASS (code1) == tcc_vl_exp
3907             && n != TREE_OPERAND_LENGTH (t2))
3908           return false;
3909
3910         for (i = 0; i < n; ++i)
3911           if (!cp_tree_equal (TREE_OPERAND (t1, i), TREE_OPERAND (t2, i)))
3912             return false;
3913
3914         return true;
3915       }
3916
3917     case tcc_type:
3918       return same_type_p (t1, t2);
3919     default:
3920       gcc_unreachable ();
3921     }
3922   /* We can get here with --disable-checking.  */
3923   return false;
3924 }
3925
3926 /* The type of ARG when used as an lvalue.  */
3927
3928 tree
3929 lvalue_type (tree arg)
3930 {
3931   tree type = TREE_TYPE (arg);
3932   return type;
3933 }
3934
3935 /* The type of ARG for printing error messages; denote lvalues with
3936    reference types.  */
3937
3938 tree
3939 error_type (tree arg)
3940 {
3941   tree type = TREE_TYPE (arg);
3942
3943   if (TREE_CODE (type) == ARRAY_TYPE)
3944     ;
3945   else if (TREE_CODE (type) == ERROR_MARK)
3946     ;
3947   else if (lvalue_p (arg))
3948     type = build_reference_type (lvalue_type (arg));
3949   else if (MAYBE_CLASS_TYPE_P (type))
3950     type = lvalue_type (arg);
3951
3952   return type;
3953 }
3954
3955 /* Does FUNCTION use a variable-length argument list?  */
3956
3957 int
3958 varargs_function_p (const_tree function)
3959 {
3960   return stdarg_p (TREE_TYPE (function));
3961 }
3962
3963 /* Returns 1 if decl is a member of a class.  */
3964
3965 int
3966 member_p (const_tree decl)
3967 {
3968   const_tree const ctx = DECL_CONTEXT (decl);
3969   return (ctx && TYPE_P (ctx));
3970 }
3971
3972 /* Create a placeholder for member access where we don't actually have an
3973    object that the access is against.  */
3974
3975 tree
3976 build_dummy_object (tree type)
3977 {
3978   tree decl = build1 (CONVERT_EXPR, build_pointer_type (type), void_node);
3979   return cp_build_fold_indirect_ref (decl);
3980 }
3981
3982 /* We've gotten a reference to a member of TYPE.  Return *this if appropriate,
3983    or a dummy object otherwise.  If BINFOP is non-0, it is filled with the
3984    binfo path from current_class_type to TYPE, or 0.  */
3985
3986 tree
3987 maybe_dummy_object (tree type, tree* binfop)
3988 {
3989   tree decl, context;
3990   tree binfo;
3991   tree current = current_nonlambda_class_type ();
3992
3993   if (current
3994       && (binfo = lookup_base (current, type, ba_any, NULL,
3995                                tf_warning_or_error)))
3996     context = current;
3997   else
3998     {
3999       /* Reference from a nested class member function.  */
4000       context = type;
4001       binfo = TYPE_BINFO (type);
4002     }
4003
4004   if (binfop)
4005     *binfop = binfo;
4006
4007   if (current_class_ref
4008       /* current_class_ref might not correspond to current_class_type if
4009          we're in tsubst_default_argument or a lambda-declarator; in either
4010          case, we want to use current_class_ref if it matches CONTEXT.  */
4011       && (same_type_ignoring_top_level_qualifiers_p
4012           (TREE_TYPE (current_class_ref), context)))
4013     decl = current_class_ref;
4014   else
4015     decl = build_dummy_object (context);
4016
4017   return decl;
4018 }
4019
4020 /* Returns 1 if OB is a placeholder object, or a pointer to one.  */
4021
4022 int
4023 is_dummy_object (const_tree ob)
4024 {
4025   if (INDIRECT_REF_P (ob))
4026     ob = TREE_OPERAND (ob, 0);
4027   return (TREE_CODE (ob) == CONVERT_EXPR
4028           && TREE_OPERAND (ob, 0) == void_node);
4029 }
4030
4031 /* Returns 1 iff type T is something we want to treat as a scalar type for
4032    the purpose of deciding whether it is trivial/POD/standard-layout.  */
4033
4034 bool
4035 scalarish_type_p (const_tree t)
4036 {
4037   if (t == error_mark_node)
4038     return 1;
4039
4040   return (SCALAR_TYPE_P (t) || VECTOR_TYPE_P (t));
4041 }
4042
4043 /* Returns true iff T requires non-trivial default initialization.  */
4044
4045 bool
4046 type_has_nontrivial_default_init (const_tree t)
4047 {
4048   t = strip_array_types (CONST_CAST_TREE (t));
4049
4050   if (CLASS_TYPE_P (t))
4051     return TYPE_HAS_COMPLEX_DFLT (t);
4052   else
4053     return 0;
4054 }
4055
4056 /* Track classes with only deleted copy/move constructors so that we can warn
4057    if they are used in call/return by value.  */
4058
4059 static GTY(()) hash_set<tree>* deleted_copy_types;
4060 static void
4061 remember_deleted_copy (const_tree t)
4062 {
4063   if (!deleted_copy_types)
4064     deleted_copy_types = hash_set<tree>::create_ggc(37);
4065   deleted_copy_types->add (CONST_CAST_TREE (t));
4066 }
4067 void
4068 maybe_warn_parm_abi (tree t, location_t loc)
4069 {
4070   if (!deleted_copy_types
4071       || !deleted_copy_types->contains (t))
4072     return;
4073
4074   if ((flag_abi_version == 12 || warn_abi_version == 12)
4075       && classtype_has_non_deleted_move_ctor (t))
4076     {
4077       if (flag_abi_version > 12)
4078         warning_at (loc, OPT_Wabi, "-fabi-version=13 (GCC 8.2) fixes the "
4079                     "calling convention for %qT, which was accidentally "
4080                     "changed in 8.1", t);
4081       else
4082         warning_at (loc, OPT_Wabi, "-fabi-version=12 (GCC 8.1) accidentally "
4083                     "changes the calling convention for %qT", t);
4084       return;
4085     }
4086
4087   warning_at (loc, OPT_Wabi, "the calling convention for %qT changes in "
4088               "-fabi-version=13 (GCC 8.2)", t);
4089   static bool explained = false;
4090   if (!explained)
4091     {
4092       inform (loc, " because all of its copy and move constructors "
4093               "are deleted");
4094       explained = true;
4095     }
4096 }
4097
4098 /* Returns true iff copying an object of type T (including via move
4099    constructor) is non-trivial.  That is, T has no non-trivial copy
4100    constructors and no non-trivial move constructors, and not all copy/move
4101    constructors are deleted.  This function implements the ABI notion of
4102    non-trivial copy, which has diverged from the one in the standard.  */
4103
4104 bool
4105 type_has_nontrivial_copy_init (const_tree type)
4106 {
4107   tree t = strip_array_types (CONST_CAST_TREE (type));
4108
4109   if (CLASS_TYPE_P (t))
4110     {
4111       gcc_assert (COMPLETE_TYPE_P (t));
4112
4113       if (TYPE_HAS_COMPLEX_COPY_CTOR (t)
4114           || TYPE_HAS_COMPLEX_MOVE_CTOR (t))
4115         /* Nontrivial.  */
4116         return true;
4117
4118       if (cxx_dialect < cxx11)
4119         /* No deleted functions before C++11.  */
4120         return false;
4121
4122       /* Before ABI v12 we did a bitwise copy of types with only deleted
4123          copy/move constructors.  */
4124       if (!abi_version_at_least (12)
4125           && !(warn_abi && abi_version_crosses (12)))
4126         return false;
4127
4128       bool saw_copy = false;
4129       bool saw_non_deleted = false;
4130       bool saw_non_deleted_move = false;
4131
4132       if (CLASSTYPE_LAZY_MOVE_CTOR (t))
4133         saw_copy = saw_non_deleted = true;
4134       else if (CLASSTYPE_LAZY_COPY_CTOR (t))
4135         {
4136           saw_copy = true;
4137           if (classtype_has_move_assign_or_move_ctor_p (t, true))
4138             /* [class.copy]/8 If the class definition declares a move
4139                constructor or move assignment operator, the implicitly declared
4140                copy constructor is defined as deleted.... */;
4141           else
4142             /* Any other reason the implicitly-declared function would be
4143                deleted would also cause TYPE_HAS_COMPLEX_COPY_CTOR to be
4144                set.  */
4145             saw_non_deleted = true;
4146         }
4147
4148       if (!saw_non_deleted)
4149         for (ovl_iterator iter (CLASSTYPE_CONSTRUCTORS (t)); iter; ++iter)
4150           {
4151             tree fn = *iter;
4152             if (copy_fn_p (fn))
4153               {
4154                 saw_copy = true;
4155                 if (!DECL_DELETED_FN (fn))
4156                   {
4157                     /* Not deleted, therefore trivial.  */
4158                     saw_non_deleted = true;
4159                     break;
4160                   }
4161               }
4162             else if (move_fn_p (fn))
4163               if (!DECL_DELETED_FN (fn))
4164                 saw_non_deleted_move = true;
4165           }
4166
4167       gcc_assert (saw_copy);
4168
4169       /* ABI v12 buggily ignored move constructors.  */
4170       bool v11nontriv = false;
4171       bool v12nontriv = !saw_non_deleted;
4172       bool v13nontriv = !saw_non_deleted && !saw_non_deleted_move;
4173       bool nontriv = (abi_version_at_least (13) ? v13nontriv
4174                       : flag_abi_version == 12 ? v12nontriv
4175                       : v11nontriv);
4176       bool warn_nontriv = (warn_abi_version >= 13 ? v13nontriv
4177                            : warn_abi_version == 12 ? v12nontriv
4178                            : v11nontriv);
4179       if (nontriv != warn_nontriv)
4180         remember_deleted_copy (t);
4181
4182       return nontriv;
4183     }
4184   else
4185     return 0;
4186 }
4187
4188 /* Returns 1 iff type T is a trivially copyable type, as defined in
4189    [basic.types] and [class].  */
4190
4191 bool
4192 trivially_copyable_p (const_tree t)
4193 {
4194   t = strip_array_types (CONST_CAST_TREE (t));
4195
4196   if (CLASS_TYPE_P (t))
4197     return ((!TYPE_HAS_COPY_CTOR (t)
4198              || !TYPE_HAS_COMPLEX_COPY_CTOR (t))
4199             && !TYPE_HAS_COMPLEX_MOVE_CTOR (t)
4200             && (!TYPE_HAS_COPY_ASSIGN (t)
4201                 || !TYPE_HAS_COMPLEX_COPY_ASSIGN (t))
4202             && !TYPE_HAS_COMPLEX_MOVE_ASSIGN (t)
4203             && TYPE_HAS_TRIVIAL_DESTRUCTOR (t));
4204   else
4205     return !CP_TYPE_VOLATILE_P (t) && scalarish_type_p (t);
4206 }
4207
4208 /* Returns 1 iff type T is a trivial type, as defined in [basic.types] and
4209    [class].  */
4210
4211 bool
4212 trivial_type_p (const_tree t)
4213 {
4214   t = strip_array_types (CONST_CAST_TREE (t));
4215
4216   if (CLASS_TYPE_P (t))
4217     return (TYPE_HAS_TRIVIAL_DFLT (t)
4218             && trivially_copyable_p (t));
4219   else
4220     return scalarish_type_p (t);
4221 }
4222
4223 /* Returns 1 iff type T is a POD type, as defined in [basic.types].  */
4224
4225 bool
4226 pod_type_p (const_tree t)
4227 {
4228   /* This CONST_CAST is okay because strip_array_types returns its
4229      argument unmodified and we assign it to a const_tree.  */
4230   t = strip_array_types (CONST_CAST_TREE(t));
4231
4232   if (!CLASS_TYPE_P (t))
4233     return scalarish_type_p (t);
4234   else if (cxx_dialect > cxx98)
4235     /* [class]/10: A POD struct is a class that is both a trivial class and a
4236        standard-layout class, and has no non-static data members of type
4237        non-POD struct, non-POD union (or array of such types).
4238
4239        We don't need to check individual members because if a member is
4240        non-std-layout or non-trivial, the class will be too.  */
4241     return (std_layout_type_p (t) && trivial_type_p (t));
4242   else
4243     /* The C++98 definition of POD is different.  */
4244     return !CLASSTYPE_NON_LAYOUT_POD_P (t);
4245 }
4246
4247 /* Returns true iff T is POD for the purpose of layout, as defined in the
4248    C++ ABI.  */
4249
4250 bool
4251 layout_pod_type_p (const_tree t)
4252 {
4253   t = strip_array_types (CONST_CAST_TREE (t));
4254
4255   if (CLASS_TYPE_P (t))
4256     return !CLASSTYPE_NON_LAYOUT_POD_P (t);
4257   else
4258     return scalarish_type_p (t);
4259 }
4260
4261 /* Returns true iff T is a standard-layout type, as defined in
4262    [basic.types].  */
4263
4264 bool
4265 std_layout_type_p (const_tree t)
4266 {
4267   t = strip_array_types (CONST_CAST_TREE (t));
4268
4269   if (CLASS_TYPE_P (t))
4270     return !CLASSTYPE_NON_STD_LAYOUT (t);
4271   else
4272     return scalarish_type_p (t);
4273 }
4274
4275 static bool record_has_unique_obj_representations (const_tree, const_tree);
4276
4277 /* Returns true iff T satisfies std::has_unique_object_representations<T>,
4278    as defined in [meta.unary.prop].  */
4279
4280 bool
4281 type_has_unique_obj_representations (const_tree t)
4282 {
4283   bool ret;
4284
4285   t = strip_array_types (CONST_CAST_TREE (t));
4286
4287   if (!trivially_copyable_p (t))
4288     return false;
4289
4290   if (CLASS_TYPE_P (t) && CLASSTYPE_UNIQUE_OBJ_REPRESENTATIONS_SET (t))
4291     return CLASSTYPE_UNIQUE_OBJ_REPRESENTATIONS (t);
4292
4293   switch (TREE_CODE (t))
4294     {
4295     case INTEGER_TYPE:
4296     case POINTER_TYPE:
4297     case REFERENCE_TYPE:
4298       /* If some backend has any paddings in these types, we should add
4299          a target hook for this and handle it there.  */
4300       return true;
4301
4302     case BOOLEAN_TYPE:
4303       /* For bool values other than 0 and 1 should only appear with
4304          undefined behavior.  */
4305       return true;
4306
4307     case ENUMERAL_TYPE:
4308       return type_has_unique_obj_representations (ENUM_UNDERLYING_TYPE (t));
4309
4310     case REAL_TYPE:
4311       /* XFmode certainly contains padding on x86, which the CPU doesn't store
4312          when storing long double values, so for that we have to return false.
4313          Other kinds of floating point values are questionable due to +.0/-.0
4314          and NaNs, let's play safe for now.  */
4315       return false;
4316
4317     case FIXED_POINT_TYPE:
4318       return false;
4319
4320     case OFFSET_TYPE:
4321       return true;
4322
4323     case COMPLEX_TYPE:
4324     case VECTOR_TYPE:
4325       return type_has_unique_obj_representations (TREE_TYPE (t));
4326
4327     case RECORD_TYPE:
4328       ret = record_has_unique_obj_representations (t, TYPE_SIZE (t));
4329       if (CLASS_TYPE_P (t))
4330         {
4331           CLASSTYPE_UNIQUE_OBJ_REPRESENTATIONS_SET (t) = 1;
4332           CLASSTYPE_UNIQUE_OBJ_REPRESENTATIONS (t) = ret;
4333         }
4334       return ret;
4335
4336     case UNION_TYPE:
4337       ret = true;
4338       bool any_fields;
4339       any_fields = false;
4340       for (tree field = TYPE_FIELDS (t); field; field = DECL_CHAIN (field))
4341         if (TREE_CODE (field) == FIELD_DECL)
4342           {
4343             any_fields = true;
4344             if (!type_has_unique_obj_representations (TREE_TYPE (field))
4345                 || simple_cst_equal (DECL_SIZE (field), TYPE_SIZE (t)) != 1)
4346               {
4347                 ret = false;
4348                 break;
4349               }
4350           }
4351       if (!any_fields && !integer_zerop (TYPE_SIZE (t)))
4352         ret = false;
4353       if (CLASS_TYPE_P (t))
4354         {
4355           CLASSTYPE_UNIQUE_OBJ_REPRESENTATIONS_SET (t) = 1;
4356           CLASSTYPE_UNIQUE_OBJ_REPRESENTATIONS (t) = ret;
4357         }
4358       return ret;
4359
4360     case NULLPTR_TYPE:
4361       return false;
4362
4363     case ERROR_MARK:
4364       return false;
4365
4366     default:
4367       gcc_unreachable ();
4368     }
4369 }
4370
4371 /* Helper function for type_has_unique_obj_representations.  */
4372
4373 static bool
4374 record_has_unique_obj_representations (const_tree t, const_tree sz)
4375 {
4376   for (tree field = TYPE_FIELDS (t); field; field = DECL_CHAIN (field))
4377     if (TREE_CODE (field) != FIELD_DECL)
4378       ;
4379     /* For bases, can't use type_has_unique_obj_representations here, as in
4380         struct S { int i : 24; S (); };
4381         struct T : public S { int j : 8; T (); };
4382         S doesn't have unique obj representations, but T does.  */
4383     else if (DECL_FIELD_IS_BASE (field))
4384       {
4385         if (!record_has_unique_obj_representations (TREE_TYPE (field),
4386                                                     DECL_SIZE (field)))
4387           return false;
4388       }
4389     else if (DECL_C_BIT_FIELD (field))
4390       {
4391         tree btype = DECL_BIT_FIELD_TYPE (field);
4392         if (!type_has_unique_obj_representations (btype))
4393           return false;
4394       }
4395     else if (!type_has_unique_obj_representations (TREE_TYPE (field)))
4396       return false;
4397
4398   offset_int cur = 0;
4399   for (tree field = TYPE_FIELDS (t); field; field = DECL_CHAIN (field))
4400     if (TREE_CODE (field) == FIELD_DECL)
4401       {
4402         offset_int fld = wi::to_offset (DECL_FIELD_OFFSET (field));
4403         offset_int bitpos = wi::to_offset (DECL_FIELD_BIT_OFFSET (field));
4404         fld = fld * BITS_PER_UNIT + bitpos;
4405         if (cur != fld)
4406           return false;
4407         if (DECL_SIZE (field))
4408           {
4409             offset_int size = wi::to_offset (DECL_SIZE (field));
4410             cur += size;
4411           }
4412       }
4413   if (cur != wi::to_offset (sz))
4414     return false;
4415
4416   return true;
4417 }
4418
4419 /* Nonzero iff type T is a class template implicit specialization.  */
4420
4421 bool
4422 class_tmpl_impl_spec_p (const_tree t)
4423 {
4424   return CLASS_TYPE_P (t) && CLASSTYPE_TEMPLATE_INSTANTIATION (t);
4425 }
4426
4427 /* Returns 1 iff zero initialization of type T means actually storing
4428    zeros in it.  */
4429
4430 int
4431 zero_init_p (const_tree t)
4432 {
4433   /* This CONST_CAST is okay because strip_array_types returns its
4434      argument unmodified and we assign it to a const_tree.  */
4435   t = strip_array_types (CONST_CAST_TREE(t));
4436
4437   if (t == error_mark_node)
4438     return 1;
4439
4440   /* NULL pointers to data members are initialized with -1.  */
4441   if (TYPE_PTRDATAMEM_P (t))
4442     return 0;
4443
4444   /* Classes that contain types that can't be zero-initialized, cannot
4445      be zero-initialized themselves.  */
4446   if (CLASS_TYPE_P (t) && CLASSTYPE_NON_ZERO_INIT_P (t))
4447     return 0;
4448
4449   return 1;
4450 }
4451
4452 /* Handle the C++17 [[nodiscard]] attribute, which is similar to the GNU
4453    warn_unused_result attribute.  */
4454
4455 static tree
4456 handle_nodiscard_attribute (tree *node, tree name, tree /*args*/,
4457                             int /*flags*/, bool *no_add_attrs)
4458 {
4459   if (TREE_CODE (*node) == FUNCTION_DECL)
4460     {
4461       if (VOID_TYPE_P (TREE_TYPE (TREE_TYPE (*node))))
4462         warning (OPT_Wattributes, "%qE attribute applied to %qD with void "
4463                  "return type", name, *node);
4464     }
4465   else if (OVERLOAD_TYPE_P (*node))
4466     /* OK */;
4467   else
4468     {
4469       warning (OPT_Wattributes, "%qE attribute can only be applied to "
4470                "functions or to class or enumeration types", name);
4471       *no_add_attrs = true;
4472     }
4473   return NULL_TREE;
4474 }
4475
4476 /* Table of valid C++ attributes.  */
4477 const struct attribute_spec cxx_attribute_table[] =
4478 {
4479   /* { name, min_len, max_len, decl_req, type_req, fn_type_req,
4480        affects_type_identity, handler, exclude } */
4481   { "init_priority",  1, 1, true,  false, false, false,
4482     handle_init_priority_attribute, NULL },
4483   { "abi_tag", 1, -1, false, false, false, true,
4484     handle_abi_tag_attribute, NULL },
4485   { NULL, 0, 0, false, false, false, false, NULL, NULL }
4486 };
4487
4488 /* Table of C++ standard attributes.  */
4489 const struct attribute_spec std_attribute_table[] =
4490 {
4491   /* { name, min_len, max_len, decl_req, type_req, fn_type_req,
4492        affects_type_identity, handler, exclude } */
4493   { "maybe_unused", 0, 0, false, false, false, false,
4494     handle_unused_attribute, NULL },
4495   { "nodiscard", 0, 0, false, false, false, false,
4496     handle_nodiscard_attribute, NULL },
4497   { NULL, 0, 0, false, false, false, false, NULL, NULL }
4498 };
4499
4500 /* Handle an "init_priority" attribute; arguments as in
4501    struct attribute_spec.handler.  */
4502 static tree
4503 handle_init_priority_attribute (tree* node,
4504                                 tree name,
4505                                 tree args,
4506                                 int /*flags*/,
4507                                 bool* no_add_attrs)
4508 {
4509   tree initp_expr = TREE_VALUE (args);
4510   tree decl = *node;
4511   tree type = TREE_TYPE (decl);
4512   int pri;
4513
4514   STRIP_NOPS (initp_expr);
4515   initp_expr = default_conversion (initp_expr);
4516   if (initp_expr)
4517     initp_expr = maybe_constant_value (initp_expr);
4518
4519   if (!initp_expr || TREE_CODE (initp_expr) != INTEGER_CST)
4520     {
4521       error ("requested init_priority is not an integer constant");
4522       cxx_constant_value (initp_expr);
4523       *no_add_attrs = true;
4524       return NULL_TREE;
4525     }
4526
4527   pri = TREE_INT_CST_LOW (initp_expr);
4528
4529   type = strip_array_types (type);
4530
4531   if (decl == NULL_TREE
4532       || !VAR_P (decl)
4533       || !TREE_STATIC (decl)
4534       || DECL_EXTERNAL (decl)
4535       || (TREE_CODE (type) != RECORD_TYPE
4536           && TREE_CODE (type) != UNION_TYPE)
4537       /* Static objects in functions are initialized the
4538          first time control passes through that
4539          function. This is not precise enough to pin down an
4540          init_priority value, so don't allow it.  */
4541       || current_function_decl)
4542     {
4543       error ("can only use %qE attribute on file-scope definitions "
4544              "of objects of class type", name);
4545       *no_add_attrs = true;
4546       return NULL_TREE;
4547     }
4548
4549   if (pri > MAX_INIT_PRIORITY || pri <= 0)
4550     {
4551       error ("requested init_priority is out of range");
4552       *no_add_attrs = true;
4553       return NULL_TREE;
4554     }
4555
4556   /* Check for init_priorities that are reserved for
4557      language and runtime support implementations.*/
4558   if (pri <= MAX_RESERVED_INIT_PRIORITY)
4559     {
4560       warning
4561         (0, "requested init_priority is reserved for internal use");
4562     }
4563
4564   if (SUPPORTS_INIT_PRIORITY)
4565     {
4566       SET_DECL_INIT_PRIORITY (decl, pri);
4567       DECL_HAS_INIT_PRIORITY_P (decl) = 1;
4568       return NULL_TREE;
4569     }
4570   else
4571     {
4572       error ("%qE attribute is not supported on this platform", name);
4573       *no_add_attrs = true;
4574       return NULL_TREE;
4575     }
4576 }
4577
4578 /* DECL is being redeclared; the old declaration had the abi tags in OLD,
4579    and the new one has the tags in NEW_.  Give an error if there are tags
4580    in NEW_ that weren't in OLD.  */
4581
4582 bool
4583 check_abi_tag_redeclaration (const_tree decl, const_tree old, const_tree new_)
4584 {
4585   if (old && TREE_CODE (TREE_VALUE (old)) == TREE_LIST)
4586     old = TREE_VALUE (old);
4587   if (new_ && TREE_CODE (TREE_VALUE (new_)) == TREE_LIST)
4588     new_ = TREE_VALUE (new_);
4589   bool err = false;
4590   for (const_tree t = new_; t; t = TREE_CHAIN (t))
4591     {
4592       tree str = TREE_VALUE (t);
4593       for (const_tree in = old; in; in = TREE_CHAIN (in))
4594         {
4595           tree ostr = TREE_VALUE (in);
4596           if (cp_tree_equal (str, ostr))
4597             goto found;
4598         }
4599       error ("redeclaration of %qD adds abi tag %qE", decl, str);
4600       err = true;
4601     found:;
4602     }
4603   if (err)
4604     {
4605       inform (DECL_SOURCE_LOCATION (decl), "previous declaration here");
4606       return false;
4607     }
4608   return true;
4609 }
4610
4611 /* The abi_tag attribute with the name NAME was given ARGS.  If they are
4612    ill-formed, give an error and return false; otherwise, return true.  */
4613
4614 bool
4615 check_abi_tag_args (tree args, tree name)
4616 {
4617   if (!args)
4618     {
4619       error ("the %qE attribute requires arguments", name);
4620       return false;
4621     }
4622   for (tree arg = args; arg; arg = TREE_CHAIN (arg))
4623     {
4624       tree elt = TREE_VALUE (arg);
4625       if (TREE_CODE (elt) != STRING_CST
4626           || (!same_type_ignoring_top_level_qualifiers_p
4627               (strip_array_types (TREE_TYPE (elt)),
4628                char_type_node)))
4629         {
4630           error ("arguments to the %qE attribute must be narrow string "
4631                  "literals", name);
4632           return false;
4633         }
4634       const char *begin = TREE_STRING_POINTER (elt);
4635       const char *end = begin + TREE_STRING_LENGTH (elt);
4636       for (const char *p = begin; p != end; ++p)
4637         {
4638           char c = *p;
4639           if (p == begin)
4640             {
4641               if (!ISALPHA (c) && c != '_')
4642                 {
4643                   error ("arguments to the %qE attribute must contain valid "
4644                          "identifiers", name);
4645                   inform (input_location, "%<%c%> is not a valid first "
4646                           "character for an identifier", c);
4647                   return false;
4648                 }
4649             }
4650           else if (p == end - 1)
4651             gcc_assert (c == 0);
4652           else
4653             {
4654               if (!ISALNUM (c) && c != '_')
4655                 {
4656                   error ("arguments to the %qE attribute must contain valid "
4657                          "identifiers", name);
4658                   inform (input_location, "%<%c%> is not a valid character "
4659                           "in an identifier", c);
4660                   return false;
4661                 }
4662             }
4663         }
4664     }
4665   return true;
4666 }
4667
4668 /* Handle an "abi_tag" attribute; arguments as in
4669    struct attribute_spec.handler.  */
4670
4671 static tree
4672 handle_abi_tag_attribute (tree* node, tree name, tree args,
4673                           int flags, bool* no_add_attrs)
4674 {
4675   if (!check_abi_tag_args (args, name))
4676     goto fail;
4677
4678   if (TYPE_P (*node))
4679     {
4680       if (!OVERLOAD_TYPE_P (*node))
4681         {
4682           error ("%qE attribute applied to non-class, non-enum type %qT",
4683                  name, *node);
4684           goto fail;
4685         }
4686       else if (!(flags & (int)ATTR_FLAG_TYPE_IN_PLACE))
4687         {
4688           error ("%qE attribute applied to %qT after its definition",
4689                  name, *node);
4690           goto fail;
4691         }
4692       else if (CLASS_TYPE_P (*node)
4693                && CLASSTYPE_TEMPLATE_INSTANTIATION (*node))
4694         {
4695           warning (OPT_Wattributes, "ignoring %qE attribute applied to "
4696                    "template instantiation %qT", name, *node);
4697           goto fail;
4698         }
4699       else if (CLASS_TYPE_P (*node)
4700                && CLASSTYPE_TEMPLATE_SPECIALIZATION (*node))
4701         {
4702           warning (OPT_Wattributes, "ignoring %qE attribute applied to "
4703                    "template specialization %qT", name, *node);
4704           goto fail;
4705         }
4706
4707       tree attributes = TYPE_ATTRIBUTES (*node);
4708       tree decl = TYPE_NAME (*node);
4709
4710       /* Make sure all declarations have the same abi tags.  */
4711       if (DECL_SOURCE_LOCATION (decl) != input_location)
4712         {
4713           if (!check_abi_tag_redeclaration (decl,
4714                                             lookup_attribute ("abi_tag",
4715                                                               attributes),
4716                                             args))
4717             goto fail;
4718         }
4719     }
4720   else
4721     {
4722       if (!VAR_OR_FUNCTION_DECL_P (*node))
4723         {
4724           error ("%qE attribute applied to non-function, non-variable %qD",
4725                  name, *node);
4726           goto fail;
4727         }
4728       else if (DECL_LANGUAGE (*node) == lang_c)
4729         {
4730           error ("%qE attribute applied to extern \"C\" declaration %qD",
4731                  name, *node);
4732           goto fail;
4733         }
4734     }
4735
4736   return NULL_TREE;
4737
4738  fail:
4739   *no_add_attrs = true;
4740   return NULL_TREE;
4741 }
4742
4743 /* Return a new PTRMEM_CST of the indicated TYPE.  The MEMBER is the
4744    thing pointed to by the constant.  */
4745
4746 tree
4747 make_ptrmem_cst (tree type, tree member)
4748 {
4749   tree ptrmem_cst = make_node (PTRMEM_CST);
4750   TREE_TYPE (ptrmem_cst) = type;
4751   PTRMEM_CST_MEMBER (ptrmem_cst) = member;
4752   return ptrmem_cst;
4753 }
4754
4755 /* Build a variant of TYPE that has the indicated ATTRIBUTES.  May
4756    return an existing type if an appropriate type already exists.  */
4757
4758 tree
4759 cp_build_type_attribute_variant (tree type, tree attributes)
4760 {
4761   tree new_type;
4762
4763   new_type = build_type_attribute_variant (type, attributes);
4764   if (TREE_CODE (new_type) == FUNCTION_TYPE
4765       || TREE_CODE (new_type) == METHOD_TYPE)
4766     gcc_checking_assert (cxx_type_hash_eq (type, new_type));
4767
4768   /* Making a new main variant of a class type is broken.  */
4769   gcc_assert (!CLASS_TYPE_P (type) || new_type == type);
4770
4771   return new_type;
4772 }
4773
4774 /* Return TRUE if TYPE1 and TYPE2 are identical for type hashing purposes.
4775    Called only after doing all language independent checks.  */
4776
4777 bool
4778 cxx_type_hash_eq (const_tree typea, const_tree typeb)
4779 {
4780   gcc_assert (TREE_CODE (typea) == FUNCTION_TYPE
4781               || TREE_CODE (typea) == METHOD_TYPE);
4782
4783   if (type_memfn_rqual (typea) != type_memfn_rqual (typeb))
4784     return false;
4785   if (TYPE_HAS_LATE_RETURN_TYPE (typea) != TYPE_HAS_LATE_RETURN_TYPE (typeb))
4786     return false;
4787   return comp_except_specs (TYPE_RAISES_EXCEPTIONS (typea),
4788                             TYPE_RAISES_EXCEPTIONS (typeb), ce_exact);
4789 }
4790
4791 /* Copy the language-specific type variant modifiers from TYPEB to TYPEA.  For
4792    C++, these are the exception-specifier and ref-qualifier.  */
4793
4794 tree
4795 cxx_copy_lang_qualifiers (const_tree typea, const_tree typeb)
4796 {
4797   tree type = CONST_CAST_TREE (typea);
4798   if (TREE_CODE (type) == FUNCTION_TYPE || TREE_CODE (type) == METHOD_TYPE)
4799     type = build_cp_fntype_variant (type, type_memfn_rqual (typeb),
4800                                     TYPE_RAISES_EXCEPTIONS (typeb),
4801                                     TYPE_HAS_LATE_RETURN_TYPE (typeb));
4802   return type;
4803 }
4804
4805 /* Apply FUNC to all language-specific sub-trees of TP in a pre-order
4806    traversal.  Called from walk_tree.  */
4807
4808 tree
4809 cp_walk_subtrees (tree *tp, int *walk_subtrees_p, walk_tree_fn func,
4810                   void *data, hash_set<tree> *pset)
4811 {
4812   enum tree_code code = TREE_CODE (*tp);
4813   tree result;
4814
4815 #define WALK_SUBTREE(NODE)                              \
4816   do                                                    \
4817     {                                                   \
4818       result = cp_walk_tree (&(NODE), func, data, pset);        \
4819       if (result) goto out;                             \
4820     }                                                   \
4821   while (0)
4822
4823   /* Not one of the easy cases.  We must explicitly go through the
4824      children.  */
4825   result = NULL_TREE;
4826   switch (code)
4827     {
4828     case DEFAULT_ARG:
4829     case TEMPLATE_TEMPLATE_PARM:
4830     case BOUND_TEMPLATE_TEMPLATE_PARM:
4831     case UNBOUND_CLASS_TEMPLATE:
4832     case TEMPLATE_PARM_INDEX:
4833     case TEMPLATE_TYPE_PARM:
4834     case TYPENAME_TYPE:
4835     case TYPEOF_TYPE:
4836     case UNDERLYING_TYPE:
4837       /* None of these have subtrees other than those already walked
4838          above.  */
4839       *walk_subtrees_p = 0;
4840       break;
4841
4842     case BASELINK:
4843       if (BASELINK_QUALIFIED_P (*tp))
4844         WALK_SUBTREE (BINFO_TYPE (BASELINK_ACCESS_BINFO (*tp)));
4845       WALK_SUBTREE (BASELINK_FUNCTIONS (*tp));
4846       *walk_subtrees_p = 0;
4847       break;
4848
4849     case PTRMEM_CST:
4850       WALK_SUBTREE (TREE_TYPE (*tp));
4851       *walk_subtrees_p = 0;
4852       break;
4853
4854     case TREE_LIST:
4855       WALK_SUBTREE (TREE_PURPOSE (*tp));
4856       break;
4857
4858     case OVERLOAD:
4859       WALK_SUBTREE (OVL_FUNCTION (*tp));
4860       WALK_SUBTREE (OVL_CHAIN (*tp));
4861       *walk_subtrees_p = 0;
4862       break;
4863
4864     case USING_DECL:
4865       WALK_SUBTREE (DECL_NAME (*tp));
4866       WALK_SUBTREE (USING_DECL_SCOPE (*tp));
4867       WALK_SUBTREE (USING_DECL_DECLS (*tp));
4868       *walk_subtrees_p = 0;
4869       break;
4870
4871     case RECORD_TYPE:
4872       if (TYPE_PTRMEMFUNC_P (*tp))
4873         WALK_SUBTREE (TYPE_PTRMEMFUNC_FN_TYPE_RAW (*tp));
4874       break;
4875
4876     case TYPE_ARGUMENT_PACK:
4877     case NONTYPE_ARGUMENT_PACK:
4878       {
4879         tree args = ARGUMENT_PACK_ARGS (*tp);
4880         int i, len = TREE_VEC_LENGTH (args);
4881         for (i = 0; i < len; i++)
4882           WALK_SUBTREE (TREE_VEC_ELT (args, i));
4883       }
4884       break;
4885
4886     case TYPE_PACK_EXPANSION:
4887       WALK_SUBTREE (TREE_TYPE (*tp));
4888       WALK_SUBTREE (PACK_EXPANSION_EXTRA_ARGS (*tp));
4889       *walk_subtrees_p = 0;
4890       break;
4891
4892     case EXPR_PACK_EXPANSION:
4893       WALK_SUBTREE (TREE_OPERAND (*tp, 0));
4894       WALK_SUBTREE (PACK_EXPANSION_EXTRA_ARGS (*tp));
4895       *walk_subtrees_p = 0;
4896       break;
4897
4898     case CAST_EXPR:
4899     case REINTERPRET_CAST_EXPR:
4900     case STATIC_CAST_EXPR:
4901     case CONST_CAST_EXPR:
4902     case DYNAMIC_CAST_EXPR:
4903     case IMPLICIT_CONV_EXPR:
4904       if (TREE_TYPE (*tp))
4905         WALK_SUBTREE (TREE_TYPE (*tp));
4906
4907       {
4908         int i;
4909         for (i = 0; i < TREE_CODE_LENGTH (TREE_CODE (*tp)); ++i)
4910           WALK_SUBTREE (TREE_OPERAND (*tp, i));
4911       }
4912       *walk_subtrees_p = 0;
4913       break;
4914
4915     case TRAIT_EXPR:
4916       WALK_SUBTREE (TRAIT_EXPR_TYPE1 (*tp));
4917       WALK_SUBTREE (TRAIT_EXPR_TYPE2 (*tp));
4918       *walk_subtrees_p = 0;
4919       break;
4920
4921     case DECLTYPE_TYPE:
4922       WALK_SUBTREE (DECLTYPE_TYPE_EXPR (*tp));
4923       *walk_subtrees_p = 0;
4924       break;
4925
4926     case REQUIRES_EXPR:
4927       // Only recurse through the nested expression. Do not
4928       // walk the parameter list. Doing so causes false
4929       // positives in the pack expansion checker since the
4930       // requires parameters are introduced as pack expansions.
4931       WALK_SUBTREE (TREE_OPERAND (*tp, 1));
4932       *walk_subtrees_p = 0;
4933       break;
4934
4935     case DECL_EXPR:
4936       /* User variables should be mentioned in BIND_EXPR_VARS
4937          and their initializers and sizes walked when walking
4938          the containing BIND_EXPR.  Compiler temporaries are
4939          handled here.  And also normal variables in templates,
4940          since do_poplevel doesn't build a BIND_EXPR then.  */
4941       if (VAR_P (TREE_OPERAND (*tp, 0))
4942           && (processing_template_decl
4943               || (DECL_ARTIFICIAL (TREE_OPERAND (*tp, 0))
4944                   && !TREE_STATIC (TREE_OPERAND (*tp, 0)))))
4945         {
4946           tree decl = TREE_OPERAND (*tp, 0);
4947           WALK_SUBTREE (DECL_INITIAL (decl));
4948           WALK_SUBTREE (DECL_SIZE (decl));
4949           WALK_SUBTREE (DECL_SIZE_UNIT (decl));
4950         }
4951       break;
4952
4953     default:
4954       return NULL_TREE;
4955     }
4956
4957   /* We didn't find what we were looking for.  */
4958  out:
4959   return result;
4960
4961 #undef WALK_SUBTREE
4962 }
4963
4964 /* Like save_expr, but for C++.  */
4965
4966 tree
4967 cp_save_expr (tree expr)
4968 {
4969   /* There is no reason to create a SAVE_EXPR within a template; if
4970      needed, we can create the SAVE_EXPR when instantiating the
4971      template.  Furthermore, the middle-end cannot handle C++-specific
4972      tree codes.  */
4973   if (processing_template_decl)
4974     return expr;
4975   return save_expr (expr);
4976 }
4977
4978 /* Initialize tree.c.  */
4979
4980 void
4981 init_tree (void)
4982 {
4983   list_hash_table = hash_table<list_hasher>::create_ggc (61);
4984   register_scoped_attributes (std_attribute_table, NULL);
4985 }
4986
4987 /* Returns the kind of special function that DECL (a FUNCTION_DECL)
4988    is.  Note that sfk_none is zero, so this function can be used as a
4989    predicate to test whether or not DECL is a special function.  */
4990
4991 special_function_kind
4992 special_function_p (const_tree decl)
4993 {
4994   /* Rather than doing all this stuff with magic names, we should
4995      probably have a field of type `special_function_kind' in
4996      DECL_LANG_SPECIFIC.  */
4997   if (DECL_INHERITED_CTOR (decl))
4998     return sfk_inheriting_constructor;
4999   if (DECL_COPY_CONSTRUCTOR_P (decl))
5000     return sfk_copy_constructor;
5001   if (DECL_MOVE_CONSTRUCTOR_P (decl))
5002     return sfk_move_constructor;
5003   if (DECL_CONSTRUCTOR_P (decl))
5004     return sfk_constructor;
5005   if (DECL_ASSIGNMENT_OPERATOR_P (decl)
5006       && DECL_OVERLOADED_OPERATOR_IS (decl, NOP_EXPR))
5007     {
5008       if (copy_fn_p (decl))
5009         return sfk_copy_assignment;
5010       if (move_fn_p (decl))
5011         return sfk_move_assignment;
5012     }
5013   if (DECL_MAYBE_IN_CHARGE_DESTRUCTOR_P (decl))
5014     return sfk_destructor;
5015   if (DECL_COMPLETE_DESTRUCTOR_P (decl))
5016     return sfk_complete_destructor;
5017   if (DECL_BASE_DESTRUCTOR_P (decl))
5018     return sfk_base_destructor;
5019   if (DECL_DELETING_DESTRUCTOR_P (decl))
5020     return sfk_deleting_destructor;
5021   if (DECL_CONV_FN_P (decl))
5022     return sfk_conversion;
5023   if (deduction_guide_p (decl))
5024     return sfk_deduction_guide;
5025
5026   return sfk_none;
5027 }
5028
5029 /* Returns nonzero if TYPE is a character type, including wchar_t.  */
5030
5031 int
5032 char_type_p (tree type)
5033 {
5034   return (same_type_p (type, char_type_node)
5035           || same_type_p (type, unsigned_char_type_node)
5036           || same_type_p (type, signed_char_type_node)
5037           || same_type_p (type, char16_type_node)
5038           || same_type_p (type, char32_type_node)
5039           || same_type_p (type, wchar_type_node));
5040 }
5041
5042 /* Returns the kind of linkage associated with the indicated DECL.  Th
5043    value returned is as specified by the language standard; it is
5044    independent of implementation details regarding template
5045    instantiation, etc.  For example, it is possible that a declaration
5046    to which this function assigns external linkage would not show up
5047    as a global symbol when you run `nm' on the resulting object file.  */
5048
5049 linkage_kind
5050 decl_linkage (tree decl)
5051 {
5052   /* This function doesn't attempt to calculate the linkage from first
5053      principles as given in [basic.link].  Instead, it makes use of
5054      the fact that we have already set TREE_PUBLIC appropriately, and
5055      then handles a few special cases.  Ideally, we would calculate
5056      linkage first, and then transform that into a concrete
5057      implementation.  */
5058
5059   /* Things that don't have names have no linkage.  */
5060   if (!DECL_NAME (decl))
5061     return lk_none;
5062
5063   /* Fields have no linkage.  */
5064   if (TREE_CODE (decl) == FIELD_DECL)
5065     return lk_none;
5066
5067   /* Things that are TREE_PUBLIC have external linkage.  */
5068   if (TREE_PUBLIC (decl))
5069     return lk_external;
5070
5071   /* maybe_thunk_body clears TREE_PUBLIC on the maybe-in-charge 'tor variants,
5072      check one of the "clones" for the real linkage.  */
5073   if (DECL_MAYBE_IN_CHARGE_CDTOR_P (decl)
5074       && DECL_CHAIN (decl)
5075       && DECL_CLONED_FUNCTION_P (DECL_CHAIN (decl)))
5076     return decl_linkage (DECL_CHAIN (decl));
5077
5078   if (TREE_CODE (decl) == NAMESPACE_DECL)
5079     return lk_external;
5080
5081   /* Linkage of a CONST_DECL depends on the linkage of the enumeration
5082      type.  */
5083   if (TREE_CODE (decl) == CONST_DECL)
5084     return decl_linkage (TYPE_NAME (DECL_CONTEXT (decl)));
5085
5086   /* Things in local scope do not have linkage, if they don't have
5087      TREE_PUBLIC set.  */
5088   if (decl_function_context (decl))
5089     return lk_none;
5090
5091   /* Members of the anonymous namespace also have TREE_PUBLIC unset, but
5092      are considered to have external linkage for language purposes, as do
5093      template instantiations on targets without weak symbols.  DECLs really
5094      meant to have internal linkage have DECL_THIS_STATIC set.  */
5095   if (TREE_CODE (decl) == TYPE_DECL)
5096     return lk_external;
5097   if (VAR_OR_FUNCTION_DECL_P (decl))
5098     {
5099       if (!DECL_THIS_STATIC (decl))
5100         return lk_external;
5101
5102       /* Static data members and static member functions from classes
5103          in anonymous namespace also don't have TREE_PUBLIC set.  */
5104       if (DECL_CLASS_CONTEXT (decl))
5105         return lk_external;
5106     }
5107
5108   /* Everything else has internal linkage.  */
5109   return lk_internal;
5110 }
5111
5112 /* Returns the storage duration of the object or reference associated with
5113    the indicated DECL, which should be a VAR_DECL or PARM_DECL.  */
5114
5115 duration_kind
5116 decl_storage_duration (tree decl)
5117 {
5118   if (TREE_CODE (decl) == PARM_DECL)
5119     return dk_auto;
5120   if (TREE_CODE (decl) == FUNCTION_DECL)
5121     return dk_static;
5122   gcc_assert (VAR_P (decl));
5123   if (!TREE_STATIC (decl)
5124       && !DECL_EXTERNAL (decl))
5125     return dk_auto;
5126   if (CP_DECL_THREAD_LOCAL_P (decl))
5127     return dk_thread;
5128   return dk_static;
5129 }
5130 \f
5131 /* EXP is an expression that we want to pre-evaluate.  Returns (in
5132    *INITP) an expression that will perform the pre-evaluation.  The
5133    value returned by this function is a side-effect free expression
5134    equivalent to the pre-evaluated expression.  Callers must ensure
5135    that *INITP is evaluated before EXP.  */
5136
5137 tree
5138 stabilize_expr (tree exp, tree* initp)
5139 {
5140   tree init_expr;
5141
5142   if (!TREE_SIDE_EFFECTS (exp))
5143     init_expr = NULL_TREE;
5144   else if (VOID_TYPE_P (TREE_TYPE (exp)))
5145     {
5146       init_expr = exp;
5147       exp = void_node;
5148     }
5149   /* There are no expressions with REFERENCE_TYPE, but there can be call
5150      arguments with such a type; just treat it as a pointer.  */
5151   else if (TYPE_REF_P (TREE_TYPE (exp))
5152            || SCALAR_TYPE_P (TREE_TYPE (exp))
5153            || !glvalue_p (exp))
5154     {
5155       init_expr = get_target_expr (exp);
5156       exp = TARGET_EXPR_SLOT (init_expr);
5157       if (CLASS_TYPE_P (TREE_TYPE (exp)))
5158         exp = move (exp);
5159       else
5160         exp = rvalue (exp);
5161     }
5162   else
5163     {
5164       bool xval = !lvalue_p (exp);
5165       exp = cp_build_addr_expr (exp, tf_warning_or_error);
5166       init_expr = get_target_expr (exp);
5167       exp = TARGET_EXPR_SLOT (init_expr);
5168       exp = cp_build_fold_indirect_ref (exp);
5169       if (xval)
5170         exp = move (exp);
5171     }
5172   *initp = init_expr;
5173
5174   gcc_assert (!TREE_SIDE_EFFECTS (exp));
5175   return exp;
5176 }
5177
5178 /* Add NEW_EXPR, an expression whose value we don't care about, after the
5179    similar expression ORIG.  */
5180
5181 tree
5182 add_stmt_to_compound (tree orig, tree new_expr)
5183 {
5184   if (!new_expr || !TREE_SIDE_EFFECTS (new_expr))
5185     return orig;
5186   if (!orig || !TREE_SIDE_EFFECTS (orig))
5187     return new_expr;
5188   return build2 (COMPOUND_EXPR, void_type_node, orig, new_expr);
5189 }
5190
5191 /* Like stabilize_expr, but for a call whose arguments we want to
5192    pre-evaluate.  CALL is modified in place to use the pre-evaluated
5193    arguments, while, upon return, *INITP contains an expression to
5194    compute the arguments.  */
5195
5196 void
5197 stabilize_call (tree call, tree *initp)
5198 {
5199   tree inits = NULL_TREE;
5200   int i;
5201   int nargs = call_expr_nargs (call);
5202
5203   if (call == error_mark_node || processing_template_decl)
5204     {
5205       *initp = NULL_TREE;
5206       return;
5207     }
5208
5209   gcc_assert (TREE_CODE (call) == CALL_EXPR);
5210
5211   for (i = 0; i < nargs; i++)
5212     {
5213       tree init;
5214       CALL_EXPR_ARG (call, i) =
5215         stabilize_expr (CALL_EXPR_ARG (call, i), &init);
5216       inits = add_stmt_to_compound (inits, init);
5217     }
5218
5219   *initp = inits;
5220 }
5221
5222 /* Like stabilize_expr, but for an AGGR_INIT_EXPR whose arguments we want
5223    to pre-evaluate.  CALL is modified in place to use the pre-evaluated
5224    arguments, while, upon return, *INITP contains an expression to
5225    compute the arguments.  */
5226
5227 static void
5228 stabilize_aggr_init (tree call, tree *initp)
5229 {
5230   tree inits = NULL_TREE;
5231   int i;
5232   int nargs = aggr_init_expr_nargs (call);
5233
5234   if (call == error_mark_node)
5235     return;
5236
5237   gcc_assert (TREE_CODE (call) == AGGR_INIT_EXPR);
5238
5239   for (i = 0; i < nargs; i++)
5240     {
5241       tree init;
5242       AGGR_INIT_EXPR_ARG (call, i) =
5243         stabilize_expr (AGGR_INIT_EXPR_ARG (call, i), &init);
5244       inits = add_stmt_to_compound (inits, init);
5245     }
5246
5247   *initp = inits;
5248 }
5249
5250 /* Like stabilize_expr, but for an initialization.
5251
5252    If the initialization is for an object of class type, this function
5253    takes care not to introduce additional temporaries.
5254
5255    Returns TRUE iff the expression was successfully pre-evaluated,
5256    i.e., if INIT is now side-effect free, except for, possibly, a
5257    single call to a constructor.  */
5258
5259 bool
5260 stabilize_init (tree init, tree *initp)
5261 {
5262   tree t = init;
5263
5264   *initp = NULL_TREE;
5265
5266   if (t == error_mark_node || processing_template_decl)
5267     return true;
5268
5269   if (TREE_CODE (t) == INIT_EXPR)
5270     t = TREE_OPERAND (t, 1);
5271   if (TREE_CODE (t) == TARGET_EXPR)
5272     t = TARGET_EXPR_INITIAL (t);
5273
5274   /* If the RHS can be stabilized without breaking copy elision, stabilize
5275      it.  We specifically don't stabilize class prvalues here because that
5276      would mean an extra copy, but they might be stabilized below.  */
5277   if (TREE_CODE (init) == INIT_EXPR
5278       && TREE_CODE (t) != CONSTRUCTOR
5279       && TREE_CODE (t) != AGGR_INIT_EXPR
5280       && (SCALAR_TYPE_P (TREE_TYPE (t))
5281           || glvalue_p (t)))
5282     {
5283       TREE_OPERAND (init, 1) = stabilize_expr (t, initp);
5284       return true;
5285     }
5286
5287   if (TREE_CODE (t) == COMPOUND_EXPR
5288       && TREE_CODE (init) == INIT_EXPR)
5289     {
5290       tree last = expr_last (t);
5291       /* Handle stabilizing the EMPTY_CLASS_EXPR pattern.  */
5292       if (!TREE_SIDE_EFFECTS (last))
5293         {
5294           *initp = t;
5295           TREE_OPERAND (init, 1) = last;
5296           return true;
5297         }
5298     }
5299
5300   if (TREE_CODE (t) == CONSTRUCTOR)
5301     {
5302       /* Aggregate initialization: stabilize each of the field
5303          initializers.  */
5304       unsigned i;
5305       constructor_elt *ce;
5306       bool good = true;
5307       vec<constructor_elt, va_gc> *v = CONSTRUCTOR_ELTS (t);
5308       for (i = 0; vec_safe_iterate (v, i, &ce); ++i)
5309         {
5310           tree type = TREE_TYPE (ce->value);
5311           tree subinit;
5312           if (TYPE_REF_P (type)
5313               || SCALAR_TYPE_P (type))
5314             ce->value = stabilize_expr (ce->value, &subinit);
5315           else if (!stabilize_init (ce->value, &subinit))
5316             good = false;
5317           *initp = add_stmt_to_compound (*initp, subinit);
5318         }
5319       return good;
5320     }
5321
5322   if (TREE_CODE (t) == CALL_EXPR)
5323     {
5324       stabilize_call (t, initp);
5325       return true;
5326     }
5327
5328   if (TREE_CODE (t) == AGGR_INIT_EXPR)
5329     {
5330       stabilize_aggr_init (t, initp);
5331       return true;
5332     }
5333
5334   /* The initialization is being performed via a bitwise copy -- and
5335      the item copied may have side effects.  */
5336   return !TREE_SIDE_EFFECTS (init);
5337 }
5338
5339 /* Returns true if a cast to TYPE may appear in an integral constant
5340    expression.  */
5341
5342 bool
5343 cast_valid_in_integral_constant_expression_p (tree type)
5344 {
5345   return (INTEGRAL_OR_ENUMERATION_TYPE_P (type)
5346           || cxx_dialect >= cxx11
5347           || dependent_type_p (type)
5348           || type == error_mark_node);
5349 }
5350
5351 /* Return true if we need to fix linkage information of DECL.  */
5352
5353 static bool
5354 cp_fix_function_decl_p (tree decl)
5355 {
5356   /* Skip if DECL is not externally visible.  */
5357   if (!TREE_PUBLIC (decl))
5358     return false;
5359
5360   /* We need to fix DECL if it a appears to be exported but with no
5361      function body.  Thunks do not have CFGs and we may need to
5362      handle them specially later.   */
5363   if (!gimple_has_body_p (decl)
5364       && !DECL_THUNK_P (decl)
5365       && !DECL_EXTERNAL (decl))
5366     {
5367       struct cgraph_node *node = cgraph_node::get (decl);
5368
5369       /* Don't fix same_body aliases.  Although they don't have their own
5370          CFG, they share it with what they alias to.  */
5371       if (!node || !node->alias
5372           || !vec_safe_length (node->ref_list.references))
5373         return true;
5374     }
5375
5376   return false;
5377 }
5378
5379 /* Clean the C++ specific parts of the tree T. */
5380
5381 void
5382 cp_free_lang_data (tree t)
5383 {
5384   if (TREE_CODE (t) == METHOD_TYPE
5385       || TREE_CODE (t) == FUNCTION_TYPE)
5386     {
5387       /* Default args are not interesting anymore.  */
5388       tree argtypes = TYPE_ARG_TYPES (t);
5389       while (argtypes)
5390         {
5391           TREE_PURPOSE (argtypes) = 0;
5392           argtypes = TREE_CHAIN (argtypes);
5393         }
5394     }
5395   else if (TREE_CODE (t) == FUNCTION_DECL
5396            && cp_fix_function_decl_p (t))
5397     {
5398       /* If T is used in this translation unit at all,  the definition
5399          must exist somewhere else since we have decided to not emit it
5400          in this TU.  So make it an external reference.  */
5401       DECL_EXTERNAL (t) = 1;
5402       TREE_STATIC (t) = 0;
5403     }
5404   if (TREE_CODE (t) == NAMESPACE_DECL)
5405     /* We do not need the leftover chaining of namespaces from the
5406        binding level.  */
5407     DECL_CHAIN (t) = NULL_TREE;
5408 }
5409
5410 /* Stub for c-common.  Please keep in sync with c-decl.c.
5411    FIXME: If address space support is target specific, then this
5412    should be a C target hook.  But currently this is not possible,
5413    because this function is called via REGISTER_TARGET_PRAGMAS.  */
5414 void
5415 c_register_addr_space (const char * /*word*/, addr_space_t /*as*/)
5416 {
5417 }
5418
5419 /* Return the number of operands in T that we care about for things like
5420    mangling.  */
5421
5422 int
5423 cp_tree_operand_length (const_tree t)
5424 {
5425   enum tree_code code = TREE_CODE (t);
5426
5427   if (TREE_CODE_CLASS (code) == tcc_vl_exp)
5428     return VL_EXP_OPERAND_LENGTH (t);
5429
5430   return cp_tree_code_length (code);
5431 }
5432
5433 /* Like cp_tree_operand_length, but takes a tree_code CODE.  */
5434
5435 int
5436 cp_tree_code_length (enum tree_code code)
5437 {
5438   gcc_assert (TREE_CODE_CLASS (code) != tcc_vl_exp);
5439
5440   switch (code)
5441     {
5442     case PREINCREMENT_EXPR:
5443     case PREDECREMENT_EXPR:
5444     case POSTINCREMENT_EXPR:
5445     case POSTDECREMENT_EXPR:
5446       return 1;
5447
5448     case ARRAY_REF:
5449       return 2;
5450
5451     case EXPR_PACK_EXPANSION:
5452       return 1;
5453
5454     default:
5455       return TREE_CODE_LENGTH (code);
5456     }
5457 }
5458
5459 /* Implement -Wzero_as_null_pointer_constant.  Return true if the
5460    conditions for the warning hold, false otherwise.  */
5461 bool
5462 maybe_warn_zero_as_null_pointer_constant (tree expr, location_t loc)
5463 {
5464   if (c_inhibit_evaluation_warnings == 0
5465       && !null_node_p (expr) && !NULLPTR_TYPE_P (TREE_TYPE (expr)))
5466     {
5467       warning_at (loc, OPT_Wzero_as_null_pointer_constant,
5468                   "zero as null pointer constant");
5469       return true;
5470     }
5471   return false;
5472 }
5473 \f
5474 #if defined ENABLE_TREE_CHECKING && (GCC_VERSION >= 2007)
5475 /* Complain that some language-specific thing hanging off a tree
5476    node has been accessed improperly.  */
5477
5478 void
5479 lang_check_failed (const char* file, int line, const char* function)
5480 {
5481   internal_error ("lang_* check: failed in %s, at %s:%d",
5482                   function, trim_filename (file), line);
5483 }
5484 #endif /* ENABLE_TREE_CHECKING */
5485
5486 #if CHECKING_P
5487
5488 namespace selftest {
5489
5490 /* Verify that lvalue_kind () works, for various expressions,
5491    and that location wrappers don't affect the results.  */
5492
5493 static void
5494 test_lvalue_kind ()
5495 {
5496   location_t loc = BUILTINS_LOCATION;
5497
5498   /* Verify constants and parameters, without and with
5499      location wrappers.  */
5500   tree int_cst = build_int_cst (integer_type_node, 42);
5501   ASSERT_EQ (clk_none, lvalue_kind (int_cst));
5502
5503   tree wrapped_int_cst = maybe_wrap_with_location (int_cst, loc);
5504   ASSERT_TRUE (location_wrapper_p (wrapped_int_cst));
5505   ASSERT_EQ (clk_none, lvalue_kind (wrapped_int_cst));
5506
5507   tree string_lit = build_string (4, "foo");
5508   TREE_TYPE (string_lit) = char_array_type_node;
5509   string_lit = fix_string_type (string_lit);
5510   ASSERT_EQ (clk_ordinary, lvalue_kind (string_lit));
5511
5512   tree wrapped_string_lit = maybe_wrap_with_location (string_lit, loc);
5513   ASSERT_TRUE (location_wrapper_p (wrapped_string_lit));
5514   ASSERT_EQ (clk_ordinary, lvalue_kind (wrapped_string_lit));
5515
5516   tree parm = build_decl (UNKNOWN_LOCATION, PARM_DECL,
5517                           get_identifier ("some_parm"),
5518                           integer_type_node);
5519   ASSERT_EQ (clk_ordinary, lvalue_kind (parm));
5520
5521   tree wrapped_parm = maybe_wrap_with_location (parm, loc);
5522   ASSERT_TRUE (location_wrapper_p (wrapped_parm));
5523   ASSERT_EQ (clk_ordinary, lvalue_kind (wrapped_parm));
5524
5525   /* Verify that lvalue_kind of std::move on a parm isn't
5526      affected by location wrappers.  */
5527   tree rvalue_ref_of_parm = move (parm);
5528   ASSERT_EQ (clk_rvalueref, lvalue_kind (rvalue_ref_of_parm));
5529   tree rvalue_ref_of_wrapped_parm = move (wrapped_parm);
5530   ASSERT_EQ (clk_rvalueref, lvalue_kind (rvalue_ref_of_wrapped_parm));
5531 }
5532
5533 /* Run all of the selftests within this file.  */
5534
5535 void
5536 cp_tree_c_tests ()
5537 {
5538   test_lvalue_kind ();
5539 }
5540
5541 } // namespace selftest
5542
5543 #endif /* #if CHECKING_P */
5544
5545
5546 #include "gt-cp-tree.h"