gcc/cp/tree.c

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