gcc/cp/pt.c

   1 /* Handle parameterized types (templates) for GNU C++.
   2    Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998, 1999, 2000,
   3    2001, 2002, 2003, 2004, 2005, 2007, 2008, 2009, 2010, 2011
   4    Free Software Foundation, Inc.
   5    Written by Ken Raeburn (raeburn@cygnus.com) while at Watchmaker Computing.
   6    Rewritten by Jason Merrill (jason@cygnus.com).
   7
   8 This file is part of GCC.
   9
  10 GCC is free software; you can redistribute it and/or modify
  11 it under the terms of the GNU General Public License as published by
  12 the Free Software Foundation; either version 3, or (at your option)
  13 any later version.
  14
  15 GCC is distributed in the hope that it will be useful,
  16 but WITHOUT ANY WARRANTY; without even the implied warranty of
  17 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  18 GNU General Public License for more details.
  19
  20 You should have received a copy of the GNU General Public License
  21 along with GCC; see the file COPYING3.  If not see
  22 <http://www.gnu.org/licenses/>.  */
  23
  24 /* Known bugs or deficiencies include:
  25
  26      all methods must be provided in header files; can't use a source
  27      file that contains only the method templates and "just win".  */
  28
  29 #include "config.h"
  30 #include "system.h"
  31 #include "coretypes.h"
  32 #include "tm.h"
  33 #include "tree.h"
  34 #include "intl.h"
  35 #include "pointer-set.h"
  36 #include "flags.h"
  37 #include "cp-tree.h"
  38 #include "c-family/c-common.h"
  39 #include "c-family/c-objc.h"
  40 #include "cp-objcp-common.h"
  41 #include "tree-inline.h"
  42 #include "decl.h"
  43 #include "output.h"
  44 #include "toplev.h"
  45 #include "timevar.h"
  46 #include "tree-iterator.h"
  47 #include "vecprim.h"
  48
  49 /* The type of functions taking a tree, and some additional data, and
  50    returning an int.  */
  51 typedef int (*tree_fn_t) (tree, void*);
  52
  53 /* The PENDING_TEMPLATES is a TREE_LIST of templates whose
  54    instantiations have been deferred, either because their definitions
  55    were not yet available, or because we were putting off doing the work.  */
  56 struct GTY ((chain_next ("%h.next"))) pending_template {
  57   struct pending_template *next;
  58   struct tinst_level *tinst;
  59 };
  60
  61 static GTY(()) struct pending_template *pending_templates;
  62 static GTY(()) struct pending_template *last_pending_template;
  63
  64 int processing_template_parmlist;
  65 static int template_header_count;
  66
  67 static GTY(()) tree saved_trees;
  68 static VEC(int,heap) *inline_parm_levels;
  69
  70 static GTY(()) struct tinst_level *current_tinst_level;
  71
  72 static GTY(()) tree saved_access_scope;
  73
  74 /* Live only within one (recursive) call to tsubst_expr.  We use
  75    this to pass the statement expression node from the STMT_EXPR
  76    to the EXPR_STMT that is its result.  */
  77 static tree cur_stmt_expr;
  78
  79 /* A map from local variable declarations in the body of the template
  80    presently being instantiated to the corresponding instantiated
  81    local variables.  */
  82 static htab_t local_specializations;
  83
  84 typedef struct GTY(()) spec_entry
  85 {
  86   tree tmpl;
  87   tree args;
  88   tree spec;
  89 } spec_entry;
  90
  91 static GTY ((param_is (spec_entry)))
  92   htab_t decl_specializations;
  93
  94 static GTY ((param_is (spec_entry)))
  95   htab_t type_specializations;
  96
  97 /* Contains canonical template parameter types. The vector is indexed by
  98    the TEMPLATE_TYPE_IDX of the template parameter. Each element is a
  99    TREE_LIST, whose TREE_VALUEs contain the canonical template
 100    parameters of various types and levels.  */
 101 static GTY(()) VEC(tree,gc) *canonical_template_parms;
 102
 103 #define UNIFY_ALLOW_NONE 0
 104 #define UNIFY_ALLOW_MORE_CV_QUAL 1
 105 #define UNIFY_ALLOW_LESS_CV_QUAL 2
 106 #define UNIFY_ALLOW_DERIVED 4
 107 #define UNIFY_ALLOW_INTEGER 8
 108 #define UNIFY_ALLOW_OUTER_LEVEL 16
 109 #define UNIFY_ALLOW_OUTER_MORE_CV_QUAL 32
 110 #define UNIFY_ALLOW_OUTER_LESS_CV_QUAL 64
 111
 112 enum template_base_result {
 113   tbr_incomplete_type,
 114   tbr_ambiguous_baseclass,
 115   tbr_success
 116 };
 117
 118 static void push_access_scope (tree);
 119 static void pop_access_scope (tree);
 120 static void push_deduction_access_scope (tree);
 121 static void pop_deduction_access_scope (tree);
 122 static bool resolve_overloaded_unification (tree, tree, tree, tree,
 123                                             unification_kind_t, int,
 124                                             bool);
 125 static int try_one_overload (tree, tree, tree, tree, tree,
 126                              unification_kind_t, int, bool, bool);
 127 static int unify (tree, tree, tree, tree, int, bool);
 128 static void add_pending_template (tree);
 129 static tree reopen_tinst_level (struct tinst_level *);
 130 static tree tsubst_initializer_list (tree, tree);
 131 static tree get_class_bindings (tree, tree, tree);
 132 static tree coerce_template_parms (tree, tree, tree, tsubst_flags_t,
 133                                    bool, bool);
 134 static void tsubst_enum (tree, tree, tree);
 135 static tree add_to_template_args (tree, tree);
 136 static tree add_outermost_template_args (tree, tree);
 137 static bool check_instantiated_args (tree, tree, tsubst_flags_t);
 138 static int maybe_adjust_types_for_deduction (unification_kind_t, tree*, tree*,
 139                                              tree);
 140 static int type_unification_real (tree, tree, tree, const tree *,
 141                                   unsigned int, int, unification_kind_t, int,
 142                                   bool);
 143 static void note_template_header (int);
 144 static tree convert_nontype_argument_function (tree, tree);
 145 static tree convert_nontype_argument (tree, tree, tsubst_flags_t);
 146 static tree convert_template_argument (tree, tree, tree,
 147                                        tsubst_flags_t, int, tree);
 148 static int for_each_template_parm (tree, tree_fn_t, void*,
 149                                    struct pointer_set_t*, bool);
 150 static tree expand_template_argument_pack (tree);
 151 static tree build_template_parm_index (int, int, int, int, tree, tree);
 152 static bool inline_needs_template_parms (tree);
 153 static void push_inline_template_parms_recursive (tree, int);
 154 static tree retrieve_local_specialization (tree);
 155 static void register_local_specialization (tree, tree);
 156 static hashval_t hash_specialization (const void *p);
 157 static tree reduce_template_parm_level (tree, tree, int, tree, tsubst_flags_t);
 158 static int mark_template_parm (tree, void *);
 159 static int template_parm_this_level_p (tree, void *);
 160 static tree tsubst_friend_function (tree, tree);
 161 static tree tsubst_friend_class (tree, tree);
 162 static int can_complete_type_without_circularity (tree);
 163 static tree get_bindings (tree, tree, tree, bool);
 164 static int template_decl_level (tree);
 165 static int check_cv_quals_for_unify (int, tree, tree);
 166 static void template_parm_level_and_index (tree, int*, int*);
 167 static int unify_pack_expansion (tree, tree, tree,
 168                                  tree, unification_kind_t, bool, bool);
 169 static tree tsubst_template_arg (tree, tree, tsubst_flags_t, tree);
 170 static tree tsubst_template_args (tree, tree, tsubst_flags_t, tree);
 171 static tree tsubst_template_parms (tree, tree, tsubst_flags_t);
 172 static void regenerate_decl_from_template (tree, tree);
 173 static tree most_specialized_class (tree, tree, tsubst_flags_t);
 174 static tree tsubst_aggr_type (tree, tree, tsubst_flags_t, tree, int);
 175 static tree tsubst_arg_types (tree, tree, tsubst_flags_t, tree);
 176 static tree tsubst_function_type (tree, tree, tsubst_flags_t, tree);
 177 static bool check_specialization_scope (void);
 178 static tree process_partial_specialization (tree);
 179 static void set_current_access_from_decl (tree);
 180 static enum template_base_result get_template_base (tree, tree, tree, tree,
 181                                                     bool , tree *);
 182 static tree try_class_unification (tree, tree, tree, tree, bool);
 183 static int coerce_template_template_parms (tree, tree, tsubst_flags_t,
 184                                            tree, tree);
 185 static bool template_template_parm_bindings_ok_p (tree, tree);
 186 static int template_args_equal (tree, tree);
 187 static void tsubst_default_arguments (tree);
 188 static tree for_each_template_parm_r (tree *, int *, void *);
 189 static tree copy_default_args_to_explicit_spec_1 (tree, tree);
 190 static void copy_default_args_to_explicit_spec (tree);
 191 static int invalid_nontype_parm_type_p (tree, tsubst_flags_t);
 192 static int eq_local_specializations (const void *, const void *);
 193 static bool dependent_template_arg_p (tree);
 194 static bool any_template_arguments_need_structural_equality_p (tree);
 195 static bool dependent_type_p_r (tree);
 196 static tree tsubst_expr (tree, tree, tsubst_flags_t, tree, bool);
 197 static tree tsubst_copy (tree, tree, tsubst_flags_t, tree);
 198 static tree tsubst_pack_expansion (tree, tree, tsubst_flags_t, tree);
 199 static tree tsubst_decl (tree, tree, tsubst_flags_t);
 200 static void perform_typedefs_access_check (tree tmpl, tree targs);
 201 static void append_type_to_template_for_access_check_1 (tree, tree, tree,
 202                                                         location_t);
 203 static tree listify (tree);
 204 static tree listify_autos (tree, tree);
 205 static tree template_parm_to_arg (tree t);
 206 static bool arg_from_parm_pack_p (tree, tree);
 207 static tree current_template_args (void);
 208 static tree fixup_template_type_parm_type (tree, int);
 209 static tree fixup_template_parm_index (tree, tree, int);
 210 static tree tsubst_template_parm (tree, tree, tsubst_flags_t);
 211
 212 /* Make the current scope suitable for access checking when we are
 213    processing T.  T can be FUNCTION_DECL for instantiated function
 214    template, or VAR_DECL for static member variable (need by
 215    instantiate_decl).  */
 216
 217 static void
 218 push_access_scope (tree t)
 219 {
 220   gcc_assert (TREE_CODE (t) == FUNCTION_DECL
 221               || TREE_CODE (t) == VAR_DECL);
 222
 223   if (DECL_FRIEND_CONTEXT (t))
 224     push_nested_class (DECL_FRIEND_CONTEXT (t));
 225   else if (DECL_CLASS_SCOPE_P (t))
 226     push_nested_class (DECL_CONTEXT (t));
 227   else
 228     push_to_top_level ();
 229
 230   if (TREE_CODE (t) == FUNCTION_DECL)
 231     {
 232       saved_access_scope = tree_cons
 233         (NULL_TREE, current_function_decl, saved_access_scope);
 234       current_function_decl = t;
 235     }
 236 }
 237
 238 /* Restore the scope set up by push_access_scope.  T is the node we
 239    are processing.  */
 240
 241 static void
 242 pop_access_scope (tree t)
 243 {
 244   if (TREE_CODE (t) == FUNCTION_DECL)
 245     {
 246       current_function_decl = TREE_VALUE (saved_access_scope);
 247       saved_access_scope = TREE_CHAIN (saved_access_scope);
 248     }
 249
 250   if (DECL_FRIEND_CONTEXT (t) || DECL_CLASS_SCOPE_P (t))
 251     pop_nested_class ();
 252   else
 253     pop_from_top_level ();
 254 }
 255
 256 /* Do any processing required when DECL (a member template
 257    declaration) is finished.  Returns the TEMPLATE_DECL corresponding
 258    to DECL, unless it is a specialization, in which case the DECL
 259    itself is returned.  */
 260
 261 tree
 262 finish_member_template_decl (tree decl)
 263 {
 264   if (decl == error_mark_node)
 265     return error_mark_node;
 266
 267   gcc_assert (DECL_P (decl));
 268
 269   if (TREE_CODE (decl) == TYPE_DECL)
 270     {
 271       tree type;
 272
 273       type = TREE_TYPE (decl);
 274       if (type == error_mark_node)
 275         return error_mark_node;
 276       if (MAYBE_CLASS_TYPE_P (type)
 277           && CLASSTYPE_TEMPLATE_INFO (type)
 278           && !CLASSTYPE_TEMPLATE_SPECIALIZATION (type))
 279         {
 280           tree tmpl = CLASSTYPE_TI_TEMPLATE (type);
 281           check_member_template (tmpl);
 282           return tmpl;
 283         }
 284       return NULL_TREE;
 285     }
 286   else if (TREE_CODE (decl) == FIELD_DECL)
 287     error ("data member %qD cannot be a member template", decl);
 288   else if (DECL_TEMPLATE_INFO (decl))
 289     {
 290       if (!DECL_TEMPLATE_SPECIALIZATION (decl))
 291         {
 292           check_member_template (DECL_TI_TEMPLATE (decl));
 293           return DECL_TI_TEMPLATE (decl);
 294         }
 295       else
 296         return decl;
 297     }
 298   else
 299     error ("invalid member template declaration %qD", decl);
 300
 301   return error_mark_node;
 302 }
 303
 304 /* Create a template info node.  */
 305
 306 tree
 307 build_template_info (tree template_decl, tree template_args)
 308 {
 309   tree result = make_node (TEMPLATE_INFO);
 310   TI_TEMPLATE (result) = template_decl;
 311   TI_ARGS (result) = template_args;
 312   return result;
 313 }
 314
 315 /* Return the template info node corresponding to T, whatever T is.  */
 316
 317 tree
 318 get_template_info (const_tree t)
 319 {
 320   tree tinfo = NULL_TREE;
 321
 322   if (!t || t == error_mark_node)
 323     return NULL;
 324
 325   if (DECL_P (t) && DECL_LANG_SPECIFIC (t))
 326     tinfo = DECL_TEMPLATE_INFO (t);
 327
 328   if (!tinfo && DECL_IMPLICIT_TYPEDEF_P (t))
 329     t = TREE_TYPE (t);
 330
 331   if (TAGGED_TYPE_P (t))
 332     tinfo = TYPE_TEMPLATE_INFO (t);
 333   else if (TREE_CODE (t) == BOUND_TEMPLATE_TEMPLATE_PARM)
 334     tinfo = TEMPLATE_TEMPLATE_PARM_TEMPLATE_INFO (t);
 335
 336   return tinfo;
 337 }
 338
 339 /* Returns the template nesting level of the indicated class TYPE.
 340
 341    For example, in:
 342      template <class T>
 343      struct A
 344      {
 345        template <class U>
 346        struct B {};
 347      };
 348
 349    A<T>::B<U> has depth two, while A<T> has depth one.
 350    Both A<T>::B<int> and A<int>::B<U> have depth one, if
 351    they are instantiations, not specializations.
 352
 353    This function is guaranteed to return 0 if passed NULL_TREE so
 354    that, for example, `template_class_depth (current_class_type)' is
 355    always safe.  */
 356
 357 int
 358 template_class_depth (tree type)
 359 {
 360   int depth;
 361
 362   for (depth = 0;
 363        type && TREE_CODE (type) != NAMESPACE_DECL;
 364        type = (TREE_CODE (type) == FUNCTION_DECL)
 365          ? CP_DECL_CONTEXT (type) : CP_TYPE_CONTEXT (type))
 366     {
 367       tree tinfo = get_template_info (type);
 368
 369       if (tinfo && PRIMARY_TEMPLATE_P (TI_TEMPLATE (tinfo))
 370           && uses_template_parms (INNERMOST_TEMPLATE_ARGS (TI_ARGS (tinfo))))
 371         ++depth;
 372     }
 373
 374   return depth;
 375 }
 376
 377 /* Subroutine of maybe_begin_member_template_processing.
 378    Returns true if processing DECL needs us to push template parms.  */
 379
 380 static bool
 381 inline_needs_template_parms (tree decl)
 382 {
 383   if (! DECL_TEMPLATE_INFO (decl))
 384     return false;
 385
 386   return (TMPL_PARMS_DEPTH (DECL_TEMPLATE_PARMS (most_general_template (decl)))
 387           > (processing_template_decl + DECL_TEMPLATE_SPECIALIZATION (decl)));
 388 }
 389
 390 /* Subroutine of maybe_begin_member_template_processing.
 391    Push the template parms in PARMS, starting from LEVELS steps into the
 392    chain, and ending at the beginning, since template parms are listed
 393    innermost first.  */
 394
 395 static void
 396 push_inline_template_parms_recursive (tree parmlist, int levels)
 397 {
 398   tree parms = TREE_VALUE (parmlist);
 399   int i;
 400
 401   if (levels > 1)
 402     push_inline_template_parms_recursive (TREE_CHAIN (parmlist), levels - 1);
 403
 404   ++processing_template_decl;
 405   current_template_parms
 406     = tree_cons (size_int (processing_template_decl),
 407                  parms, current_template_parms);
 408   TEMPLATE_PARMS_FOR_INLINE (current_template_parms) = 1;
 409
 410   begin_scope (TREE_VEC_LENGTH (parms) ? sk_template_parms : sk_template_spec,
 411                NULL);
 412   for (i = 0; i < TREE_VEC_LENGTH (parms); ++i)
 413     {
 414       tree parm = TREE_VALUE (TREE_VEC_ELT (parms, i));
 415
 416       if (parm == error_mark_node)
 417         continue;
 418
 419       gcc_assert (DECL_P (parm));
 420
 421       switch (TREE_CODE (parm))
 422         {
 423         case TYPE_DECL:
 424         case TEMPLATE_DECL:
 425           pushdecl (parm);
 426           break;
 427
 428         case PARM_DECL:
 429           {
 430             /* Make a CONST_DECL as is done in process_template_parm.
 431                It is ugly that we recreate this here; the original
 432                version built in process_template_parm is no longer
 433                available.  */
 434             tree decl = build_decl (DECL_SOURCE_LOCATION (parm),
 435                                     CONST_DECL, DECL_NAME (parm),
 436                                     TREE_TYPE (parm));
 437             DECL_ARTIFICIAL (decl) = 1;
 438             TREE_CONSTANT (decl) = 1;
 439             TREE_READONLY (decl) = 1;
 440             DECL_INITIAL (decl) = DECL_INITIAL (parm);
 441             SET_DECL_TEMPLATE_PARM_P (decl);
 442             pushdecl (decl);
 443           }
 444           break;
 445
 446         default:
 447           gcc_unreachable ();
 448         }
 449     }
 450 }
 451
 452 /* Restore the template parameter context for a member template or
 453    a friend template defined in a class definition.  */
 454
 455 void
 456 maybe_begin_member_template_processing (tree decl)
 457 {
 458   tree parms;
 459   int levels = 0;
 460
 461   if (inline_needs_template_parms (decl))
 462     {
 463       parms = DECL_TEMPLATE_PARMS (most_general_template (decl));
 464       levels = TMPL_PARMS_DEPTH (parms) - processing_template_decl;
 465
 466       if (DECL_TEMPLATE_SPECIALIZATION (decl))
 467         {
 468           --levels;
 469           parms = TREE_CHAIN (parms);
 470         }
 471
 472       push_inline_template_parms_recursive (parms, levels);
 473     }
 474
 475   /* Remember how many levels of template parameters we pushed so that
 476      we can pop them later.  */
 477   VEC_safe_push (int, heap, inline_parm_levels, levels);
 478 }
 479
 480 /* Undo the effects of maybe_begin_member_template_processing.  */
 481
 482 void
 483 maybe_end_member_template_processing (void)
 484 {
 485   int i;
 486   int last;
 487
 488   if (VEC_length (int, inline_parm_levels) == 0)
 489     return;
 490
 491   last = VEC_pop (int, inline_parm_levels);
 492   for (i = 0; i < last; ++i)
 493     {
 494       --processing_template_decl;
 495       current_template_parms = TREE_CHAIN (current_template_parms);
 496       poplevel (0, 0, 0);
 497     }
 498 }
 499
 500 /* Return a new template argument vector which contains all of ARGS,
 501    but has as its innermost set of arguments the EXTRA_ARGS.  */
 502
 503 static tree
 504 add_to_template_args (tree args, tree extra_args)
 505 {
 506   tree new_args;
 507   int extra_depth;
 508   int i;
 509   int j;
 510
 511   if (args == NULL_TREE || extra_args == error_mark_node)
 512     return extra_args;
 513
 514   extra_depth = TMPL_ARGS_DEPTH (extra_args);
 515   new_args = make_tree_vec (TMPL_ARGS_DEPTH (args) + extra_depth);
 516
 517   for (i = 1; i <= TMPL_ARGS_DEPTH (args); ++i)
 518     SET_TMPL_ARGS_LEVEL (new_args, i, TMPL_ARGS_LEVEL (args, i));
 519
 520   for (j = 1; j <= extra_depth; ++j, ++i)
 521     SET_TMPL_ARGS_LEVEL (new_args, i, TMPL_ARGS_LEVEL (extra_args, j));
 522
 523   return new_args;
 524 }
 525
 526 /* Like add_to_template_args, but only the outermost ARGS are added to
 527    the EXTRA_ARGS.  In particular, all but TMPL_ARGS_DEPTH
 528    (EXTRA_ARGS) levels are added.  This function is used to combine
 529    the template arguments from a partial instantiation with the
 530    template arguments used to attain the full instantiation from the
 531    partial instantiation.  */
 532
 533 static tree
 534 add_outermost_template_args (tree args, tree extra_args)
 535 {
 536   tree new_args;
 537
 538   /* If there are more levels of EXTRA_ARGS than there are ARGS,
 539      something very fishy is going on.  */
 540   gcc_assert (TMPL_ARGS_DEPTH (args) >= TMPL_ARGS_DEPTH (extra_args));
 541
 542   /* If *all* the new arguments will be the EXTRA_ARGS, just return
 543      them.  */
 544   if (TMPL_ARGS_DEPTH (args) == TMPL_ARGS_DEPTH (extra_args))
 545     return extra_args;
 546
 547   /* For the moment, we make ARGS look like it contains fewer levels.  */
 548   TREE_VEC_LENGTH (args) -= TMPL_ARGS_DEPTH (extra_args);
 549
 550   new_args = add_to_template_args (args, extra_args);
 551
 552   /* Now, we restore ARGS to its full dimensions.  */
 553   TREE_VEC_LENGTH (args) += TMPL_ARGS_DEPTH (extra_args);
 554
 555   return new_args;
 556 }
 557
 558 /* Return the N levels of innermost template arguments from the ARGS.  */
 559
 560 tree
 561 get_innermost_template_args (tree args, int n)
 562 {
 563   tree new_args;
 564   int extra_levels;
 565   int i;
 566
 567   gcc_assert (n >= 0);
 568
 569   /* If N is 1, just return the innermost set of template arguments.  */
 570   if (n == 1)
 571     return TMPL_ARGS_LEVEL (args, TMPL_ARGS_DEPTH (args));
 572
 573   /* If we're not removing anything, just return the arguments we were
 574      given.  */
 575   extra_levels = TMPL_ARGS_DEPTH (args) - n;
 576   gcc_assert (extra_levels >= 0);
 577   if (extra_levels == 0)
 578     return args;
 579
 580   /* Make a new set of arguments, not containing the outer arguments.  */
 581   new_args = make_tree_vec (n);
 582   for (i = 1; i <= n; ++i)
 583     SET_TMPL_ARGS_LEVEL (new_args, i,
 584                          TMPL_ARGS_LEVEL (args, i + extra_levels));
 585
 586   return new_args;
 587 }
 588
 589 /* The inverse of get_innermost_template_args: Return all but the innermost
 590    EXTRA_LEVELS levels of template arguments from the ARGS.  */
 591
 592 static tree
 593 strip_innermost_template_args (tree args, int extra_levels)
 594 {
 595   tree new_args;
 596   int n = TMPL_ARGS_DEPTH (args) - extra_levels;
 597   int i;
 598
 599   gcc_assert (n >= 0);
 600
 601   /* If N is 1, just return the outermost set of template arguments.  */
 602   if (n == 1)
 603     return TMPL_ARGS_LEVEL (args, 1);
 604
 605   /* If we're not removing anything, just return the arguments we were
 606      given.  */
 607   gcc_assert (extra_levels >= 0);
 608   if (extra_levels == 0)
 609     return args;
 610
 611   /* Make a new set of arguments, not containing the inner arguments.  */
 612   new_args = make_tree_vec (n);
 613   for (i = 1; i <= n; ++i)
 614     SET_TMPL_ARGS_LEVEL (new_args, i,
 615                          TMPL_ARGS_LEVEL (args, i));
 616
 617   return new_args;
 618 }
 619
 620 /* We've got a template header coming up; push to a new level for storing
 621    the parms.  */
 622
 623 void
 624 begin_template_parm_list (void)
 625 {
 626   /* We use a non-tag-transparent scope here, which causes pushtag to
 627      put tags in this scope, rather than in the enclosing class or
 628      namespace scope.  This is the right thing, since we want
 629      TEMPLATE_DECLS, and not TYPE_DECLS for template classes.  For a
 630      global template class, push_template_decl handles putting the
 631      TEMPLATE_DECL into top-level scope.  For a nested template class,
 632      e.g.:
 633
 634        template <class T> struct S1 {
 635          template <class T> struct S2 {};
 636        };
 637
 638      pushtag contains special code to call pushdecl_with_scope on the
 639      TEMPLATE_DECL for S2.  */
 640   begin_scope (sk_template_parms, NULL);
 641   ++processing_template_decl;
 642   ++processing_template_parmlist;
 643   note_template_header (0);
 644 }
 645
 646 /* This routine is called when a specialization is declared.  If it is
 647    invalid to declare a specialization here, an error is reported and
 648    false is returned, otherwise this routine will return true.  */
 649
 650 static bool
 651 check_specialization_scope (void)
 652 {
 653   tree scope = current_scope ();
 654
 655   /* [temp.expl.spec]
 656
 657      An explicit specialization shall be declared in the namespace of
 658      which the template is a member, or, for member templates, in the
 659      namespace of which the enclosing class or enclosing class
 660      template is a member.  An explicit specialization of a member
 661      function, member class or static data member of a class template
 662      shall be declared in the namespace of which the class template
 663      is a member.  */
 664   if (scope && TREE_CODE (scope) != NAMESPACE_DECL)
 665     {
 666       error ("explicit specialization in non-namespace scope %qD", scope);
 667       return false;
 668     }
 669
 670   /* [temp.expl.spec]
 671
 672      In an explicit specialization declaration for a member of a class
 673      template or a member template that appears in namespace scope,
 674      the member template and some of its enclosing class templates may
 675      remain unspecialized, except that the declaration shall not
 676      explicitly specialize a class member template if its enclosing
 677      class templates are not explicitly specialized as well.  */
 678   if (current_template_parms)
 679     {
 680       error ("enclosing class templates are not explicitly specialized");
 681       return false;
 682     }
 683
 684   return true;
 685 }
 686
 687 /* We've just seen template <>.  */
 688
 689 bool
 690 begin_specialization (void)
 691 {
 692   begin_scope (sk_template_spec, NULL);
 693   note_template_header (1);
 694   return check_specialization_scope ();
 695 }
 696
 697 /* Called at then end of processing a declaration preceded by
 698    template<>.  */
 699
 700 void
 701 end_specialization (void)
 702 {
 703   finish_scope ();
 704   reset_specialization ();
 705 }
 706
 707 /* Any template <>'s that we have seen thus far are not referring to a
 708    function specialization.  */
 709
 710 void
 711 reset_specialization (void)
 712 {
 713   processing_specialization = 0;
 714   template_header_count = 0;
 715 }
 716
 717 /* We've just seen a template header.  If SPECIALIZATION is nonzero,
 718    it was of the form template <>.  */
 719
 720 static void
 721 note_template_header (int specialization)
 722 {
 723   processing_specialization = specialization;
 724   template_header_count++;
 725 }
 726
 727 /* We're beginning an explicit instantiation.  */
 728
 729 void
 730 begin_explicit_instantiation (void)
 731 {
 732   gcc_assert (!processing_explicit_instantiation);
 733   processing_explicit_instantiation = true;
 734 }
 735
 736
 737 void
 738 end_explicit_instantiation (void)
 739 {
 740   gcc_assert (processing_explicit_instantiation);
 741   processing_explicit_instantiation = false;
 742 }
 743
 744 /* An explicit specialization or partial specialization TMPL is being
 745    declared.  Check that the namespace in which the specialization is
 746    occurring is permissible.  Returns false iff it is invalid to
 747    specialize TMPL in the current namespace.  */
 748
 749 static bool
 750 check_specialization_namespace (tree tmpl)
 751 {
 752   tree tpl_ns = decl_namespace_context (tmpl);
 753
 754   /* [tmpl.expl.spec]
 755
 756      An explicit specialization shall be declared in the namespace of
 757      which the template is a member, or, for member templates, in the
 758      namespace of which the enclosing class or enclosing class
 759      template is a member.  An explicit specialization of a member
 760      function, member class or static data member of a class template
 761      shall be declared in the namespace of which the class template is
 762      a member.  */
 763   if (current_scope() != DECL_CONTEXT (tmpl)
 764       && !at_namespace_scope_p ())
 765     {
 766       error ("specialization of %qD must appear at namespace scope", tmpl);
 767       return false;
 768     }
 769   if (is_associated_namespace (current_namespace, tpl_ns))
 770     /* Same or super-using namespace.  */
 771     return true;
 772   else
 773     {
 774       permerror (input_location, "specialization of %qD in different namespace", tmpl);
 775       permerror (input_location, "  from definition of %q+#D", tmpl);
 776       return false;
 777     }
 778 }
 779
 780 /* SPEC is an explicit instantiation.  Check that it is valid to
 781    perform this explicit instantiation in the current namespace.  */
 782
 783 static void
 784 check_explicit_instantiation_namespace (tree spec)
 785 {
 786   tree ns;
 787
 788   /* DR 275: An explicit instantiation shall appear in an enclosing
 789      namespace of its template.  */
 790   ns = decl_namespace_context (spec);
 791   if (!is_ancestor (current_namespace, ns))
 792     permerror (input_location, "explicit instantiation of %qD in namespace %qD "
 793                "(which does not enclose namespace %qD)",
 794                spec, current_namespace, ns);
 795 }
 796
 797 /* The TYPE is being declared.  If it is a template type, that means it
 798    is a partial specialization.  Do appropriate error-checking.  */
 799
 800 tree
 801 maybe_process_partial_specialization (tree type)
 802 {
 803   tree context;
 804
 805   if (type == error_mark_node)
 806     return error_mark_node;
 807
 808   if (TREE_CODE (type) == BOUND_TEMPLATE_TEMPLATE_PARM)
 809     {
 810       error ("name of class shadows template template parameter %qD",
 811              TYPE_NAME (type));
 812       return error_mark_node;
 813     }
 814
 815   context = TYPE_CONTEXT (type);
 816
 817   if ((CLASS_TYPE_P (type) && CLASSTYPE_USE_TEMPLATE (type))
 818       /* Consider non-class instantiations of alias templates as
 819          well.  */
 820       || (TYPE_P (type)
 821           && TYPE_TEMPLATE_INFO (type)
 822           && DECL_LANG_SPECIFIC (TYPE_NAME (type))
 823           && DECL_USE_TEMPLATE (TYPE_NAME (type))))
 824     {
 825       /* This is for ordinary explicit specialization and partial
 826          specialization of a template class such as:
 827
 828            template <> class C<int>;
 829
 830          or:
 831
 832            template <class T> class C<T*>;
 833
 834          Make sure that `C<int>' and `C<T*>' are implicit instantiations.  */
 835
 836       if (CLASS_TYPE_P (type)
 837           && CLASSTYPE_IMPLICIT_INSTANTIATION (type)
 838           && !COMPLETE_TYPE_P (type))
 839         {
 840           check_specialization_namespace (CLASSTYPE_TI_TEMPLATE (type));
 841           SET_CLASSTYPE_TEMPLATE_SPECIALIZATION (type);
 842           if (processing_template_decl)
 843             {
 844               if (push_template_decl (TYPE_MAIN_DECL (type))
 845                   == error_mark_node)
 846                 return error_mark_node;
 847             }
 848         }
 849       else if (CLASS_TYPE_P (type)
 850                && CLASSTYPE_TEMPLATE_INSTANTIATION (type))
 851         error ("specialization of %qT after instantiation", type);
 852
 853       if (DECL_ALIAS_TEMPLATE_P (TYPE_TI_TEMPLATE (type)))
 854         {
 855           error ("partial specialization of alias template %qD",
 856                  TYPE_TI_TEMPLATE (type));
 857           return error_mark_node;
 858         }
 859     }
 860   else if (CLASS_TYPE_P (type)
 861            && !CLASSTYPE_USE_TEMPLATE (type)
 862            && CLASSTYPE_TEMPLATE_INFO (type)
 863            && context && CLASS_TYPE_P (context)
 864            && CLASSTYPE_TEMPLATE_INFO (context))
 865     {
 866       /* This is for an explicit specialization of member class
 867          template according to [temp.expl.spec/18]:
 868
 869            template <> template <class U> class C<int>::D;
 870
 871          The context `C<int>' must be an implicit instantiation.
 872          Otherwise this is just a member class template declared
 873          earlier like:
 874
 875            template <> class C<int> { template <class U> class D; };
 876            template <> template <class U> class C<int>::D;
 877
 878          In the first case, `C<int>::D' is a specialization of `C<T>::D'
 879          while in the second case, `C<int>::D' is a primary template
 880          and `C<T>::D' may not exist.  */
 881
 882       if (CLASSTYPE_IMPLICIT_INSTANTIATION (context)
 883           && !COMPLETE_TYPE_P (type))
 884         {
 885           tree t;
 886           tree tmpl = CLASSTYPE_TI_TEMPLATE (type);
 887
 888           if (current_namespace
 889               != decl_namespace_context (tmpl))
 890             {
 891               permerror (input_location, "specializing %q#T in different namespace", type);
 892               permerror (input_location, "  from definition of %q+#D", tmpl);
 893             }
 894
 895           /* Check for invalid specialization after instantiation:
 896
 897                template <> template <> class C<int>::D<int>;
 898                template <> template <class U> class C<int>::D;  */
 899
 900           for (t = DECL_TEMPLATE_INSTANTIATIONS (tmpl);
 901                t; t = TREE_CHAIN (t))
 902             {
 903               tree inst = TREE_VALUE (t);
 904               if (CLASSTYPE_TEMPLATE_SPECIALIZATION (inst))
 905                 {
 906                   /* We already have a full specialization of this partial
 907                      instantiation.  Reassign it to the new member
 908                      specialization template.  */
 909                   spec_entry elt;
 910                   spec_entry *entry;
 911                   void **slot;
 912
 913                   elt.tmpl = most_general_template (tmpl);
 914                   elt.args = CLASSTYPE_TI_ARGS (inst);
 915                   elt.spec = inst;
 916
 917                   htab_remove_elt (type_specializations, &elt);
 918
 919                   elt.tmpl = tmpl;
 920                   elt.args = INNERMOST_TEMPLATE_ARGS (elt.args);
 921
 922                   slot = htab_find_slot (type_specializations, &elt, INSERT);
 923                   entry = ggc_alloc_spec_entry ();
 924                   *entry = elt;
 925                   *slot = entry;
 926                 }
 927               else if (COMPLETE_OR_OPEN_TYPE_P (inst))
 928                 /* But if we've had an implicit instantiation, that's a
 929                    problem ([temp.expl.spec]/6).  */
 930                 error ("specialization %qT after instantiation %qT",
 931                        type, inst);
 932             }
 933
 934           /* Mark TYPE as a specialization.  And as a result, we only
 935              have one level of template argument for the innermost
 936              class template.  */
 937           SET_CLASSTYPE_TEMPLATE_SPECIALIZATION (type);
 938           CLASSTYPE_TI_ARGS (type)
 939             = INNERMOST_TEMPLATE_ARGS (CLASSTYPE_TI_ARGS (type));
 940         }
 941     }
 942   else if (processing_specialization)
 943     {
 944        /* Someday C++0x may allow for enum template specialization.  */
 945       if (cxx_dialect > cxx98 && TREE_CODE (type) == ENUMERAL_TYPE
 946           && CLASS_TYPE_P (context) && CLASSTYPE_USE_TEMPLATE (context))
 947         pedwarn (input_location, OPT_pedantic, "template specialization "
 948                  "of %qD not allowed by ISO C++", type);
 949       else
 950         {
 951           error ("explicit specialization of non-template %qT", type);
 952           return error_mark_node;
 953         }
 954     }
 955
 956   return type;
 957 }
 958
 959 /* Returns nonzero if we can optimize the retrieval of specializations
 960    for TMPL, a TEMPLATE_DECL.  In particular, for such a template, we
 961    do not use DECL_TEMPLATE_SPECIALIZATIONS at all.  */
 962
 963 static inline bool
 964 optimize_specialization_lookup_p (tree tmpl)
 965 {
 966   return (DECL_FUNCTION_TEMPLATE_P (tmpl)
 967           && DECL_CLASS_SCOPE_P (tmpl)
 968           /* DECL_CLASS_SCOPE_P holds of T::f even if T is a template
 969              parameter.  */
 970           && CLASS_TYPE_P (DECL_CONTEXT (tmpl))
 971           /* The optimized lookup depends on the fact that the
 972              template arguments for the member function template apply
 973              purely to the containing class, which is not true if the
 974              containing class is an explicit or partial
 975              specialization.  */
 976           && !CLASSTYPE_TEMPLATE_SPECIALIZATION (DECL_CONTEXT (tmpl))
 977           && !DECL_MEMBER_TEMPLATE_P (tmpl)
 978           && !DECL_CONV_FN_P (tmpl)
 979           /* It is possible to have a template that is not a member
 980              template and is not a member of a template class:
 981
 982              template <typename T>
 983              struct S { friend A::f(); };
 984
 985              Here, the friend function is a template, but the context does
 986              not have template information.  The optimized lookup relies
 987              on having ARGS be the template arguments for both the class
 988              and the function template.  */
 989           && !DECL_FRIEND_P (DECL_TEMPLATE_RESULT (tmpl)));
 990 }
 991
 992 /* Retrieve the specialization (in the sense of [temp.spec] - a
 993    specialization is either an instantiation or an explicit
 994    specialization) of TMPL for the given template ARGS.  If there is
 995    no such specialization, return NULL_TREE.  The ARGS are a vector of
 996    arguments, or a vector of vectors of arguments, in the case of
 997    templates with more than one level of parameters.
 998
 999    If TMPL is a type template and CLASS_SPECIALIZATIONS_P is true,
1000    then we search for a partial specialization matching ARGS.  This
1001    parameter is ignored if TMPL is not a class template.  */
1002
1003 static tree
1004 retrieve_specialization (tree tmpl, tree args, hashval_t hash)
1005 {
1006   if (args == error_mark_node)
1007     return NULL_TREE;
1008
1009   gcc_assert (TREE_CODE (tmpl) == TEMPLATE_DECL);
1010
1011   /* There should be as many levels of arguments as there are
1012      levels of parameters.  */
1013   gcc_assert (TMPL_ARGS_DEPTH (args)
1014               == TMPL_PARMS_DEPTH (DECL_TEMPLATE_PARMS (tmpl)));
1015
1016   if (optimize_specialization_lookup_p (tmpl))
1017     {
1018       tree class_template;
1019       tree class_specialization;
1020       VEC(tree,gc) *methods;
1021       tree fns;
1022       int idx;
1023
1024       /* The template arguments actually apply to the containing
1025          class.  Find the class specialization with those
1026          arguments.  */
1027       class_template = CLASSTYPE_TI_TEMPLATE (DECL_CONTEXT (tmpl));
1028       class_specialization
1029         = retrieve_specialization (class_template, args, 0);
1030       if (!class_specialization)
1031         return NULL_TREE;
1032       /* Now, find the appropriate entry in the CLASSTYPE_METHOD_VEC
1033          for the specialization.  */
1034       idx = class_method_index_for_fn (class_specialization, tmpl);
1035       if (idx == -1)
1036         return NULL_TREE;
1037       /* Iterate through the methods with the indicated name, looking
1038          for the one that has an instance of TMPL.  */
1039       methods = CLASSTYPE_METHOD_VEC (class_specialization);
1040       for (fns = VEC_index (tree, methods, idx); fns; fns = OVL_NEXT (fns))
1041         {
1042           tree fn = OVL_CURRENT (fns);
1043           if (DECL_TEMPLATE_INFO (fn) && DECL_TI_TEMPLATE (fn) == tmpl
1044               /* using-declarations can add base methods to the method vec,
1045                  and we don't want those here.  */
1046               && DECL_CONTEXT (fn) == class_specialization)
1047             return fn;
1048         }
1049       return NULL_TREE;
1050     }
1051   else
1052     {
1053       spec_entry *found;
1054       spec_entry elt;
1055       htab_t specializations;
1056
1057       elt.tmpl = tmpl;
1058       elt.args = args;
1059       elt.spec = NULL_TREE;
1060
1061       if (DECL_CLASS_TEMPLATE_P (tmpl))
1062         specializations = type_specializations;
1063       else
1064         specializations = decl_specializations;
1065
1066       if (hash == 0)
1067         hash = hash_specialization (&elt);
1068       found = (spec_entry *) htab_find_with_hash (specializations, &elt, hash);
1069       if (found)
1070         return found->spec;
1071     }
1072
1073   return NULL_TREE;
1074 }
1075
1076 /* Like retrieve_specialization, but for local declarations.  */
1077
1078 static tree
1079 retrieve_local_specialization (tree tmpl)
1080 {
1081   tree spec;
1082
1083   if (local_specializations == NULL)
1084     return NULL_TREE;
1085
1086   spec = (tree) htab_find_with_hash (local_specializations, tmpl,
1087                                      htab_hash_pointer (tmpl));
1088   return spec ? TREE_PURPOSE (spec) : NULL_TREE;
1089 }
1090
1091 /* Returns nonzero iff DECL is a specialization of TMPL.  */
1092
1093 int
1094 is_specialization_of (tree decl, tree tmpl)
1095 {
1096   tree t;
1097
1098   if (TREE_CODE (decl) == FUNCTION_DECL)
1099     {
1100       for (t = decl;
1101            t != NULL_TREE;
1102            t = DECL_TEMPLATE_INFO (t) ? DECL_TI_TEMPLATE (t) : NULL_TREE)
1103         if (t == tmpl)
1104           return 1;
1105     }
1106   else
1107     {
1108       gcc_assert (TREE_CODE (decl) == TYPE_DECL);
1109
1110       for (t = TREE_TYPE (decl);
1111            t != NULL_TREE;
1112            t = CLASSTYPE_USE_TEMPLATE (t)
1113              ? TREE_TYPE (CLASSTYPE_TI_TEMPLATE (t)) : NULL_TREE)
1114         if (same_type_ignoring_top_level_qualifiers_p (t, TREE_TYPE (tmpl)))
1115           return 1;
1116     }
1117
1118   return 0;
1119 }
1120
1121 /* Returns nonzero iff DECL is a specialization of friend declaration
1122    FRIEND_DECL according to [temp.friend].  */
1123
1124 bool
1125 is_specialization_of_friend (tree decl, tree friend_decl)
1126 {
1127   bool need_template = true;
1128   int template_depth;
1129
1130   gcc_assert (TREE_CODE (decl) == FUNCTION_DECL
1131               || TREE_CODE (decl) == TYPE_DECL);
1132
1133   /* For [temp.friend/6] when FRIEND_DECL is an ordinary member function
1134      of a template class, we want to check if DECL is a specialization
1135      if this.  */
1136   if (TREE_CODE (friend_decl) == FUNCTION_DECL
1137       && DECL_TEMPLATE_INFO (friend_decl)
1138       && !DECL_USE_TEMPLATE (friend_decl))
1139     {
1140       /* We want a TEMPLATE_DECL for `is_specialization_of'.  */
1141       friend_decl = DECL_TI_TEMPLATE (friend_decl);
1142       need_template = false;
1143     }
1144   else if (TREE_CODE (friend_decl) == TEMPLATE_DECL
1145            && !PRIMARY_TEMPLATE_P (friend_decl))
1146     need_template = false;
1147
1148   /* There is nothing to do if this is not a template friend.  */
1149   if (TREE_CODE (friend_decl) != TEMPLATE_DECL)
1150     return false;
1151
1152   if (is_specialization_of (decl, friend_decl))
1153     return true;
1154
1155   /* [temp.friend/6]
1156      A member of a class template may be declared to be a friend of a
1157      non-template class.  In this case, the corresponding member of
1158      every specialization of the class template is a friend of the
1159      class granting friendship.
1160
1161      For example, given a template friend declaration
1162
1163        template <class T> friend void A<T>::f();
1164
1165      the member function below is considered a friend
1166
1167        template <> struct A<int> {
1168          void f();
1169        };
1170
1171      For this type of template friend, TEMPLATE_DEPTH below will be
1172      nonzero.  To determine if DECL is a friend of FRIEND, we first
1173      check if the enclosing class is a specialization of another.  */
1174
1175   template_depth = template_class_depth (CP_DECL_CONTEXT (friend_decl));
1176   if (template_depth
1177       && DECL_CLASS_SCOPE_P (decl)
1178       && is_specialization_of (TYPE_NAME (DECL_CONTEXT (decl)),
1179                                CLASSTYPE_TI_TEMPLATE (DECL_CONTEXT (friend_decl))))
1180     {
1181       /* Next, we check the members themselves.  In order to handle
1182          a few tricky cases, such as when FRIEND_DECL's are
1183
1184            template <class T> friend void A<T>::g(T t);
1185            template <class T> template <T t> friend void A<T>::h();
1186
1187          and DECL's are
1188
1189            void A<int>::g(int);
1190            template <int> void A<int>::h();
1191
1192          we need to figure out ARGS, the template arguments from
1193          the context of DECL.  This is required for template substitution
1194          of `T' in the function parameter of `g' and template parameter
1195          of `h' in the above examples.  Here ARGS corresponds to `int'.  */
1196
1197       tree context = DECL_CONTEXT (decl);
1198       tree args = NULL_TREE;
1199       int current_depth = 0;
1200
1201       while (current_depth < template_depth)
1202         {
1203           if (CLASSTYPE_TEMPLATE_INFO (context))
1204             {
1205               if (current_depth == 0)
1206                 args = TYPE_TI_ARGS (context);
1207               else
1208                 args = add_to_template_args (TYPE_TI_ARGS (context), args);
1209               current_depth++;
1210             }
1211           context = TYPE_CONTEXT (context);
1212         }
1213
1214       if (TREE_CODE (decl) == FUNCTION_DECL)
1215         {
1216           bool is_template;
1217           tree friend_type;
1218           tree decl_type;
1219           tree friend_args_type;
1220           tree decl_args_type;
1221
1222           /* Make sure that both DECL and FRIEND_DECL are templates or
1223              non-templates.  */
1224           is_template = DECL_TEMPLATE_INFO (decl)
1225                         && PRIMARY_TEMPLATE_P (DECL_TI_TEMPLATE (decl));
1226           if (need_template ^ is_template)
1227             return false;
1228           else if (is_template)
1229             {
1230               /* If both are templates, check template parameter list.  */
1231               tree friend_parms
1232                 = tsubst_template_parms (DECL_TEMPLATE_PARMS (friend_decl),
1233                                          args, tf_none);
1234               if (!comp_template_parms
1235                      (DECL_TEMPLATE_PARMS (DECL_TI_TEMPLATE (decl)),
1236                       friend_parms))
1237                 return false;
1238
1239               decl_type = TREE_TYPE (DECL_TI_TEMPLATE (decl));
1240             }
1241           else
1242             decl_type = TREE_TYPE (decl);
1243
1244           friend_type = tsubst_function_type (TREE_TYPE (friend_decl), args,
1245                                               tf_none, NULL_TREE);
1246           if (friend_type == error_mark_node)
1247             return false;
1248
1249           /* Check if return types match.  */
1250           if (!same_type_p (TREE_TYPE (decl_type), TREE_TYPE (friend_type)))
1251             return false;
1252
1253           /* Check if function parameter types match, ignoring the
1254              `this' parameter.  */
1255           friend_args_type = TYPE_ARG_TYPES (friend_type);
1256           decl_args_type = TYPE_ARG_TYPES (decl_type);
1257           if (DECL_NONSTATIC_MEMBER_FUNCTION_P (friend_decl))
1258             friend_args_type = TREE_CHAIN (friend_args_type);
1259           if (DECL_NONSTATIC_MEMBER_FUNCTION_P (decl))
1260             decl_args_type = TREE_CHAIN (decl_args_type);
1261
1262           return compparms (decl_args_type, friend_args_type);
1263         }
1264       else
1265         {
1266           /* DECL is a TYPE_DECL */
1267           bool is_template;
1268           tree decl_type = TREE_TYPE (decl);
1269
1270           /* Make sure that both DECL and FRIEND_DECL are templates or
1271              non-templates.  */
1272           is_template
1273             = CLASSTYPE_TEMPLATE_INFO (decl_type)
1274               && PRIMARY_TEMPLATE_P (CLASSTYPE_TI_TEMPLATE (decl_type));
1275
1276           if (need_template ^ is_template)
1277             return false;
1278           else if (is_template)
1279             {
1280               tree friend_parms;
1281               /* If both are templates, check the name of the two
1282                  TEMPLATE_DECL's first because is_friend didn't.  */
1283               if (DECL_NAME (CLASSTYPE_TI_TEMPLATE (decl_type))
1284                   != DECL_NAME (friend_decl))
1285                 return false;
1286
1287               /* Now check template parameter list.  */
1288               friend_parms
1289                 = tsubst_template_parms (DECL_TEMPLATE_PARMS (friend_decl),
1290                                          args, tf_none);
1291               return comp_template_parms
1292                 (DECL_TEMPLATE_PARMS (CLASSTYPE_TI_TEMPLATE (decl_type)),
1293                  friend_parms);
1294             }
1295           else
1296             return (DECL_NAME (decl)
1297                     == DECL_NAME (friend_decl));
1298         }
1299     }
1300   return false;
1301 }
1302
1303 /* Register the specialization SPEC as a specialization of TMPL with
1304    the indicated ARGS.  IS_FRIEND indicates whether the specialization
1305    is actually just a friend declaration.  Returns SPEC, or an
1306    equivalent prior declaration, if available.  */
1307
1308 static tree
1309 register_specialization (tree spec, tree tmpl, tree args, bool is_friend,
1310                          hashval_t hash)
1311 {
1312   tree fn;
1313   void **slot = NULL;
1314   spec_entry elt;
1315
1316   gcc_assert (TREE_CODE (tmpl) == TEMPLATE_DECL && DECL_P (spec));
1317
1318   if (TREE_CODE (spec) == FUNCTION_DECL
1319       && uses_template_parms (DECL_TI_ARGS (spec)))
1320     /* This is the FUNCTION_DECL for a partial instantiation.  Don't
1321        register it; we want the corresponding TEMPLATE_DECL instead.
1322        We use `uses_template_parms (DECL_TI_ARGS (spec))' rather than
1323        the more obvious `uses_template_parms (spec)' to avoid problems
1324        with default function arguments.  In particular, given
1325        something like this:
1326
1327           template <class T> void f(T t1, T t = T())
1328
1329        the default argument expression is not substituted for in an
1330        instantiation unless and until it is actually needed.  */
1331     return spec;
1332
1333   if (optimize_specialization_lookup_p (tmpl))
1334     /* We don't put these specializations in the hash table, but we might
1335        want to give an error about a mismatch.  */
1336     fn = retrieve_specialization (tmpl, args, 0);
1337   else
1338     {
1339       elt.tmpl = tmpl;
1340       elt.args = args;
1341       elt.spec = spec;
1342
1343       if (hash == 0)
1344         hash = hash_specialization (&elt);
1345
1346       slot =
1347         htab_find_slot_with_hash (decl_specializations, &elt, hash, INSERT);
1348       if (*slot)
1349         fn = ((spec_entry *) *slot)->spec;
1350       else
1351         fn = NULL_TREE;
1352     }
1353
1354   /* We can sometimes try to re-register a specialization that we've
1355      already got.  In particular, regenerate_decl_from_template calls
1356      duplicate_decls which will update the specialization list.  But,
1357      we'll still get called again here anyhow.  It's more convenient
1358      to simply allow this than to try to prevent it.  */
1359   if (fn == spec)
1360     return spec;
1361   else if (fn && DECL_TEMPLATE_SPECIALIZATION (spec))
1362     {
1363       if (DECL_TEMPLATE_INSTANTIATION (fn))
1364         {
1365           if (DECL_ODR_USED (fn)
1366               || DECL_EXPLICIT_INSTANTIATION (fn))
1367             {
1368               error ("specialization of %qD after instantiation",
1369                      fn);
1370               return error_mark_node;
1371             }
1372           else
1373             {
1374               tree clone;
1375               /* This situation should occur only if the first
1376                  specialization is an implicit instantiation, the
1377                  second is an explicit specialization, and the
1378                  implicit instantiation has not yet been used.  That
1379                  situation can occur if we have implicitly
1380                  instantiated a member function and then specialized
1381                  it later.
1382
1383                  We can also wind up here if a friend declaration that
1384                  looked like an instantiation turns out to be a
1385                  specialization:
1386
1387                    template <class T> void foo(T);
1388                    class S { friend void foo<>(int) };
1389                    template <> void foo(int);
1390
1391                  We transform the existing DECL in place so that any
1392                  pointers to it become pointers to the updated
1393                  declaration.
1394
1395                  If there was a definition for the template, but not
1396                  for the specialization, we want this to look as if
1397                  there were no definition, and vice versa.  */
1398               DECL_INITIAL (fn) = NULL_TREE;
1399               duplicate_decls (spec, fn, is_friend);
1400               /* The call to duplicate_decls will have applied
1401                  [temp.expl.spec]:
1402
1403                    An explicit specialization of a function template
1404                    is inline only if it is explicitly declared to be,
1405                    and independently of whether its function template
1406                    is.
1407
1408                 to the primary function; now copy the inline bits to
1409                 the various clones.  */
1410               FOR_EACH_CLONE (clone, fn)
1411                 {
1412                   DECL_DECLARED_INLINE_P (clone)
1413                     = DECL_DECLARED_INLINE_P (fn);
1414                   DECL_SOURCE_LOCATION (clone)
1415                     = DECL_SOURCE_LOCATION (fn);
1416                 }
1417               check_specialization_namespace (fn);
1418
1419               return fn;
1420             }
1421         }
1422       else if (DECL_TEMPLATE_SPECIALIZATION (fn))
1423         {
1424           if (!duplicate_decls (spec, fn, is_friend) && DECL_INITIAL (spec))
1425             /* Dup decl failed, but this is a new definition. Set the
1426                line number so any errors match this new
1427                definition.  */
1428             DECL_SOURCE_LOCATION (fn) = DECL_SOURCE_LOCATION (spec);
1429
1430           return fn;
1431         }
1432     }
1433   else if (fn)
1434     return duplicate_decls (spec, fn, is_friend);
1435
1436   /* A specialization must be declared in the same namespace as the
1437      template it is specializing.  */
1438   if (DECL_TEMPLATE_SPECIALIZATION (spec)
1439       && !check_specialization_namespace (tmpl))
1440     DECL_CONTEXT (spec) = DECL_CONTEXT (tmpl);
1441
1442   if (slot != NULL /* !optimize_specialization_lookup_p (tmpl) */)
1443     {
1444       spec_entry *entry = ggc_alloc_spec_entry ();
1445       gcc_assert (tmpl && args && spec);
1446       *entry = elt;
1447       *slot = entry;
1448       if (TREE_CODE (spec) == FUNCTION_DECL && DECL_NAMESPACE_SCOPE_P (spec)
1449           && PRIMARY_TEMPLATE_P (tmpl)
1450           && DECL_SAVED_TREE (DECL_TEMPLATE_RESULT (tmpl)) == NULL_TREE)
1451         /* TMPL is a forward declaration of a template function; keep a list
1452            of all specializations in case we need to reassign them to a friend
1453            template later in tsubst_friend_function.  */
1454         DECL_TEMPLATE_INSTANTIATIONS (tmpl)
1455           = tree_cons (args, spec, DECL_TEMPLATE_INSTANTIATIONS (tmpl));
1456     }
1457
1458   return spec;
1459 }
1460
1461 /* Returns true iff two spec_entry nodes are equivalent.  Only compares the
1462    TMPL and ARGS members, ignores SPEC.  */
1463
1464 static int
1465 eq_specializations (const void *p1, const void *p2)
1466 {
1467   const spec_entry *e1 = (const spec_entry *)p1;
1468   const spec_entry *e2 = (const spec_entry *)p2;
1469
1470   return (e1->tmpl == e2->tmpl
1471           && comp_template_args (e1->args, e2->args));
1472 }
1473
1474 /* Returns a hash for a template TMPL and template arguments ARGS.  */
1475
1476 static hashval_t
1477 hash_tmpl_and_args (tree tmpl, tree args)
1478 {
1479   hashval_t val = DECL_UID (tmpl);
1480   return iterative_hash_template_arg (args, val);
1481 }
1482
1483 /* Returns a hash for a spec_entry node based on the TMPL and ARGS members,
1484    ignoring SPEC.  */
1485
1486 static hashval_t
1487 hash_specialization (const void *p)
1488 {
1489   const spec_entry *e = (const spec_entry *)p;
1490   return hash_tmpl_and_args (e->tmpl, e->args);
1491 }
1492
1493 /* Recursively calculate a hash value for a template argument ARG, for use
1494    in the hash tables of template specializations.  */
1495
1496 hashval_t
1497 iterative_hash_template_arg (tree arg, hashval_t val)
1498 {
1499   unsigned HOST_WIDE_INT i;
1500   enum tree_code code;
1501   char tclass;
1502
1503   if (arg == NULL_TREE)
1504     return iterative_hash_object (arg, val);
1505
1506   if (!TYPE_P (arg))
1507     STRIP_NOPS (arg);
1508
1509   if (TREE_CODE (arg) == ARGUMENT_PACK_SELECT)
1510     /* We can get one of these when re-hashing a previous entry in the middle
1511        of substituting into a pack expansion.  Just look through it.  */
1512     arg = ARGUMENT_PACK_SELECT_FROM_PACK (arg);
1513
1514   code = TREE_CODE (arg);
1515   tclass = TREE_CODE_CLASS (code);
1516
1517   val = iterative_hash_object (code, val);
1518
1519   switch (code)
1520     {
1521     case ERROR_MARK:
1522       return val;
1523
1524     case IDENTIFIER_NODE:
1525       return iterative_hash_object (IDENTIFIER_HASH_VALUE (arg), val);
1526
1527     case TREE_VEC:
1528       {
1529         int i, len = TREE_VEC_LENGTH (arg);
1530         for (i = 0; i < len; ++i)
1531           val = iterative_hash_template_arg (TREE_VEC_ELT (arg, i), val);
1532         return val;
1533       }
1534
1535     case TYPE_PACK_EXPANSION:
1536     case EXPR_PACK_EXPANSION:
1537       return iterative_hash_template_arg (PACK_EXPANSION_PATTERN (arg), val);
1538
1539     case TYPE_ARGUMENT_PACK:
1540     case NONTYPE_ARGUMENT_PACK:
1541       return iterative_hash_template_arg (ARGUMENT_PACK_ARGS (arg), val);
1542
1543     case TREE_LIST:
1544       for (; arg; arg = TREE_CHAIN (arg))
1545         val = iterative_hash_template_arg (TREE_VALUE (arg), val);
1546       return val;
1547
1548     case OVERLOAD:
1549       for (; arg; arg = OVL_NEXT (arg))
1550         val = iterative_hash_template_arg (OVL_CURRENT (arg), val);
1551       return val;
1552
1553     case CONSTRUCTOR:
1554       {
1555         tree field, value;
1556         FOR_EACH_CONSTRUCTOR_ELT (CONSTRUCTOR_ELTS (arg), i, field, value)
1557           {
1558             val = iterative_hash_template_arg (field, val);
1559             val = iterative_hash_template_arg (value, val);
1560           }
1561         return val;
1562       }
1563
1564     case PARM_DECL:
1565       if (!DECL_ARTIFICIAL (arg))
1566         {
1567           val = iterative_hash_object (DECL_PARM_INDEX (arg), val);
1568           val = iterative_hash_object (DECL_PARM_LEVEL (arg), val);
1569         }
1570       return iterative_hash_template_arg (TREE_TYPE (arg), val);
1571
1572     case TARGET_EXPR:
1573       return iterative_hash_template_arg (TARGET_EXPR_INITIAL (arg), val);
1574
1575     case PTRMEM_CST:
1576       val = iterative_hash_template_arg (PTRMEM_CST_CLASS (arg), val);
1577       return iterative_hash_template_arg (PTRMEM_CST_MEMBER (arg), val);
1578
1579     case TEMPLATE_PARM_INDEX:
1580       val = iterative_hash_template_arg
1581         (TREE_TYPE (TEMPLATE_PARM_DECL (arg)), val);
1582       val = iterative_hash_object (TEMPLATE_PARM_LEVEL (arg), val);
1583       return iterative_hash_object (TEMPLATE_PARM_IDX (arg), val);
1584
1585     case TRAIT_EXPR:
1586       val = iterative_hash_object (TRAIT_EXPR_KIND (arg), val);
1587       val = iterative_hash_template_arg (TRAIT_EXPR_TYPE1 (arg), val);
1588       return iterative_hash_template_arg (TRAIT_EXPR_TYPE2 (arg), val);
1589
1590     case BASELINK:
1591       val = iterative_hash_template_arg (BINFO_TYPE (BASELINK_BINFO (arg)),
1592                                          val);
1593       return iterative_hash_template_arg (DECL_NAME (get_first_fn (arg)),
1594                                           val);
1595
1596     case MODOP_EXPR:
1597       val = iterative_hash_template_arg (TREE_OPERAND (arg, 0), val);
1598       code = TREE_CODE (TREE_OPERAND (arg, 1));
1599       val = iterative_hash_object (code, val);
1600       return iterative_hash_template_arg (TREE_OPERAND (arg, 2), val);
1601
1602     case LAMBDA_EXPR:
1603       /* A lambda can't appear in a template arg, but don't crash on
1604          erroneous input.  */
1605       gcc_assert (seen_error ());
1606       return val;
1607
1608     case CAST_EXPR:
1609     case IMPLICIT_CONV_EXPR:
1610     case STATIC_CAST_EXPR:
1611     case REINTERPRET_CAST_EXPR:
1612     case CONST_CAST_EXPR:
1613     case DYNAMIC_CAST_EXPR:
1614     case NEW_EXPR:
1615       val = iterative_hash_template_arg (TREE_TYPE (arg), val);
1616       /* Now hash operands as usual.  */
1617       break;
1618
1619     default:
1620       break;
1621     }
1622
1623   switch (tclass)
1624     {
1625     case tcc_type:
1626       if (TYPE_CANONICAL (arg))
1627         return iterative_hash_object (TYPE_HASH (TYPE_CANONICAL (arg)),
1628                                       val);
1629       else if (TREE_CODE (arg) == DECLTYPE_TYPE)
1630         return iterative_hash_template_arg (DECLTYPE_TYPE_EXPR (arg), val);
1631       /* Otherwise just compare the types during lookup.  */
1632       return val;
1633
1634     case tcc_declaration:
1635     case tcc_constant:
1636       return iterative_hash_expr (arg, val);
1637
1638     default:
1639       gcc_assert (IS_EXPR_CODE_CLASS (tclass));
1640       {
1641         unsigned n = cp_tree_operand_length (arg);
1642         for (i = 0; i < n; ++i)
1643           val = iterative_hash_template_arg (TREE_OPERAND (arg, i), val);
1644         return val;
1645       }
1646     }
1647   gcc_unreachable ();
1648   return 0;
1649 }
1650
1651 /* Unregister the specialization SPEC as a specialization of TMPL.
1652    Replace it with NEW_SPEC, if NEW_SPEC is non-NULL.  Returns true
1653    if the SPEC was listed as a specialization of TMPL.
1654
1655    Note that SPEC has been ggc_freed, so we can't look inside it.  */
1656
1657 bool
1658 reregister_specialization (tree spec, tree tinfo, tree new_spec)
1659 {
1660   spec_entry *entry;
1661   spec_entry elt;
1662
1663   elt.tmpl = most_general_template (TI_TEMPLATE (tinfo));
1664   elt.args = TI_ARGS (tinfo);
1665   elt.spec = NULL_TREE;
1666
1667   entry = (spec_entry *) htab_find (decl_specializations, &elt);
1668   if (entry != NULL)
1669     {
1670       gcc_assert (entry->spec == spec || entry->spec == new_spec);
1671       gcc_assert (new_spec != NULL_TREE);
1672       entry->spec = new_spec;
1673       return 1;
1674     }
1675
1676   return 0;
1677 }
1678
1679 /* Compare an entry in the local specializations hash table P1 (which
1680    is really a pointer to a TREE_LIST) with P2 (which is really a
1681    DECL).  */
1682
1683 static int
1684 eq_local_specializations (const void *p1, const void *p2)
1685 {
1686   return TREE_VALUE ((const_tree) p1) == (const_tree) p2;
1687 }
1688
1689 /* Hash P1, an entry in the local specializations table.  */
1690
1691 static hashval_t
1692 hash_local_specialization (const void* p1)
1693 {
1694   return htab_hash_pointer (TREE_VALUE ((const_tree) p1));
1695 }
1696
1697 /* Like register_specialization, but for local declarations.  We are
1698    registering SPEC, an instantiation of TMPL.  */
1699
1700 static void
1701 register_local_specialization (tree spec, tree tmpl)
1702 {
1703   void **slot;
1704
1705   slot = htab_find_slot_with_hash (local_specializations, tmpl,
1706                                    htab_hash_pointer (tmpl), INSERT);
1707   *slot = build_tree_list (spec, tmpl);
1708 }
1709
1710 /* TYPE is a class type.  Returns true if TYPE is an explicitly
1711    specialized class.  */
1712
1713 bool
1714 explicit_class_specialization_p (tree type)
1715 {
1716   if (!CLASSTYPE_TEMPLATE_SPECIALIZATION (type))
1717     return false;
1718   return !uses_template_parms (CLASSTYPE_TI_ARGS (type));
1719 }
1720
1721 /* Print the list of functions at FNS, going through all the overloads
1722    for each element of the list.  Alternatively, FNS can not be a
1723    TREE_LIST, in which case it will be printed together with all the
1724    overloads.
1725
1726    MORE and *STR should respectively be FALSE and NULL when the function
1727    is called from the outside.  They are used internally on recursive
1728    calls.  print_candidates manages the two parameters and leaves NULL
1729    in *STR when it ends.  */
1730
1731 static void
1732 print_candidates_1 (tree fns, bool more, const char **str)
1733 {
1734   tree fn, fn2;
1735   char *spaces = NULL;
1736
1737   for (fn = fns; fn; fn = OVL_NEXT (fn))
1738     if (TREE_CODE (fn) == TREE_LIST)
1739       {
1740         for (fn2 = fn; fn2 != NULL_TREE; fn2 = TREE_CHAIN (fn2))
1741           print_candidates_1 (TREE_VALUE (fn2),
1742                               TREE_CHAIN (fn2) || more, str);
1743       }
1744     else
1745       {
1746         if (!*str)
1747           {
1748             /* Pick the prefix string.  */
1749             if (!more && !OVL_NEXT (fns))
1750               {
1751                 error ("candidate is: %+#D", OVL_CURRENT (fn));
1752                 continue;
1753               }
1754
1755             *str = _("candidates are:");
1756             spaces = get_spaces (*str);
1757           }
1758         error ("%s %+#D", *str, OVL_CURRENT (fn));
1759         *str = spaces ? spaces : *str;
1760       }
1761
1762   if (!more)
1763     {
1764       free (spaces);
1765       *str = NULL;
1766     }
1767 }
1768
1769 /* Print the list of candidate FNS in an error message.  FNS can also
1770    be a TREE_LIST of non-functions in the case of an ambiguous lookup.  */
1771
1772 void
1773 print_candidates (tree fns)
1774 {
1775   const char *str = NULL;
1776   print_candidates_1 (fns, false, &str);
1777   gcc_assert (str == NULL);
1778 }
1779
1780 /* Returns the template (one of the functions given by TEMPLATE_ID)
1781    which can be specialized to match the indicated DECL with the
1782    explicit template args given in TEMPLATE_ID.  The DECL may be
1783    NULL_TREE if none is available.  In that case, the functions in
1784    TEMPLATE_ID are non-members.
1785
1786    If NEED_MEMBER_TEMPLATE is nonzero the function is known to be a
1787    specialization of a member template.
1788
1789    The TEMPLATE_COUNT is the number of references to qualifying
1790    template classes that appeared in the name of the function. See
1791    check_explicit_specialization for a more accurate description.
1792
1793    TSK indicates what kind of template declaration (if any) is being
1794    declared.  TSK_TEMPLATE indicates that the declaration given by
1795    DECL, though a FUNCTION_DECL, has template parameters, and is
1796    therefore a template function.
1797
1798    The template args (those explicitly specified and those deduced)
1799    are output in a newly created vector *TARGS_OUT.
1800
1801    If it is impossible to determine the result, an error message is
1802    issued.  The error_mark_node is returned to indicate failure.  */
1803
1804 static tree
1805 determine_specialization (tree template_id,
1806                           tree decl,
1807                           tree* targs_out,
1808                           int need_member_template,
1809                           int template_count,
1810                           tmpl_spec_kind tsk)
1811 {
1812   tree fns;
1813   tree targs;
1814   tree explicit_targs;
1815   tree candidates = NULL_TREE;
1816   /* A TREE_LIST of templates of which DECL may be a specialization.
1817      The TREE_VALUE of each node is a TEMPLATE_DECL.  The
1818      corresponding TREE_PURPOSE is the set of template arguments that,
1819      when used to instantiate the template, would produce a function
1820      with the signature of DECL.  */
1821   tree templates = NULL_TREE;
1822   int header_count;
1823   cp_binding_level *b;
1824
1825   *targs_out = NULL_TREE;
1826
1827   if (template_id == error_mark_node || decl == error_mark_node)
1828     return error_mark_node;
1829
1830   fns = TREE_OPERAND (template_id, 0);
1831   explicit_targs = TREE_OPERAND (template_id, 1);
1832
1833   if (fns == error_mark_node)
1834     return error_mark_node;
1835
1836   /* Check for baselinks.  */
1837   if (BASELINK_P (fns))
1838     fns = BASELINK_FUNCTIONS (fns);
1839
1840   if (!is_overloaded_fn (fns))
1841     {
1842       error ("%qD is not a function template", fns);
1843       return error_mark_node;
1844     }
1845
1846   /* Count the number of template headers specified for this
1847      specialization.  */
1848   header_count = 0;
1849   for (b = current_binding_level;
1850        b->kind == sk_template_parms;
1851        b = b->level_chain)
1852     ++header_count;
1853
1854   for (; fns; fns = OVL_NEXT (fns))
1855     {
1856       tree fn = OVL_CURRENT (fns);
1857
1858       if (TREE_CODE (fn) == TEMPLATE_DECL)
1859         {
1860           tree decl_arg_types;
1861           tree fn_arg_types;
1862
1863           /* In case of explicit specialization, we need to check if
1864              the number of template headers appearing in the specialization
1865              is correct. This is usually done in check_explicit_specialization,
1866              but the check done there cannot be exhaustive when specializing
1867              member functions. Consider the following code:
1868
1869              template <> void A<int>::f(int);
1870              template <> template <> void A<int>::f(int);
1871
1872              Assuming that A<int> is not itself an explicit specialization
1873              already, the first line specializes "f" which is a non-template
1874              member function, whilst the second line specializes "f" which
1875              is a template member function. So both lines are syntactically
1876              correct, and check_explicit_specialization does not reject
1877              them.
1878
1879              Here, we can do better, as we are matching the specialization
1880              against the declarations. We count the number of template
1881              headers, and we check if they match TEMPLATE_COUNT + 1
1882              (TEMPLATE_COUNT is the number of qualifying template classes,
1883              plus there must be another header for the member template
1884              itself).
1885
1886              Notice that if header_count is zero, this is not a
1887              specialization but rather a template instantiation, so there
1888              is no check we can perform here.  */
1889           if (header_count && header_count != template_count + 1)
1890             continue;
1891
1892           /* Check that the number of template arguments at the
1893              innermost level for DECL is the same as for FN.  */
1894           if (current_binding_level->kind == sk_template_parms
1895               && !current_binding_level->explicit_spec_p
1896               && (TREE_VEC_LENGTH (DECL_INNERMOST_TEMPLATE_PARMS (fn))
1897                   != TREE_VEC_LENGTH (INNERMOST_TEMPLATE_PARMS
1898                                       (current_template_parms))))
1899             continue;
1900
1901           /* DECL might be a specialization of FN.  */
1902           decl_arg_types = TYPE_ARG_TYPES (TREE_TYPE (decl));
1903           fn_arg_types = TYPE_ARG_TYPES (TREE_TYPE (fn));
1904
1905           /* For a non-static member function, we need to make sure
1906              that the const qualification is the same.  Since
1907              get_bindings does not try to merge the "this" parameter,
1908              we must do the comparison explicitly.  */
1909           if (DECL_NONSTATIC_MEMBER_FUNCTION_P (fn)
1910               && !same_type_p (TREE_VALUE (fn_arg_types),
1911                                TREE_VALUE (decl_arg_types)))
1912             continue;
1913
1914           /* Skip the "this" parameter and, for constructors of
1915              classes with virtual bases, the VTT parameter.  A
1916              full specialization of a constructor will have a VTT
1917              parameter, but a template never will.  */
1918           decl_arg_types
1919             = skip_artificial_parms_for (decl, decl_arg_types);
1920           fn_arg_types
1921             = skip_artificial_parms_for (fn, fn_arg_types);
1922
1923           /* Check that the number of function parameters matches.
1924              For example,
1925                template <class T> void f(int i = 0);
1926                template <> void f<int>();
1927              The specialization f<int> is invalid but is not caught
1928              by get_bindings below.  */
1929           if (list_length (fn_arg_types) != list_length (decl_arg_types))
1930             continue;
1931
1932           /* Function templates cannot be specializations; there are
1933              no partial specializations of functions.  Therefore, if
1934              the type of DECL does not match FN, there is no
1935              match.  */
1936           if (tsk == tsk_template)
1937             {
1938               if (compparms (fn_arg_types, decl_arg_types))
1939                 candidates = tree_cons (NULL_TREE, fn, candidates);
1940               continue;
1941             }
1942
1943           /* See whether this function might be a specialization of this
1944              template.  */
1945           targs = get_bindings (fn, decl, explicit_targs, /*check_ret=*/true);
1946
1947           if (!targs)
1948             /* We cannot deduce template arguments that when used to
1949                specialize TMPL will produce DECL.  */
1950             continue;
1951
1952           /* Save this template, and the arguments deduced.  */
1953           templates = tree_cons (targs, fn, templates);
1954         }
1955       else if (need_member_template)
1956         /* FN is an ordinary member function, and we need a
1957            specialization of a member template.  */
1958         ;
1959       else if (TREE_CODE (fn) != FUNCTION_DECL)
1960         /* We can get IDENTIFIER_NODEs here in certain erroneous
1961            cases.  */
1962         ;
1963       else if (!DECL_FUNCTION_MEMBER_P (fn))
1964         /* This is just an ordinary non-member function.  Nothing can
1965            be a specialization of that.  */
1966         ;
1967       else if (DECL_ARTIFICIAL (fn))
1968         /* Cannot specialize functions that are created implicitly.  */
1969         ;
1970       else
1971         {
1972           tree decl_arg_types;
1973
1974           /* This is an ordinary member function.  However, since
1975              we're here, we can assume it's enclosing class is a
1976              template class.  For example,
1977
1978                template <typename T> struct S { void f(); };
1979                template <> void S<int>::f() {}
1980
1981              Here, S<int>::f is a non-template, but S<int> is a
1982              template class.  If FN has the same type as DECL, we
1983              might be in business.  */
1984
1985           if (!DECL_TEMPLATE_INFO (fn))
1986             /* Its enclosing class is an explicit specialization
1987                of a template class.  This is not a candidate.  */
1988             continue;
1989
1990           if (!same_type_p (TREE_TYPE (TREE_TYPE (decl)),
1991                             TREE_TYPE (TREE_TYPE (fn))))
1992             /* The return types differ.  */
1993             continue;
1994
1995           /* Adjust the type of DECL in case FN is a static member.  */
1996           decl_arg_types = TYPE_ARG_TYPES (TREE_TYPE (decl));
1997           if (DECL_STATIC_FUNCTION_P (fn)
1998               && DECL_NONSTATIC_MEMBER_FUNCTION_P (decl))
1999             decl_arg_types = TREE_CHAIN (decl_arg_types);
2000
2001           if (compparms (TYPE_ARG_TYPES (TREE_TYPE (fn)),
2002                          decl_arg_types))
2003             /* They match!  */
2004             candidates = tree_cons (NULL_TREE, fn, candidates);
2005         }
2006     }
2007
2008   if (templates && TREE_CHAIN (templates))
2009     {
2010       /* We have:
2011
2012            [temp.expl.spec]
2013
2014            It is possible for a specialization with a given function
2015            signature to be instantiated from more than one function
2016            template.  In such cases, explicit specification of the
2017            template arguments must be used to uniquely identify the
2018            function template specialization being specialized.
2019
2020          Note that here, there's no suggestion that we're supposed to
2021          determine which of the candidate templates is most
2022          specialized.  However, we, also have:
2023
2024            [temp.func.order]
2025
2026            Partial ordering of overloaded function template
2027            declarations is used in the following contexts to select
2028            the function template to which a function template
2029            specialization refers:
2030
2031            -- when an explicit specialization refers to a function
2032               template.
2033
2034          So, we do use the partial ordering rules, at least for now.
2035          This extension can only serve to make invalid programs valid,
2036          so it's safe.  And, there is strong anecdotal evidence that
2037          the committee intended the partial ordering rules to apply;
2038          the EDG front end has that behavior, and John Spicer claims
2039          that the committee simply forgot to delete the wording in
2040          [temp.expl.spec].  */
2041       tree tmpl = most_specialized_instantiation (templates);
2042       if (tmpl != error_mark_node)
2043         {
2044           templates = tmpl;
2045           TREE_CHAIN (templates) = NULL_TREE;
2046         }
2047     }
2048
2049   if (templates == NULL_TREE && candidates == NULL_TREE)
2050     {
2051       error ("template-id %qD for %q+D does not match any template "
2052              "declaration", template_id, decl);
2053       if (header_count && header_count != template_count + 1)
2054         inform (input_location, "saw %d %<template<>%>, need %d for "
2055                 "specializing a member function template",
2056                 header_count, template_count + 1);
2057       return error_mark_node;
2058     }
2059   else if ((templates && TREE_CHAIN (templates))
2060            || (candidates && TREE_CHAIN (candidates))
2061            || (templates && candidates))
2062     {
2063       error ("ambiguous template specialization %qD for %q+D",
2064              template_id, decl);
2065       candidates = chainon (candidates, templates);
2066       print_candidates (candidates);
2067       return error_mark_node;
2068     }
2069
2070   /* We have one, and exactly one, match.  */
2071   if (candidates)
2072     {
2073       tree fn = TREE_VALUE (candidates);
2074       *targs_out = copy_node (DECL_TI_ARGS (fn));
2075       /* DECL is a re-declaration or partial instantiation of a template
2076          function.  */
2077       if (TREE_CODE (fn) == TEMPLATE_DECL)
2078         return fn;
2079       /* It was a specialization of an ordinary member function in a
2080          template class.  */
2081       return DECL_TI_TEMPLATE (fn);
2082     }
2083
2084   /* It was a specialization of a template.  */
2085   targs = DECL_TI_ARGS (DECL_TEMPLATE_RESULT (TREE_VALUE (templates)));
2086   if (TMPL_ARGS_HAVE_MULTIPLE_LEVELS (targs))
2087     {
2088       *targs_out = copy_node (targs);
2089       SET_TMPL_ARGS_LEVEL (*targs_out,
2090                            TMPL_ARGS_DEPTH (*targs_out),
2091                            TREE_PURPOSE (templates));
2092     }
2093   else
2094     *targs_out = TREE_PURPOSE (templates);
2095   return TREE_VALUE (templates);
2096 }
2097
2098 /* Returns a chain of parameter types, exactly like the SPEC_TYPES,
2099    but with the default argument values filled in from those in the
2100    TMPL_TYPES.  */
2101
2102 static tree
2103 copy_default_args_to_explicit_spec_1 (tree spec_types,
2104                                       tree tmpl_types)
2105 {
2106   tree new_spec_types;
2107
2108   if (!spec_types)
2109     return NULL_TREE;
2110
2111   if (spec_types == void_list_node)
2112     return void_list_node;
2113
2114   /* Substitute into the rest of the list.  */
2115   new_spec_types =
2116     copy_default_args_to_explicit_spec_1 (TREE_CHAIN (spec_types),
2117                                           TREE_CHAIN (tmpl_types));
2118
2119   /* Add the default argument for this parameter.  */
2120   return hash_tree_cons (TREE_PURPOSE (tmpl_types),
2121                          TREE_VALUE (spec_types),
2122                          new_spec_types);
2123 }
2124
2125 /* DECL is an explicit specialization.  Replicate default arguments
2126    from the template it specializes.  (That way, code like:
2127
2128      template <class T> void f(T = 3);
2129      template <> void f(double);
2130      void g () { f (); }
2131
2132    works, as required.)  An alternative approach would be to look up
2133    the correct default arguments at the call-site, but this approach
2134    is consistent with how implicit instantiations are handled.  */
2135
2136 static void
2137 copy_default_args_to_explicit_spec (tree decl)
2138 {
2139   tree tmpl;
2140   tree spec_types;
2141   tree tmpl_types;
2142   tree new_spec_types;
2143   tree old_type;
2144   tree new_type;
2145   tree t;
2146   tree object_type = NULL_TREE;
2147   tree in_charge = NULL_TREE;
2148   tree vtt = NULL_TREE;
2149
2150   /* See if there's anything we need to do.  */
2151   tmpl = DECL_TI_TEMPLATE (decl);
2152   tmpl_types = TYPE_ARG_TYPES (TREE_TYPE (DECL_TEMPLATE_RESULT (tmpl)));
2153   for (t = tmpl_types; t; t = TREE_CHAIN (t))
2154     if (TREE_PURPOSE (t))
2155       break;
2156   if (!t)
2157     return;
2158
2159   old_type = TREE_TYPE (decl);
2160   spec_types = TYPE_ARG_TYPES (old_type);
2161
2162   if (DECL_NONSTATIC_MEMBER_FUNCTION_P (decl))
2163     {
2164       /* Remove the this pointer, but remember the object's type for
2165          CV quals.  */
2166       object_type = TREE_TYPE (TREE_VALUE (spec_types));
2167       spec_types = TREE_CHAIN (spec_types);
2168       tmpl_types = TREE_CHAIN (tmpl_types);
2169
2170       if (DECL_HAS_IN_CHARGE_PARM_P (decl))
2171         {
2172           /* DECL may contain more parameters than TMPL due to the extra
2173              in-charge parameter in constructors and destructors.  */
2174           in_charge = spec_types;
2175           spec_types = TREE_CHAIN (spec_types);
2176         }
2177       if (DECL_HAS_VTT_PARM_P (decl))
2178         {
2179           vtt = spec_types;
2180           spec_types = TREE_CHAIN (spec_types);
2181         }
2182     }
2183
2184   /* Compute the merged default arguments.  */
2185   new_spec_types =
2186     copy_default_args_to_explicit_spec_1 (spec_types, tmpl_types);
2187
2188   /* Compute the new FUNCTION_TYPE.  */
2189   if (object_type)
2190     {
2191       if (vtt)
2192         new_spec_types = hash_tree_cons (TREE_PURPOSE (vtt),
2193                                          TREE_VALUE (vtt),
2194                                          new_spec_types);
2195
2196       if (in_charge)
2197         /* Put the in-charge parameter back.  */
2198         new_spec_types = hash_tree_cons (TREE_PURPOSE (in_charge),
2199                                          TREE_VALUE (in_charge),
2200                                          new_spec_types);
2201
2202       new_type = build_method_type_directly (object_type,
2203                                              TREE_TYPE (old_type),
2204                                              new_spec_types);
2205     }
2206   else
2207     new_type = build_function_type (TREE_TYPE (old_type),
2208                                     new_spec_types);
2209   new_type = cp_build_type_attribute_variant (new_type,
2210                                               TYPE_ATTRIBUTES (old_type));
2211   new_type = build_exception_variant (new_type,
2212                                       TYPE_RAISES_EXCEPTIONS (old_type));
2213   TREE_TYPE (decl) = new_type;
2214 }
2215
2216 /* Check to see if the function just declared, as indicated in
2217    DECLARATOR, and in DECL, is a specialization of a function
2218    template.  We may also discover that the declaration is an explicit
2219    instantiation at this point.
2220
2221    Returns DECL, or an equivalent declaration that should be used
2222    instead if all goes well.  Issues an error message if something is
2223    amiss.  Returns error_mark_node if the error is not easily
2224    recoverable.
2225
2226    FLAGS is a bitmask consisting of the following flags:
2227
2228    2: The function has a definition.
2229    4: The function is a friend.
2230
2231    The TEMPLATE_COUNT is the number of references to qualifying
2232    template classes that appeared in the name of the function.  For
2233    example, in
2234
2235      template <class T> struct S { void f(); };
2236      void S<int>::f();
2237
2238    the TEMPLATE_COUNT would be 1.  However, explicitly specialized
2239    classes are not counted in the TEMPLATE_COUNT, so that in
2240
2241      template <class T> struct S {};
2242      template <> struct S<int> { void f(); }
2243      template <> void S<int>::f();
2244
2245    the TEMPLATE_COUNT would be 0.  (Note that this declaration is
2246    invalid; there should be no template <>.)
2247
2248    If the function is a specialization, it is marked as such via
2249    DECL_TEMPLATE_SPECIALIZATION.  Furthermore, its DECL_TEMPLATE_INFO
2250    is set up correctly, and it is added to the list of specializations
2251    for that template.  */
2252
2253 tree
2254 check_explicit_specialization (tree declarator,
2255                                tree decl,
2256                                int template_count,
2257                                int flags)
2258 {
2259   int have_def = flags & 2;
2260   int is_friend = flags & 4;
2261   int specialization = 0;
2262   int explicit_instantiation = 0;
2263   int member_specialization = 0;
2264   tree ctype = DECL_CLASS_CONTEXT (decl);
2265   tree dname = DECL_NAME (decl);
2266   tmpl_spec_kind tsk;
2267
2268   if (is_friend)
2269     {
2270       if (!processing_specialization)
2271         tsk = tsk_none;
2272       else
2273         tsk = tsk_excessive_parms;
2274     }
2275   else
2276     tsk = current_tmpl_spec_kind (template_count);
2277
2278   switch (tsk)
2279     {
2280     case tsk_none:
2281       if (processing_specialization)
2282         {
2283           specialization = 1;
2284           SET_DECL_TEMPLATE_SPECIALIZATION (decl);
2285         }
2286       else if (TREE_CODE (declarator) == TEMPLATE_ID_EXPR)
2287         {
2288           if (is_friend)
2289             /* This could be something like:
2290
2291                template <class T> void f(T);
2292                class S { friend void f<>(int); }  */
2293             specialization = 1;
2294           else
2295             {
2296               /* This case handles bogus declarations like template <>
2297                  template <class T> void f<int>(); */
2298
2299               error ("template-id %qD in declaration of primary template",
2300                      declarator);
2301               return decl;
2302             }
2303         }
2304       break;
2305
2306     case tsk_invalid_member_spec:
2307       /* The error has already been reported in
2308          check_specialization_scope.  */
2309       return error_mark_node;
2310
2311     case tsk_invalid_expl_inst:
2312       error ("template parameter list used in explicit instantiation");
2313
2314       /* Fall through.  */
2315
2316     case tsk_expl_inst:
2317       if (have_def)
2318         error ("definition provided for explicit instantiation");
2319
2320       explicit_instantiation = 1;
2321       break;
2322
2323     case tsk_excessive_parms:
2324     case tsk_insufficient_parms:
2325       if (tsk == tsk_excessive_parms)
2326         error ("too many template parameter lists in declaration of %qD",
2327                decl);
2328       else if (template_header_count)
2329         error("too few template parameter lists in declaration of %qD", decl);
2330       else
2331         error("explicit specialization of %qD must be introduced by "
2332               "%<template <>%>", decl);
2333
2334       /* Fall through.  */
2335     case tsk_expl_spec:
2336       SET_DECL_TEMPLATE_SPECIALIZATION (decl);
2337       if (ctype)
2338         member_specialization = 1;
2339       else
2340         specialization = 1;
2341       break;
2342
2343     case tsk_template:
2344       if (TREE_CODE (declarator) == TEMPLATE_ID_EXPR)
2345         {
2346           /* This case handles bogus declarations like template <>
2347              template <class T> void f<int>(); */
2348
2349           if (uses_template_parms (declarator))
2350             error ("function template partial specialization %qD "
2351                    "is not allowed", declarator);
2352           else
2353             error ("template-id %qD in declaration of primary template",
2354                    declarator);
2355           return decl;
2356         }
2357
2358       if (ctype && CLASSTYPE_TEMPLATE_INSTANTIATION (ctype))
2359         /* This is a specialization of a member template, without
2360            specialization the containing class.  Something like:
2361
2362              template <class T> struct S {
2363                template <class U> void f (U);
2364              };
2365              template <> template <class U> void S<int>::f(U) {}
2366
2367            That's a specialization -- but of the entire template.  */
2368         specialization = 1;
2369       break;
2370
2371     default:
2372       gcc_unreachable ();
2373     }
2374
2375   if (specialization || member_specialization)
2376     {
2377       tree t = TYPE_ARG_TYPES (TREE_TYPE (decl));
2378       for (; t; t = TREE_CHAIN (t))
2379         if (TREE_PURPOSE (t))
2380           {
2381             permerror (input_location,
2382                        "default argument specified in explicit specialization");
2383             break;
2384           }
2385     }
2386
2387   if (specialization || member_specialization || explicit_instantiation)
2388     {
2389       tree tmpl = NULL_TREE;
2390       tree targs = NULL_TREE;
2391
2392       /* Make sure that the declarator is a TEMPLATE_ID_EXPR.  */
2393       if (TREE_CODE (declarator) != TEMPLATE_ID_EXPR)
2394         {
2395           tree fns;
2396
2397           gcc_assert (TREE_CODE (declarator) == IDENTIFIER_NODE);
2398           if (ctype)
2399             fns = dname;
2400           else
2401             {
2402               /* If there is no class context, the explicit instantiation
2403                  must be at namespace scope.  */
2404               gcc_assert (DECL_NAMESPACE_SCOPE_P (decl));
2405
2406               /* Find the namespace binding, using the declaration
2407                  context.  */
2408               fns = lookup_qualified_name (CP_DECL_CONTEXT (decl), dname,
2409                                            false, true);
2410               if (fns == error_mark_node || !is_overloaded_fn (fns))
2411                 {
2412                   error ("%qD is not a template function", dname);
2413                   fns = error_mark_node;
2414                 }
2415               else
2416                 {
2417                   tree fn = OVL_CURRENT (fns);
2418                   if (!is_associated_namespace (CP_DECL_CONTEXT (decl),
2419                                                 CP_DECL_CONTEXT (fn)))
2420                     error ("%qD is not declared in %qD",
2421                            decl, current_namespace);
2422                 }
2423             }
2424
2425           declarator = lookup_template_function (fns, NULL_TREE);
2426         }
2427
2428       if (declarator == error_mark_node)
2429         return error_mark_node;
2430
2431       if (ctype != NULL_TREE && TYPE_BEING_DEFINED (ctype))
2432         {
2433           if (!explicit_instantiation)
2434             /* A specialization in class scope.  This is invalid,
2435                but the error will already have been flagged by
2436                check_specialization_scope.  */
2437             return error_mark_node;
2438           else
2439             {
2440               /* It's not valid to write an explicit instantiation in
2441                  class scope, e.g.:
2442
2443                    class C { template void f(); }
2444
2445                    This case is caught by the parser.  However, on
2446                    something like:
2447
2448                    template class C { void f(); };
2449
2450                    (which is invalid) we can get here.  The error will be
2451                    issued later.  */
2452               ;
2453             }
2454
2455           return decl;
2456         }
2457       else if (ctype != NULL_TREE
2458                && (TREE_CODE (TREE_OPERAND (declarator, 0)) ==
2459                    IDENTIFIER_NODE))
2460         {
2461           /* Find the list of functions in ctype that have the same
2462              name as the declared function.  */
2463           tree name = TREE_OPERAND (declarator, 0);
2464           tree fns = NULL_TREE;
2465           int idx;
2466
2467           if (constructor_name_p (name, ctype))
2468             {
2469               int is_constructor = DECL_CONSTRUCTOR_P (decl);
2470
2471               if (is_constructor ? !TYPE_HAS_USER_CONSTRUCTOR (ctype)
2472                   : !CLASSTYPE_DESTRUCTORS (ctype))
2473                 {
2474                   /* From [temp.expl.spec]:
2475
2476                      If such an explicit specialization for the member
2477                      of a class template names an implicitly-declared
2478                      special member function (clause _special_), the
2479                      program is ill-formed.
2480
2481                      Similar language is found in [temp.explicit].  */
2482                   error ("specialization of implicitly-declared special member function");
2483                   return error_mark_node;
2484                 }
2485
2486               name = is_constructor ? ctor_identifier : dtor_identifier;
2487             }
2488
2489           if (!DECL_CONV_FN_P (decl))
2490             {
2491               idx = lookup_fnfields_1 (ctype, name);
2492               if (idx >= 0)
2493                 fns = VEC_index (tree, CLASSTYPE_METHOD_VEC (ctype), idx);
2494             }
2495           else
2496             {
2497               VEC(tree,gc) *methods;
2498               tree ovl;
2499
2500               /* For a type-conversion operator, we cannot do a
2501                  name-based lookup.  We might be looking for `operator
2502                  int' which will be a specialization of `operator T'.
2503                  So, we find *all* the conversion operators, and then
2504                  select from them.  */
2505               fns = NULL_TREE;
2506
2507               methods = CLASSTYPE_METHOD_VEC (ctype);
2508               if (methods)
2509                 for (idx = CLASSTYPE_FIRST_CONVERSION_SLOT;
2510                      VEC_iterate (tree, methods, idx, ovl);
2511                      ++idx)
2512                   {
2513                     if (!DECL_CONV_FN_P (OVL_CURRENT (ovl)))
2514                       /* There are no more conversion functions.  */
2515                       break;
2516
2517                     /* Glue all these conversion functions together
2518                        with those we already have.  */
2519                     for (; ovl; ovl = OVL_NEXT (ovl))
2520                       fns = ovl_cons (OVL_CURRENT (ovl), fns);
2521                   }
2522             }
2523
2524           if (fns == NULL_TREE)
2525             {
2526               error ("no member function %qD declared in %qT", name, ctype);
2527               return error_mark_node;
2528             }
2529           else
2530             TREE_OPERAND (declarator, 0) = fns;
2531         }
2532
2533       /* Figure out what exactly is being specialized at this point.
2534          Note that for an explicit instantiation, even one for a
2535          member function, we cannot tell apriori whether the
2536          instantiation is for a member template, or just a member
2537          function of a template class.  Even if a member template is
2538          being instantiated, the member template arguments may be
2539          elided if they can be deduced from the rest of the
2540          declaration.  */
2541       tmpl = determine_specialization (declarator, decl,
2542                                        &targs,
2543                                        member_specialization,
2544                                        template_count,
2545                                        tsk);
2546
2547       if (!tmpl || tmpl == error_mark_node)
2548         /* We couldn't figure out what this declaration was
2549            specializing.  */
2550         return error_mark_node;
2551       else
2552         {
2553           tree gen_tmpl = most_general_template (tmpl);
2554
2555           if (explicit_instantiation)
2556             {
2557               /* We don't set DECL_EXPLICIT_INSTANTIATION here; that
2558                  is done by do_decl_instantiation later.  */
2559
2560               int arg_depth = TMPL_ARGS_DEPTH (targs);
2561               int parm_depth = TMPL_PARMS_DEPTH (DECL_TEMPLATE_PARMS (tmpl));
2562
2563               if (arg_depth > parm_depth)
2564                 {
2565                   /* If TMPL is not the most general template (for
2566                      example, if TMPL is a friend template that is
2567                      injected into namespace scope), then there will
2568                      be too many levels of TARGS.  Remove some of them
2569                      here.  */
2570                   int i;
2571                   tree new_targs;
2572
2573                   new_targs = make_tree_vec (parm_depth);
2574                   for (i = arg_depth - parm_depth; i < arg_depth; ++i)
2575                     TREE_VEC_ELT (new_targs, i - (arg_depth - parm_depth))
2576                       = TREE_VEC_ELT (targs, i);
2577                   targs = new_targs;
2578                 }
2579
2580               return instantiate_template (tmpl, targs, tf_error);
2581             }
2582
2583           /* If we thought that the DECL was a member function, but it
2584              turns out to be specializing a static member function,
2585              make DECL a static member function as well.  */
2586           if (DECL_STATIC_FUNCTION_P (tmpl)
2587               && DECL_NONSTATIC_MEMBER_FUNCTION_P (decl))
2588             revert_static_member_fn (decl);
2589
2590           /* If this is a specialization of a member template of a
2591              template class, we want to return the TEMPLATE_DECL, not
2592              the specialization of it.  */
2593           if (tsk == tsk_template)
2594             {
2595               tree result = DECL_TEMPLATE_RESULT (tmpl);
2596               SET_DECL_TEMPLATE_SPECIALIZATION (tmpl);
2597               DECL_INITIAL (result) = NULL_TREE;
2598               if (have_def)
2599                 {
2600                   tree parm;
2601                   DECL_SOURCE_LOCATION (tmpl) = DECL_SOURCE_LOCATION (decl);
2602                   DECL_SOURCE_LOCATION (result)
2603                     = DECL_SOURCE_LOCATION (decl);
2604                   /* We want to use the argument list specified in the
2605                      definition, not in the original declaration.  */
2606                   DECL_ARGUMENTS (result) = DECL_ARGUMENTS (decl);
2607                   for (parm = DECL_ARGUMENTS (result); parm;
2608                        parm = DECL_CHAIN (parm))
2609                     DECL_CONTEXT (parm) = result;
2610                 }
2611               return register_specialization (tmpl, gen_tmpl, targs,
2612                                               is_friend, 0);
2613             }
2614
2615           /* Set up the DECL_TEMPLATE_INFO for DECL.  */
2616           DECL_TEMPLATE_INFO (decl) = build_template_info (tmpl, targs);
2617
2618           /* Inherit default function arguments from the template
2619              DECL is specializing.  */
2620           copy_default_args_to_explicit_spec (decl);
2621
2622           /* This specialization has the same protection as the
2623              template it specializes.  */
2624           TREE_PRIVATE (decl) = TREE_PRIVATE (gen_tmpl);
2625           TREE_PROTECTED (decl) = TREE_PROTECTED (gen_tmpl);
2626
2627           /* 7.1.1-1 [dcl.stc]
2628
2629              A storage-class-specifier shall not be specified in an
2630              explicit specialization...
2631
2632              The parser rejects these, so unless action is taken here,
2633              explicit function specializations will always appear with
2634              global linkage.
2635
2636              The action recommended by the C++ CWG in response to C++
2637              defect report 605 is to make the storage class and linkage
2638              of the explicit specialization match the templated function:
2639
2640              http://www.open-std.org/jtc1/sc22/wg21/docs/cwg_active.html#605
2641            */
2642           if (tsk == tsk_expl_spec && DECL_FUNCTION_TEMPLATE_P (gen_tmpl))
2643             {
2644               tree tmpl_func = DECL_TEMPLATE_RESULT (gen_tmpl);
2645               gcc_assert (TREE_CODE (tmpl_func) == FUNCTION_DECL);
2646
2647               /* This specialization has the same linkage and visibility as
2648                  the function template it specializes.  */
2649               TREE_PUBLIC (decl) = TREE_PUBLIC (tmpl_func);
2650               if (! TREE_PUBLIC (decl))
2651                 {
2652                   DECL_INTERFACE_KNOWN (decl) = 1;
2653                   DECL_NOT_REALLY_EXTERN (decl) = 1;
2654                 }
2655               DECL_THIS_STATIC (decl) = DECL_THIS_STATIC (tmpl_func);
2656               if (DECL_VISIBILITY_SPECIFIED (tmpl_func))
2657                 {
2658                   DECL_VISIBILITY_SPECIFIED (decl) = 1;
2659                   DECL_VISIBILITY (decl) = DECL_VISIBILITY (tmpl_func);
2660                 }
2661             }
2662
2663           /* If DECL is a friend declaration, declared using an
2664              unqualified name, the namespace associated with DECL may
2665              have been set incorrectly.  For example, in:
2666
2667                template <typename T> void f(T);
2668                namespace N {
2669                  struct S { friend void f<int>(int); }
2670                }
2671
2672              we will have set the DECL_CONTEXT for the friend
2673              declaration to N, rather than to the global namespace.  */
2674           if (DECL_NAMESPACE_SCOPE_P (decl))
2675             DECL_CONTEXT (decl) = DECL_CONTEXT (tmpl);
2676
2677           if (is_friend && !have_def)
2678             /* This is not really a declaration of a specialization.
2679                It's just the name of an instantiation.  But, it's not
2680                a request for an instantiation, either.  */
2681             SET_DECL_IMPLICIT_INSTANTIATION (decl);
2682           else if (DECL_CONSTRUCTOR_P (decl) || DECL_DESTRUCTOR_P (decl))
2683             /* This is indeed a specialization.  In case of constructors
2684                and destructors, we need in-charge and not-in-charge
2685                versions in V3 ABI.  */
2686             clone_function_decl (decl, /*update_method_vec_p=*/0);
2687
2688           /* Register this specialization so that we can find it
2689              again.  */
2690           decl = register_specialization (decl, gen_tmpl, targs, is_friend, 0);
2691         }
2692     }
2693
2694   return decl;
2695 }
2696
2697 /* Returns 1 iff PARMS1 and PARMS2 are identical sets of template
2698    parameters.  These are represented in the same format used for
2699    DECL_TEMPLATE_PARMS.  */
2700
2701 int
2702 comp_template_parms (const_tree parms1, const_tree parms2)
2703 {
2704   const_tree p1;
2705   const_tree p2;
2706
2707   if (parms1 == parms2)
2708     return 1;
2709
2710   for (p1 = parms1, p2 = parms2;
2711        p1 != NULL_TREE && p2 != NULL_TREE;
2712        p1 = TREE_CHAIN (p1), p2 = TREE_CHAIN (p2))
2713     {
2714       tree t1 = TREE_VALUE (p1);
2715       tree t2 = TREE_VALUE (p2);
2716       int i;
2717
2718       gcc_assert (TREE_CODE (t1) == TREE_VEC);
2719       gcc_assert (TREE_CODE (t2) == TREE_VEC);
2720
2721       if (TREE_VEC_LENGTH (t1) != TREE_VEC_LENGTH (t2))
2722         return 0;
2723
2724       for (i = 0; i < TREE_VEC_LENGTH (t2); ++i)
2725         {
2726           tree parm1 = TREE_VALUE (TREE_VEC_ELT (t1, i));
2727           tree parm2 = TREE_VALUE (TREE_VEC_ELT (t2, i));
2728
2729           /* If either of the template parameters are invalid, assume
2730              they match for the sake of error recovery. */
2731           if (parm1 == error_mark_node || parm2 == error_mark_node)
2732             return 1;
2733
2734           if (TREE_CODE (parm1) != TREE_CODE (parm2))
2735             return 0;
2736
2737           if (TREE_CODE (parm1) == TEMPLATE_TYPE_PARM
2738               && (TEMPLATE_TYPE_PARAMETER_PACK (parm1)
2739                   == TEMPLATE_TYPE_PARAMETER_PACK (parm2)))
2740             continue;
2741           else if (!same_type_p (TREE_TYPE (parm1), TREE_TYPE (parm2)))
2742             return 0;
2743         }
2744     }
2745
2746   if ((p1 != NULL_TREE) != (p2 != NULL_TREE))
2747     /* One set of parameters has more parameters lists than the
2748        other.  */
2749     return 0;
2750
2751   return 1;
2752 }
2753
2754 /* Determine whether PARM is a parameter pack.  */
2755
2756 bool
2757 template_parameter_pack_p (const_tree parm)
2758 {
2759   /* Determine if we have a non-type template parameter pack.  */
2760   if (TREE_CODE (parm) == PARM_DECL)
2761     return (DECL_TEMPLATE_PARM_P (parm)
2762             && TEMPLATE_PARM_PARAMETER_PACK (DECL_INITIAL (parm)));
2763   if (TREE_CODE (parm) == TEMPLATE_PARM_INDEX)
2764     return TEMPLATE_PARM_PARAMETER_PACK (parm);
2765
2766   /* If this is a list of template parameters, we could get a
2767      TYPE_DECL or a TEMPLATE_DECL.  */
2768   if (TREE_CODE (parm) == TYPE_DECL || TREE_CODE (parm) == TEMPLATE_DECL)
2769     parm = TREE_TYPE (parm);
2770
2771   /* Otherwise it must be a type template parameter.  */
2772   return ((TREE_CODE (parm) == TEMPLATE_TYPE_PARM
2773            || TREE_CODE (parm) == TEMPLATE_TEMPLATE_PARM)
2774           && TEMPLATE_TYPE_PARAMETER_PACK (parm));
2775 }
2776
2777 /* Determine if T is a function parameter pack.  */
2778
2779 bool
2780 function_parameter_pack_p (const_tree t)
2781 {
2782   if (t && TREE_CODE (t) == PARM_DECL)
2783     return FUNCTION_PARAMETER_PACK_P (t);
2784   return false;
2785 }
2786
2787 /* Return the function template declaration of PRIMARY_FUNC_TMPL_INST.
2788    PRIMARY_FUNC_TMPL_INST is a primary function template instantiation.  */
2789
2790 tree
2791 get_function_template_decl (const_tree primary_func_tmpl_inst)
2792 {
2793   if (! primary_func_tmpl_inst
2794       || TREE_CODE (primary_func_tmpl_inst) != FUNCTION_DECL
2795       || ! primary_template_instantiation_p (primary_func_tmpl_inst))
2796     return NULL;
2797
2798   return DECL_TEMPLATE_RESULT (DECL_TI_TEMPLATE (primary_func_tmpl_inst));
2799 }
2800
2801 /* Return true iff the function parameter PARAM_DECL was expanded
2802    from the function parameter pack PACK.  */
2803
2804 bool
2805 function_parameter_expanded_from_pack_p (tree param_decl, tree pack)
2806 {
2807   if (DECL_ARTIFICIAL (param_decl)
2808       || !function_parameter_pack_p (pack))
2809     return false;
2810
2811   /* The parameter pack and its pack arguments have the same
2812      DECL_PARM_INDEX.  */
2813   return DECL_PARM_INDEX (pack) == DECL_PARM_INDEX (param_decl);
2814 }
2815
2816 /* Determine whether ARGS describes a variadic template args list,
2817    i.e., one that is terminated by a template argument pack.  */
2818
2819 static bool
2820 template_args_variadic_p (tree args)
2821 {
2822   int nargs;
2823   tree last_parm;
2824
2825   if (args == NULL_TREE)
2826     return false;
2827
2828   args = INNERMOST_TEMPLATE_ARGS (args);
2829   nargs = TREE_VEC_LENGTH (args);
2830
2831   if (nargs == 0)
2832     return false;
2833
2834   last_parm = TREE_VEC_ELT (args, nargs - 1);
2835
2836   return ARGUMENT_PACK_P (last_parm);
2837 }
2838
2839 /* Generate a new name for the parameter pack name NAME (an
2840    IDENTIFIER_NODE) that incorporates its */
2841
2842 static tree
2843 make_ith_pack_parameter_name (tree name, int i)
2844 {
2845   /* Munge the name to include the parameter index.  */
2846 #define NUMBUF_LEN 128
2847   char numbuf[NUMBUF_LEN];
2848   char* newname;
2849   int newname_len;
2850
2851   snprintf (numbuf, NUMBUF_LEN, "%i", i);
2852   newname_len = IDENTIFIER_LENGTH (name)
2853                 + strlen (numbuf) + 2;
2854   newname = (char*)alloca (newname_len);
2855   snprintf (newname, newname_len,
2856             "%s#%i", IDENTIFIER_POINTER (name), i);
2857   return get_identifier (newname);
2858 }
2859
2860 /* Return true if T is a primary function, class or alias template
2861    instantiation.  */
2862
2863 bool
2864 primary_template_instantiation_p (const_tree t)
2865 {
2866   if (!t)
2867     return false;
2868
2869   if (TREE_CODE (t) == FUNCTION_DECL)
2870     return DECL_LANG_SPECIFIC (t)
2871            && DECL_TEMPLATE_INSTANTIATION (t)
2872            && PRIMARY_TEMPLATE_P (DECL_TI_TEMPLATE (t));
2873   else if (CLASS_TYPE_P (t) && !TYPE_DECL_ALIAS_P (TYPE_NAME (t)))
2874     return CLASSTYPE_TEMPLATE_INSTANTIATION (t)
2875            && PRIMARY_TEMPLATE_P (CLASSTYPE_TI_TEMPLATE (t));
2876   else if (TYPE_P (t)
2877            && TYPE_TEMPLATE_INFO (t)
2878            && PRIMARY_TEMPLATE_P (TYPE_TI_TEMPLATE (t))
2879            && DECL_TEMPLATE_INSTANTIATION (TYPE_NAME (t)))
2880     return true;
2881   return false;
2882 }
2883
2884 /* Return true if PARM is a template template parameter.  */
2885
2886 bool
2887 template_template_parameter_p (const_tree parm)
2888 {
2889   return DECL_TEMPLATE_TEMPLATE_PARM_P (parm);
2890 }
2891
2892 /* Return the template parameters of T if T is a
2893    primary template instantiation, NULL otherwise.  */
2894
2895 tree
2896 get_primary_template_innermost_parameters (const_tree t)
2897 {
2898   tree parms = NULL, template_info = NULL;
2899
2900   if ((template_info = get_template_info (t))
2901       && primary_template_instantiation_p (t))
2902     parms = INNERMOST_TEMPLATE_PARMS
2903         (DECL_TEMPLATE_PARMS (TI_TEMPLATE (template_info)));
2904
2905   return parms;
2906 }
2907
2908 /* Return the template parameters of the LEVELth level from the full list
2909    of template parameters PARMS.  */
2910
2911 tree
2912 get_template_parms_at_level (tree parms, int level)
2913 {
2914   tree p;
2915   if (!parms
2916       || TREE_CODE (parms) != TREE_LIST
2917       || level > TMPL_PARMS_DEPTH (parms))
2918     return NULL_TREE;
2919
2920   for (p = parms; p; p = TREE_CHAIN (p))
2921     if (TMPL_PARMS_DEPTH (p) == level)
2922       return p;
2923
2924   return NULL_TREE;
2925 }
2926
2927 /* Returns the template arguments of T if T is a template instantiation,
2928    NULL otherwise.  */
2929
2930 tree
2931 get_template_innermost_arguments (const_tree t)
2932 {
2933   tree args = NULL, template_info = NULL;
2934
2935   if ((template_info = get_template_info (t))
2936       && TI_ARGS (template_info))
2937     args = INNERMOST_TEMPLATE_ARGS (TI_ARGS (template_info));
2938
2939   return args;
2940 }
2941
2942 /* Return the argument pack elements of T if T is a template argument pack,
2943    NULL otherwise.  */
2944
2945 tree
2946 get_template_argument_pack_elems (const_tree t)
2947 {
2948   if (TREE_CODE (t) != TYPE_ARGUMENT_PACK
2949       && TREE_CODE (t) != NONTYPE_ARGUMENT_PACK)
2950     return NULL;
2951
2952   return ARGUMENT_PACK_ARGS (t);
2953 }
2954
2955 /* Structure used to track the progress of find_parameter_packs_r.  */
2956 struct find_parameter_pack_data
2957 {
2958   /* TREE_LIST that will contain all of the parameter packs found by
2959      the traversal.  */
2960   tree* parameter_packs;
2961
2962   /* Set of AST nodes that have been visited by the traversal.  */
2963   struct pointer_set_t *visited;
2964 };
2965
2966 /* Identifies all of the argument packs that occur in a template
2967    argument and appends them to the TREE_LIST inside DATA, which is a
2968    find_parameter_pack_data structure. This is a subroutine of
2969    make_pack_expansion and uses_parameter_packs.  */
2970 static tree
2971 find_parameter_packs_r (tree *tp, int *walk_subtrees, void* data)
2972 {
2973   tree t = *tp;
2974   struct find_parameter_pack_data* ppd =
2975     (struct find_parameter_pack_data*)data;
2976   bool parameter_pack_p = false;
2977
2978   /* Identify whether this is a parameter pack or not.  */
2979   switch (TREE_CODE (t))
2980     {
2981     case TEMPLATE_PARM_INDEX:
2982       if (TEMPLATE_PARM_PARAMETER_PACK (t))
2983         parameter_pack_p = true;
2984       break;
2985
2986     case TEMPLATE_TYPE_PARM:
2987       t = TYPE_MAIN_VARIANT (t);
2988     case TEMPLATE_TEMPLATE_PARM:
2989       if (TEMPLATE_TYPE_PARAMETER_PACK (t))
2990         parameter_pack_p = true;
2991       break;
2992
2993     case PARM_DECL:
2994       if (FUNCTION_PARAMETER_PACK_P (t))
2995         {
2996           /* We don't want to walk into the type of a PARM_DECL,
2997              because we don't want to see the type parameter pack.  */
2998           *walk_subtrees = 0;
2999           parameter_pack_p = true;
3000         }
3001       break;
3002
3003     case BASES:
3004       parameter_pack_p = true;
3005       break;
3006     default:
3007       /* Not a parameter pack.  */
3008       break;
3009     }
3010
3011   if (parameter_pack_p)
3012     {
3013       /* Add this parameter pack to the list.  */
3014       *ppd->parameter_packs = tree_cons (NULL_TREE, t, *ppd->parameter_packs);
3015     }
3016
3017   if (TYPE_P (t))
3018     cp_walk_tree (&TYPE_CONTEXT (t),
3019                   &find_parameter_packs_r, ppd, ppd->visited);
3020
3021   /* This switch statement will return immediately if we don't find a
3022      parameter pack.  */
3023   switch (TREE_CODE (t))
3024     {
3025     case TEMPLATE_PARM_INDEX:
3026       return NULL_TREE;
3027
3028     case BOUND_TEMPLATE_TEMPLATE_PARM:
3029       /* Check the template itself.  */
3030       cp_walk_tree (&TREE_TYPE (TYPE_TI_TEMPLATE (t)),
3031                     &find_parameter_packs_r, ppd, ppd->visited);
3032       /* Check the template arguments.  */
3033       cp_walk_tree (&TYPE_TI_ARGS (t), &find_parameter_packs_r, ppd,
3034                     ppd->visited);
3035       *walk_subtrees = 0;
3036       return NULL_TREE;
3037
3038     case TEMPLATE_TYPE_PARM:
3039     case TEMPLATE_TEMPLATE_PARM:
3040       return NULL_TREE;
3041
3042     case PARM_DECL:
3043       return NULL_TREE;
3044
3045     case RECORD_TYPE:
3046       if (TYPE_PTRMEMFUNC_P (t))
3047         return NULL_TREE;
3048       /* Fall through.  */
3049
3050     case UNION_TYPE:
3051     case ENUMERAL_TYPE:
3052       if (TYPE_TEMPLATE_INFO (t))
3053         cp_walk_tree (&TI_ARGS (TYPE_TEMPLATE_INFO (t)),
3054                       &find_parameter_packs_r, ppd, ppd->visited);
3055
3056       *walk_subtrees = 0;
3057       return NULL_TREE;
3058
3059     case CONSTRUCTOR:
3060     case TEMPLATE_DECL:
3061       cp_walk_tree (&TREE_TYPE (t),
3062                     &find_parameter_packs_r, ppd, ppd->visited);
3063       return NULL_TREE;
3064
3065     case TYPENAME_TYPE:
3066       cp_walk_tree (&TYPENAME_TYPE_FULLNAME (t), &find_parameter_packs_r,
3067                    ppd, ppd->visited);
3068       *walk_subtrees = 0;
3069       return NULL_TREE;
3070
3071     case TYPE_PACK_EXPANSION:
3072     case EXPR_PACK_EXPANSION:
3073       *walk_subtrees = 0;
3074       return NULL_TREE;
3075
3076     case INTEGER_TYPE:
3077       cp_walk_tree (&TYPE_MAX_VALUE (t), &find_parameter_packs_r,
3078                     ppd, ppd->visited);
3079       *walk_subtrees = 0;
3080       return NULL_TREE;
3081
3082     case IDENTIFIER_NODE:
3083       cp_walk_tree (&TREE_TYPE (t), &find_parameter_packs_r, ppd,
3084                     ppd->visited);
3085       *walk_subtrees = 0;
3086       return NULL_TREE;
3087
3088     default:
3089       return NULL_TREE;
3090     }
3091
3092   return NULL_TREE;
3093 }
3094
3095 /* Determines if the expression or type T uses any parameter packs.  */
3096 bool
3097 uses_parameter_packs (tree t)
3098 {
3099   tree parameter_packs = NULL_TREE;
3100   struct find_parameter_pack_data ppd;
3101   ppd.parameter_packs = &parameter_packs;
3102   ppd.visited = pointer_set_create ();
3103   cp_walk_tree (&t, &find_parameter_packs_r, &ppd, ppd.visited);
3104   pointer_set_destroy (ppd.visited);
3105   return parameter_packs != NULL_TREE;
3106 }
3107
3108 /* Turn ARG, which may be an expression, type, or a TREE_LIST
3109    representation a base-class initializer into a parameter pack
3110    expansion. If all goes well, the resulting node will be an
3111    EXPR_PACK_EXPANSION, TYPE_PACK_EXPANSION, or TREE_LIST,
3112    respectively.  */
3113 tree
3114 make_pack_expansion (tree arg)
3115 {
3116   tree result;
3117   tree parameter_packs = NULL_TREE;
3118   bool for_types = false;
3119   struct find_parameter_pack_data ppd;
3120
3121   if (!arg || arg == error_mark_node)
3122     return arg;
3123
3124   if (TREE_CODE (arg) == TREE_LIST)
3125     {
3126       /* The only time we will see a TREE_LIST here is for a base
3127          class initializer.  In this case, the TREE_PURPOSE will be a
3128          _TYPE node (representing the base class expansion we're
3129          initializing) and the TREE_VALUE will be a TREE_LIST
3130          containing the initialization arguments.
3131
3132          The resulting expansion looks somewhat different from most
3133          expansions. Rather than returning just one _EXPANSION, we
3134          return a TREE_LIST whose TREE_PURPOSE is a
3135          TYPE_PACK_EXPANSION containing the bases that will be
3136          initialized.  The TREE_VALUE will be identical to the
3137          original TREE_VALUE, which is a list of arguments that will
3138          be passed to each base.  We do not introduce any new pack
3139          expansion nodes into the TREE_VALUE (although it is possible
3140          that some already exist), because the TREE_PURPOSE and
3141          TREE_VALUE all need to be expanded together with the same
3142          _EXPANSION node.  Note that the TYPE_PACK_EXPANSION in the
3143          resulting TREE_PURPOSE will mention the parameter packs in
3144          both the bases and the arguments to the bases.  */
3145       tree purpose;
3146       tree value;
3147       tree parameter_packs = NULL_TREE;
3148
3149       /* Determine which parameter packs will be used by the base
3150          class expansion.  */
3151       ppd.visited = pointer_set_create ();
3152       ppd.parameter_packs = &parameter_packs;
3153       cp_walk_tree (&TREE_PURPOSE (arg), &find_parameter_packs_r,
3154                     &ppd, ppd.visited);
3155
3156       if (parameter_packs == NULL_TREE)
3157         {
3158           error ("base initializer expansion %<%T%> contains no parameter packs", arg);
3159           pointer_set_destroy (ppd.visited);
3160           return error_mark_node;
3161         }
3162
3163       if (TREE_VALUE (arg) != void_type_node)
3164         {
3165           /* Collect the sets of parameter packs used in each of the
3166              initialization arguments.  */
3167           for (value = TREE_VALUE (arg); value; value = TREE_CHAIN (value))
3168             {
3169               /* Determine which parameter packs will be expanded in this
3170                  argument.  */
3171               cp_walk_tree (&TREE_VALUE (value), &find_parameter_packs_r,
3172                             &ppd, ppd.visited);
3173             }
3174         }
3175
3176       pointer_set_destroy (ppd.visited);
3177
3178       /* Create the pack expansion type for the base type.  */
3179       purpose = cxx_make_type (TYPE_PACK_EXPANSION);
3180       SET_PACK_EXPANSION_PATTERN (purpose, TREE_PURPOSE (arg));
3181       PACK_EXPANSION_PARAMETER_PACKS (purpose) = parameter_packs;
3182
3183       /* Just use structural equality for these TYPE_PACK_EXPANSIONS;
3184          they will rarely be compared to anything.  */
3185       SET_TYPE_STRUCTURAL_EQUALITY (purpose);
3186
3187       return tree_cons (purpose, TREE_VALUE (arg), NULL_TREE);
3188     }
3189
3190   if (TYPE_P (arg) || TREE_CODE (arg) == TEMPLATE_DECL)
3191     for_types = true;
3192
3193   /* Build the PACK_EXPANSION_* node.  */
3194   result = for_types
3195      ? cxx_make_type (TYPE_PACK_EXPANSION)
3196      : make_node (EXPR_PACK_EXPANSION);
3197   SET_PACK_EXPANSION_PATTERN (result, arg);
3198   if (TREE_CODE (result) == EXPR_PACK_EXPANSION)
3199     {
3200       /* Propagate type and const-expression information.  */
3201       TREE_TYPE (result) = TREE_TYPE (arg);
3202       TREE_CONSTANT (result) = TREE_CONSTANT (arg);
3203     }
3204   else
3205     /* Just use structural equality for these TYPE_PACK_EXPANSIONS;
3206        they will rarely be compared to anything.  */
3207     SET_TYPE_STRUCTURAL_EQUALITY (result);
3208
3209   /* Determine which parameter packs will be expanded.  */
3210   ppd.parameter_packs = &parameter_packs;
3211   ppd.visited = pointer_set_create ();
3212   cp_walk_tree (&arg, &find_parameter_packs_r, &ppd, ppd.visited);
3213   pointer_set_destroy (ppd.visited);
3214
3215   /* Make sure we found some parameter packs.  */
3216   if (parameter_packs == NULL_TREE)
3217     {
3218       if (TYPE_P (arg))
3219         error ("expansion pattern %<%T%> contains no argument packs", arg);
3220       else
3221         error ("expansion pattern %<%E%> contains no argument packs", arg);
3222       return error_mark_node;
3223     }
3224   PACK_EXPANSION_PARAMETER_PACKS (result) = parameter_packs;
3225
3226   return result;
3227 }
3228
3229 /* Checks T for any "bare" parameter packs, which have not yet been
3230    expanded, and issues an error if any are found. This operation can
3231    only be done on full expressions or types (e.g., an expression
3232    statement, "if" condition, etc.), because we could have expressions like:
3233
3234      foo(f(g(h(args)))...)
3235
3236    where "args" is a parameter pack. check_for_bare_parameter_packs
3237    should not be called for the subexpressions args, h(args),
3238    g(h(args)), or f(g(h(args))), because we would produce erroneous
3239    error messages.
3240
3241    Returns TRUE and emits an error if there were bare parameter packs,
3242    returns FALSE otherwise.  */
3243 bool
3244 check_for_bare_parameter_packs (tree t)
3245 {
3246   tree parameter_packs = NULL_TREE;
3247   struct find_parameter_pack_data ppd;
3248
3249   if (!processing_template_decl || !t || t == error_mark_node)
3250     return false;
3251
3252   if (TREE_CODE (t) == TYPE_DECL)
3253     t = TREE_TYPE (t);
3254
3255   ppd.parameter_packs = &parameter_packs;
3256   ppd.visited = pointer_set_create ();
3257   cp_walk_tree (&t, &find_parameter_packs_r, &ppd, ppd.visited);
3258   pointer_set_destroy (ppd.visited);
3259
3260   if (parameter_packs)
3261     {
3262       error ("parameter packs not expanded with %<...%>:");
3263       while (parameter_packs)
3264         {
3265           tree pack = TREE_VALUE (parameter_packs);
3266           tree name = NULL_TREE;
3267
3268           if (TREE_CODE (pack) == TEMPLATE_TYPE_PARM
3269               || TREE_CODE (pack) == TEMPLATE_TEMPLATE_PARM)
3270             name = TYPE_NAME (pack);
3271           else if (TREE_CODE (pack) == TEMPLATE_PARM_INDEX)
3272             name = DECL_NAME (TEMPLATE_PARM_DECL (pack));
3273           else
3274             name = DECL_NAME (pack);
3275
3276           if (name)
3277             inform (input_location, "        %qD", name);
3278           else
3279             inform (input_location, "        <anonymous>");
3280
3281           parameter_packs = TREE_CHAIN (parameter_packs);
3282         }
3283
3284       return true;
3285     }
3286
3287   return false;
3288 }
3289
3290 /* Expand any parameter packs that occur in the template arguments in
3291    ARGS.  */
3292 tree
3293 expand_template_argument_pack (tree args)
3294 {
3295   tree result_args = NULL_TREE;
3296   int in_arg, out_arg = 0, nargs = args ? TREE_VEC_LENGTH (args) : 0;
3297   int num_result_args = -1;
3298   int non_default_args_count = -1;
3299
3300   /* First, determine if we need to expand anything, and the number of
3301      slots we'll need.  */
3302   for (in_arg = 0; in_arg < nargs; ++in_arg)
3303     {
3304       tree arg = TREE_VEC_ELT (args, in_arg);
3305       if (arg == NULL_TREE)
3306         return args;
3307       if (ARGUMENT_PACK_P (arg))
3308         {
3309           int num_packed = TREE_VEC_LENGTH (ARGUMENT_PACK_ARGS (arg));
3310           if (num_result_args < 0)
3311             num_result_args = in_arg + num_packed;
3312           else
3313             num_result_args += num_packed;
3314         }
3315       else
3316         {
3317           if (num_result_args >= 0)
3318             num_result_args++;
3319         }
3320     }
3321
3322   /* If no expansion is necessary, we're done.  */
3323   if (num_result_args < 0)
3324     return args;
3325
3326   /* Expand arguments.  */
3327   result_args = make_tree_vec (num_result_args);
3328   if (NON_DEFAULT_TEMPLATE_ARGS_COUNT (args))
3329     non_default_args_count =
3330       GET_NON_DEFAULT_TEMPLATE_ARGS_COUNT (args);
3331   for (in_arg = 0; in_arg < nargs; ++in_arg)
3332     {
3333       tree arg = TREE_VEC_ELT (args, in_arg);
3334       if (ARGUMENT_PACK_P (arg))
3335         {
3336           tree packed = ARGUMENT_PACK_ARGS (arg);
3337           int i, num_packed = TREE_VEC_LENGTH (packed);
3338           for (i = 0; i < num_packed; ++i, ++out_arg)
3339             TREE_VEC_ELT (result_args, out_arg) = TREE_VEC_ELT(packed, i);
3340           if (non_default_args_count > 0)
3341             non_default_args_count += num_packed;
3342         }
3343       else
3344         {
3345           TREE_VEC_ELT (result_args, out_arg) = arg;
3346           ++out_arg;
3347         }
3348     }
3349   if (non_default_args_count >= 0)
3350     SET_NON_DEFAULT_TEMPLATE_ARGS_COUNT (result_args, non_default_args_count);
3351   return result_args;
3352 }
3353
3354 /* Checks if DECL shadows a template parameter.
3355
3356    [temp.local]: A template-parameter shall not be redeclared within its
3357    scope (including nested scopes).
3358
3359    Emits an error and returns TRUE if the DECL shadows a parameter,
3360    returns FALSE otherwise.  */
3361
3362 bool
3363 check_template_shadow (tree decl)
3364 {
3365   tree olddecl;
3366
3367   /* If we're not in a template, we can't possibly shadow a template
3368      parameter.  */
3369   if (!current_template_parms)
3370     return true;
3371
3372   /* Figure out what we're shadowing.  */
3373   if (TREE_CODE (decl) == OVERLOAD)
3374     decl = OVL_CURRENT (decl);
3375   olddecl = innermost_non_namespace_value (DECL_NAME (decl));
3376
3377   /* If there's no previous binding for this name, we're not shadowing
3378      anything, let alone a template parameter.  */
3379   if (!olddecl)
3380     return true;
3381
3382   /* If we're not shadowing a template parameter, we're done.  Note
3383      that OLDDECL might be an OVERLOAD (or perhaps even an
3384      ERROR_MARK), so we can't just blithely assume it to be a _DECL
3385      node.  */
3386   if (!DECL_P (olddecl) || !DECL_TEMPLATE_PARM_P (olddecl))
3387     return true;
3388
3389   /* We check for decl != olddecl to avoid bogus errors for using a
3390      name inside a class.  We check TPFI to avoid duplicate errors for
3391      inline member templates.  */
3392   if (decl == olddecl
3393       || TEMPLATE_PARMS_FOR_INLINE (current_template_parms))
3394     return true;
3395
3396   error ("declaration of %q+#D", decl);
3397   error (" shadows template parm %q+#D", olddecl);
3398   return false;
3399 }
3400
3401 /* Return a new TEMPLATE_PARM_INDEX with the indicated INDEX, LEVEL,
3402    ORIG_LEVEL, DECL, and TYPE.  NUM_SIBLINGS is the total number of
3403    template parameters.  */
3404
3405 static tree
3406 build_template_parm_index (int index,
3407                            int level,
3408                            int orig_level,
3409                            int num_siblings,
3410                            tree decl,
3411                            tree type)
3412 {
3413   tree t = make_node (TEMPLATE_PARM_INDEX);
3414   TEMPLATE_PARM_IDX (t) = index;
3415   TEMPLATE_PARM_LEVEL (t) = level;
3416   TEMPLATE_PARM_ORIG_LEVEL (t) = orig_level;
3417   TEMPLATE_PARM_NUM_SIBLINGS (t) = num_siblings;
3418   TEMPLATE_PARM_DECL (t) = decl;
3419   TREE_TYPE (t) = type;
3420   TREE_CONSTANT (t) = TREE_CONSTANT (decl);
3421   TREE_READONLY (t) = TREE_READONLY (decl);
3422
3423   return t;
3424 }
3425
3426 /* Find the canonical type parameter for the given template type
3427    parameter.  Returns the canonical type parameter, which may be TYPE
3428    if no such parameter existed.  */
3429
3430 static tree
3431 canonical_type_parameter (tree type)
3432 {
3433   tree list;
3434   int idx = TEMPLATE_TYPE_IDX (type);
3435   if (!canonical_template_parms)
3436     canonical_template_parms = VEC_alloc (tree, gc, idx+1);
3437
3438   while (VEC_length (tree, canonical_template_parms) <= (unsigned)idx)
3439     VEC_safe_push (tree, gc, canonical_template_parms, NULL_TREE);
3440
3441   list = VEC_index (tree, canonical_template_parms, idx);
3442   while (list && !comptypes (type, TREE_VALUE (list), COMPARE_STRUCTURAL))
3443     list = TREE_CHAIN (list);
3444
3445   if (list)
3446     return TREE_VALUE (list);
3447   else
3448     {
3449       VEC_replace(tree, canonical_template_parms, idx,
3450                   tree_cons (NULL_TREE, type,
3451                              VEC_index (tree, canonical_template_parms, idx)));
3452       return type;
3453     }
3454 }
3455
3456 /* Return a TEMPLATE_PARM_INDEX, similar to INDEX, but whose
3457    TEMPLATE_PARM_LEVEL has been decreased by LEVELS.  If such a
3458    TEMPLATE_PARM_INDEX already exists, it is returned; otherwise, a
3459    new one is created.  */
3460
3461 static tree
3462 reduce_template_parm_level (tree index, tree type, int levels, tree args,
3463                             tsubst_flags_t complain)
3464 {
3465   if (TEMPLATE_PARM_DESCENDANTS (index) == NULL_TREE
3466       || (TEMPLATE_PARM_LEVEL (TEMPLATE_PARM_DESCENDANTS (index))
3467           != TEMPLATE_PARM_LEVEL (index) - levels)
3468       || !same_type_p (type, TREE_TYPE (TEMPLATE_PARM_DESCENDANTS (index))))
3469     {
3470       tree orig_decl = TEMPLATE_PARM_DECL (index);
3471       tree decl, t;
3472
3473       decl = build_decl (DECL_SOURCE_LOCATION (orig_decl),
3474                          TREE_CODE (orig_decl), DECL_NAME (orig_decl), type);
3475       TREE_CONSTANT (decl) = TREE_CONSTANT (orig_decl);
3476       TREE_READONLY (decl) = TREE_READONLY (orig_decl);
3477       DECL_ARTIFICIAL (decl) = 1;
3478       SET_DECL_TEMPLATE_PARM_P (decl);
3479
3480       t = build_template_parm_index (TEMPLATE_PARM_IDX (index),
3481                                      TEMPLATE_PARM_LEVEL (index) - levels,
3482                                      TEMPLATE_PARM_ORIG_LEVEL (index),
3483                                      TEMPLATE_PARM_NUM_SIBLINGS (index),
3484                                      decl, type);
3485       TEMPLATE_PARM_DESCENDANTS (index) = t;
3486       TEMPLATE_PARM_PARAMETER_PACK (t)
3487         = TEMPLATE_PARM_PARAMETER_PACK (index);
3488
3489         /* Template template parameters need this.  */
3490       if (TREE_CODE (decl) == TEMPLATE_DECL)
3491         DECL_TEMPLATE_PARMS (decl) = tsubst_template_parms
3492           (DECL_TEMPLATE_PARMS (TEMPLATE_PARM_DECL (index)),
3493            args, complain);
3494     }
3495
3496   return TEMPLATE_PARM_DESCENDANTS (index);
3497 }
3498
3499 /* Process information from new template parameter PARM and append it
3500    to the LIST being built.  This new parameter is a non-type
3501    parameter iff IS_NON_TYPE is true. This new parameter is a
3502    parameter pack iff IS_PARAMETER_PACK is true.  The location of PARM
3503    is in PARM_LOC. NUM_TEMPLATE_PARMS is the size of the template
3504    parameter list PARM belongs to. This is used used to create a
3505    proper canonical type for the type of PARM that is to be created,
3506    iff PARM is a type.  If the size is not known, this parameter shall
3507    be set to 0.  */
3508
3509 tree
3510 process_template_parm (tree list, location_t parm_loc, tree parm,
3511                        bool is_non_type, bool is_parameter_pack,
3512                        unsigned num_template_parms)
3513 {
3514   tree decl = 0;
3515   tree defval;
3516   tree err_parm_list;
3517   int idx = 0;
3518
3519   gcc_assert (TREE_CODE (parm) == TREE_LIST);
3520   defval = TREE_PURPOSE (parm);
3521
3522   if (list)
3523     {
3524       tree p = tree_last (list);
3525
3526       if (p && TREE_VALUE (p) != error_mark_node)
3527         {
3528           p = TREE_VALUE (p);
3529           if (TREE_CODE (p) == TYPE_DECL || TREE_CODE (p) == TEMPLATE_DECL)
3530             idx = TEMPLATE_TYPE_IDX (TREE_TYPE (p));
3531           else
3532             idx = TEMPLATE_PARM_IDX (DECL_INITIAL (p));
3533         }
3534
3535       ++idx;
3536     }
3537   else
3538     idx = 0;
3539
3540   if (is_non_type)
3541     {
3542       parm = TREE_VALUE (parm);
3543
3544       SET_DECL_TEMPLATE_PARM_P (parm);
3545
3546       if (TREE_TYPE (parm) == error_mark_node)
3547         {
3548           err_parm_list = build_tree_list (defval, parm);
3549           TREE_VALUE (err_parm_list) = error_mark_node;
3550            return chainon (list, err_parm_list);
3551         }
3552       else
3553       {
3554         /* [temp.param]
3555
3556            The top-level cv-qualifiers on the template-parameter are
3557            ignored when determining its type.  */
3558         TREE_TYPE (parm) = TYPE_MAIN_VARIANT (TREE_TYPE (parm));
3559         if (invalid_nontype_parm_type_p (TREE_TYPE (parm), 1))
3560           {
3561             err_parm_list = build_tree_list (defval, parm);
3562             TREE_VALUE (err_parm_list) = error_mark_node;
3563              return chainon (list, err_parm_list);
3564           }
3565
3566         if (uses_parameter_packs (TREE_TYPE (parm)) && !is_parameter_pack)
3567           {
3568             /* This template parameter is not a parameter pack, but it
3569                should be. Complain about "bare" parameter packs.  */
3570             check_for_bare_parameter_packs (TREE_TYPE (parm));
3571
3572             /* Recover by calling this a parameter pack.  */
3573             is_parameter_pack = true;
3574           }
3575       }
3576
3577       /* A template parameter is not modifiable.  */
3578       TREE_CONSTANT (parm) = 1;
3579       TREE_READONLY (parm) = 1;
3580       decl = build_decl (parm_loc,
3581                          CONST_DECL, DECL_NAME (parm), TREE_TYPE (parm));
3582       TREE_CONSTANT (decl) = 1;
3583       TREE_READONLY (decl) = 1;
3584       DECL_INITIAL (parm) = DECL_INITIAL (decl)
3585         = build_template_parm_index (idx, processing_template_decl,
3586                                      processing_template_decl,
3587                                      num_template_parms,
3588                                      decl, TREE_TYPE (parm));
3589
3590       TEMPLATE_PARM_PARAMETER_PACK (DECL_INITIAL (parm))
3591         = is_parameter_pack;
3592     }
3593   else
3594     {
3595       tree t;
3596       parm = TREE_VALUE (TREE_VALUE (parm));
3597
3598       if (parm && TREE_CODE (parm) == TEMPLATE_DECL)
3599         {
3600           t = cxx_make_type (TEMPLATE_TEMPLATE_PARM);
3601           /* This is for distinguishing between real templates and template
3602              template parameters */
3603           TREE_TYPE (parm) = t;
3604           TREE_TYPE (DECL_TEMPLATE_RESULT (parm)) = t;
3605           decl = parm;
3606         }
3607       else
3608         {
3609           t = cxx_make_type (TEMPLATE_TYPE_PARM);
3610           /* parm is either IDENTIFIER_NODE or NULL_TREE.  */
3611           decl = build_decl (parm_loc,
3612                              TYPE_DECL, parm, t);
3613         }
3614
3615       TYPE_NAME (t) = decl;
3616       TYPE_STUB_DECL (t) = decl;
3617       parm = decl;
3618       TEMPLATE_TYPE_PARM_INDEX (t)
3619         = build_template_parm_index (idx, processing_template_decl,
3620                                      processing_template_decl,
3621                                      num_template_parms,
3622                                      decl, TREE_TYPE (parm));
3623       TEMPLATE_TYPE_PARAMETER_PACK (t) = is_parameter_pack;
3624       TYPE_CANONICAL (t) = canonical_type_parameter (t);
3625     }
3626   DECL_ARTIFICIAL (decl) = 1;
3627   SET_DECL_TEMPLATE_PARM_P (decl);
3628   pushdecl (decl);
3629   parm = build_tree_list (defval, parm);
3630   return chainon (list, parm);
3631 }
3632
3633 /* The end of a template parameter list has been reached.  Process the
3634    tree list into a parameter vector, converting each parameter into a more
3635    useful form.  Type parameters are saved as IDENTIFIER_NODEs, and others
3636    as PARM_DECLs.  */
3637
3638 tree
3639 end_template_parm_list (tree parms)
3640 {
3641   int nparms;
3642   tree parm, next;
3643   tree saved_parmlist = make_tree_vec (list_length (parms));
3644
3645   current_template_parms
3646     = tree_cons (size_int (processing_template_decl),
3647                  saved_parmlist, current_template_parms);
3648
3649   for (parm = parms, nparms = 0; parm; parm = next, nparms++)
3650     {
3651       next = TREE_CHAIN (parm);
3652       TREE_VEC_ELT (saved_parmlist, nparms) = parm;
3653       TREE_CHAIN (parm) = NULL_TREE;
3654     }
3655
3656   --processing_template_parmlist;
3657
3658   return saved_parmlist;
3659 }
3660
3661 /* Create a new type almost identical to TYPE but which has the
3662    following differences:
3663
3664      1/ T has a new TEMPLATE_PARM_INDEX that carries the new number of
3665      template sibling parameters of T.
3666
3667      2/ T has a new canonical type that matches the new number
3668      of sibling parms.
3669
3670      3/ From now on, T is going to be what lookups referring to the
3671      name of TYPE will return. No lookup should return TYPE anymore.
3672
3673    NUM_PARMS is the new number of sibling parms TYPE belongs to.
3674
3675    This is a subroutine of fixup_template_parms.  */
3676
3677 static tree
3678 fixup_template_type_parm_type (tree type, int num_parms)
3679 {
3680   tree orig_idx = TEMPLATE_TYPE_PARM_INDEX (type), idx;
3681   tree t;
3682   /* This is the decl which name is inserted into the symbol table for
3683      the template parm type. So whenever we lookup the type name, this
3684      is the DECL we get.  */
3685   tree decl;
3686
3687   /* Do not fix up the type twice.  */
3688   if (orig_idx && TEMPLATE_PARM_NUM_SIBLINGS (orig_idx) != 0)
3689     return type;
3690
3691   t = copy_type (type);
3692   decl = TYPE_NAME (t);
3693
3694   TYPE_MAIN_VARIANT (t) = t;
3695   TYPE_NEXT_VARIANT (t)= NULL_TREE;
3696   TYPE_POINTER_TO (t) = 0;
3697   TYPE_REFERENCE_TO (t) = 0;
3698
3699   idx = build_template_parm_index (TEMPLATE_PARM_IDX (orig_idx),
3700                                    TEMPLATE_PARM_LEVEL (orig_idx),
3701                                    TEMPLATE_PARM_ORIG_LEVEL (orig_idx),
3702                                    num_parms,
3703                                    decl, t);
3704   TEMPLATE_PARM_DESCENDANTS (idx) = TEMPLATE_PARM_DESCENDANTS (orig_idx);
3705   TEMPLATE_PARM_PARAMETER_PACK (idx) = TEMPLATE_PARM_PARAMETER_PACK (orig_idx);
3706   TEMPLATE_TYPE_PARM_INDEX (t) = idx;
3707
3708   TYPE_STUB_DECL (t) = decl;
3709   TEMPLATE_TYPE_DECL (t) = decl;
3710   if (TREE_CODE (type) == TEMPLATE_TEMPLATE_PARM)
3711     TREE_TYPE (DECL_TEMPLATE_RESULT  (decl)) = t;
3712
3713   /* Update the type associated to the type name stored in the symbol
3714      table. Now, whenever the type name is looked up, the resulting
3715      type is properly fixed up.  */
3716   TREE_TYPE (decl) = t;
3717
3718   TYPE_CANONICAL (t) = canonical_type_parameter (t);
3719
3720   return t;
3721 }
3722
3723 /* Create and return a new TEMPLATE_PARM_INDEX that is almost
3724    identical to I, but that is fixed up as to:
3725
3726    1/ carry the number of sibling parms (NUM_PARMS) of the template
3727    parm represented by I.
3728
3729    2/ replace all references to template parm types declared before I
3730    (in the same template parm list as I) by references to template
3731    parm types contained in ARGS. ARGS should contain the list of
3732    template parms that have been fixed up so far, in a form suitable
3733    to be passed to tsubst.
3734
3735    This is a subroutine of fixup_template_parms.  */
3736
3737 static tree
3738 fixup_template_parm_index (tree i, tree args, int num_parms)
3739 {
3740   tree index, decl, type;
3741
3742   if (i == NULL_TREE
3743       || TREE_CODE (i) != TEMPLATE_PARM_INDEX
3744       /* Do not fix up the index twice.  */
3745       || (TEMPLATE_PARM_NUM_SIBLINGS (i) != 0))
3746     return i;
3747
3748   decl = TEMPLATE_PARM_DECL (i);
3749   type = TREE_TYPE (decl);
3750
3751   index = build_template_parm_index (TEMPLATE_PARM_IDX (i),
3752                                      TEMPLATE_PARM_LEVEL (i),
3753                                      TEMPLATE_PARM_ORIG_LEVEL (i),
3754                                      num_parms,
3755                                      decl, type);
3756
3757   TEMPLATE_PARM_DESCENDANTS (index) = TEMPLATE_PARM_DESCENDANTS (i);
3758   TEMPLATE_PARM_PARAMETER_PACK (index) = TEMPLATE_PARM_PARAMETER_PACK (i);
3759
3760   type = tsubst (type, args, tf_none, NULL_TREE);
3761
3762   TREE_TYPE (decl) = type;
3763   TREE_TYPE (index) = type;
3764
3765   return index;
3766 }
3767
3768 /*
3769    This is a subroutine of fixup_template_parms.
3770
3771    It computes the canonical type of the type of the template
3772    parameter PARM_DESC and update all references to that type so that
3773    they use the newly computed canonical type. No access check is
3774    performed during the fixup. PARM_DESC is a TREE_LIST which
3775    TREE_VALUE is the template parameter and its TREE_PURPOSE is the
3776    default argument of the template parm if any. IDX is the index of
3777    the template parameter, starting at 0. NUM_PARMS is the number of
3778    template parameters in the set PARM_DESC belongs to. ARGLIST is a
3779    TREE_VEC containing the full set of template parameters in a form
3780    suitable to be passed to substs functions as their ARGS
3781    argument. This is what current_template_args returns for a given
3782    template. The innermost vector of args in ARGLIST is the set of
3783    template parms that have been fixed up so far. This function adds
3784    the fixed up parameter into that vector.  */
3785
3786 static void
3787 fixup_template_parm (tree parm_desc,
3788                      int idx,
3789                      int num_parms,
3790                      tree arglist)
3791 {
3792   tree parm = TREE_VALUE (parm_desc);
3793   tree fixedup_args = INNERMOST_TEMPLATE_ARGS (arglist);
3794
3795   push_deferring_access_checks (dk_no_check);
3796
3797   if (TREE_CODE (parm) == TYPE_DECL)
3798     {
3799       /* PARM is a template type parameter. Fix up its type, add
3800          the fixed-up template parm to the vector of fixed-up
3801          template parms so far, and substitute the fixed-up
3802          template parms into the default argument of this
3803          parameter.  */
3804       tree t =
3805         fixup_template_type_parm_type (TREE_TYPE (parm), num_parms);
3806       TREE_TYPE (parm) = t;
3807
3808       TREE_VEC_ELT (fixedup_args, idx) = template_parm_to_arg (parm_desc);
3809     }
3810   else if (TREE_CODE (parm) == TEMPLATE_DECL)
3811     {
3812       /* PARM is a template template parameter. This is going to
3813          be interesting.  */
3814       tree tparms, targs, innermost_args, t;
3815       int j;
3816
3817       /* First, fix up the parms of the template template parm
3818          because the parms are involved in defining the new canonical
3819          type of the template template parm.  */
3820
3821       /* So we need to substitute the template parm types that have
3822          been fixed up so far into the template parms of this template
3823          template parm. E.g, consider this:
3824
3825          template<class T, template<T u> class TT> class S;
3826
3827          In this case we want to substitute T into the
3828          template parameters of TT.
3829
3830          So let's walk the template parms of PARM here, and
3831          tsubst ARGLIST into into each of the template
3832          parms.   */
3833
3834       /* For this substitution we need to build the full set of
3835          template parameters and use that as arguments for the
3836          tsubsting function.  */
3837       tparms = INNERMOST_TEMPLATE_PARMS (DECL_TEMPLATE_PARMS (parm));
3838
3839       /* This will contain the innermost parms of PARM into which
3840          we have substituted so far.  */
3841       innermost_args = make_tree_vec (TREE_VEC_LENGTH (tparms));
3842       targs = add_to_template_args (arglist, innermost_args);
3843       for (j = 0; j < TREE_VEC_LENGTH (tparms); ++j)
3844         {
3845           tree parameter;
3846
3847           parameter = TREE_VEC_ELT (tparms, j);
3848
3849           /* INNERMOST_ARGS needs to have at least the same number
3850              of elements as the index PARAMETER, ortherwise
3851              tsubsting into PARAMETER will result in partially
3852              instantiating it, reducing its tempate parm
3853              level. Let's tactically fill INNERMOST_ARGS for that
3854              purpose.  */
3855           TREE_VEC_ELT (innermost_args, j) =
3856             template_parm_to_arg (parameter);
3857
3858           fixup_template_parm (parameter, j,
3859                                TREE_VEC_LENGTH (tparms),
3860                                targs);
3861         }
3862
3863       /* Now fix up the type of the template template parm.  */
3864
3865       t = fixup_template_type_parm_type (TREE_TYPE (parm), num_parms);
3866       TREE_TYPE (parm) = t;
3867
3868       TREE_VEC_ELT (fixedup_args, idx) =
3869         template_parm_to_arg (parm_desc);
3870     }
3871   else if (TREE_CODE (parm) == PARM_DECL)
3872     {
3873       /* PARM is a non-type template parameter. We need to:
3874
3875        * Fix up its TEMPLATE_PARM_INDEX to make it carry the
3876        proper number of sibling parameters.
3877
3878        * Make lookups of the template parameter return a reference
3879        to the fixed-up index. No lookup should return references
3880        to the former index anymore.
3881
3882        * Substitute the template parms that got fixed up so far
3883
3884        * into the type of PARM.  */
3885
3886       tree index = DECL_INITIAL (parm);
3887
3888       /* PUSHED_DECL is the decl added to the symbol table with
3889          the name of the parameter. E,g:
3890
3891          template<class T, T u> //#0
3892          auto my_function(T t) -> decltype(u); //#1
3893
3894          Here, when looking up u at //#1, we get the decl of u
3895          resulting from the declaration in #0. This is what
3896          PUSHED_DECL is. We need to replace the reference to the
3897          old TEMPLATE_PARM_INDEX carried by PUSHED_DECL by the
3898          fixed-up TEMPLATE_PARM_INDEX.  */
3899       tree pushed_decl = TEMPLATE_PARM_DECL (index);
3900
3901       /* Let's fix up the TEMPLATE_PARM_INDEX then. Note that we must
3902          fixup the type of PUSHED_DECL as well and luckily
3903          fixup_template_parm_index does it for us too.  */
3904       tree fixed_up_index =
3905         fixup_template_parm_index (index, arglist, num_parms);
3906
3907       DECL_INITIAL (pushed_decl) = DECL_INITIAL (parm) = fixed_up_index;
3908
3909       /* Add this fixed up PARM to the template parms we've fixed
3910          up so far and use that to substitute the fixed-up
3911          template parms into the type of PARM.  */
3912       TREE_VEC_ELT (fixedup_args, idx) =
3913         template_parm_to_arg (parm_desc);
3914       TREE_TYPE (parm) = tsubst (TREE_TYPE (parm), arglist,
3915                                  tf_none, NULL_TREE);
3916     }
3917
3918   TREE_PURPOSE (parm_desc) =
3919     tsubst_template_arg (TREE_PURPOSE (parm_desc),
3920                          arglist, tf_none, parm);
3921
3922   pop_deferring_access_checks ();
3923 }
3924
3925 /* Walk the current template parms and properly compute the canonical
3926    types of the dependent types created during
3927    cp_parser_template_parameter_list.  */
3928
3929 void
3930 fixup_template_parms (void)
3931 {
3932   tree arglist;
3933   tree parameter_vec;
3934   tree fixedup_args;
3935   int i, num_parms;
3936
3937   parameter_vec = INNERMOST_TEMPLATE_PARMS (current_template_parms);
3938   if (parameter_vec == NULL_TREE)
3939     return;
3940
3941   num_parms = TREE_VEC_LENGTH (parameter_vec);
3942
3943   /* This vector contains the current innermost template parms that
3944      have been fixed up so far.  The form of FIXEDUP_ARGS is suitable
3945      to be passed to tsubst* functions as their ARGS argument.  */
3946   fixedup_args = make_tree_vec (num_parms);
3947
3948   /* This vector contains the full set of template parms in a form
3949      suitable to be passed to substs functions as their ARGS
3950      argument.  */
3951   arglist = current_template_args ();
3952   arglist = add_outermost_template_args (arglist, fixedup_args);
3953
3954   /* Let's do the proper fixup now.  */
3955   for (i = 0; i < num_parms; ++i)
3956     fixup_template_parm (TREE_VEC_ELT (parameter_vec, i),
3957                          i, num_parms, arglist);
3958 }
3959
3960 /* end_template_decl is called after a template declaration is seen.  */
3961
3962 void
3963 end_template_decl (void)
3964 {
3965   reset_specialization ();
3966
3967   if (! processing_template_decl)
3968     return;
3969
3970   /* This matches the pushlevel in begin_template_parm_list.  */
3971   finish_scope ();
3972
3973   --processing_template_decl;
3974   current_template_parms = TREE_CHAIN (current_template_parms);
3975 }
3976
3977 /* Takes a TREE_LIST representing a template parameter and convert it
3978    into an argument suitable to be passed to the type substitution
3979    functions.  Note that If the TREE_LIST contains an error_mark
3980    node, the returned argument is error_mark_node.  */
3981
3982 static tree
3983 template_parm_to_arg (tree t)
3984 {
3985
3986   if (t == NULL_TREE
3987       || TREE_CODE (t) != TREE_LIST)
3988     return t;
3989
3990   if (error_operand_p (TREE_VALUE (t)))
3991     return error_mark_node;
3992
3993   t = TREE_VALUE (t);
3994
3995   if (TREE_CODE (t) == TYPE_DECL
3996       || TREE_CODE (t) == TEMPLATE_DECL)
3997     {
3998       t = TREE_TYPE (t);
3999
4000       if (TEMPLATE_TYPE_PARAMETER_PACK (t))
4001         {
4002           /* Turn this argument into a TYPE_ARGUMENT_PACK
4003              with a single element, which expands T.  */
4004           tree vec = make_tree_vec (1);
4005 #ifdef ENABLE_CHECKING
4006           SET_NON_DEFAULT_TEMPLATE_ARGS_COUNT
4007             (vec, TREE_VEC_LENGTH (vec));
4008 #endif
4009           TREE_VEC_ELT (vec, 0) = make_pack_expansion (t);
4010
4011           t = cxx_make_type (TYPE_ARGUMENT_PACK);
4012           SET_ARGUMENT_PACK_ARGS (t, vec);
4013         }
4014     }
4015   else
4016     {
4017       t = DECL_INITIAL (t);
4018
4019       if (TEMPLATE_PARM_PARAMETER_PACK (t))
4020         {
4021           /* Turn this argument into a NONTYPE_ARGUMENT_PACK
4022              with a single element, which expands T.  */
4023           tree vec = make_tree_vec (1);
4024           tree type = TREE_TYPE (TEMPLATE_PARM_DECL (t));
4025 #ifdef ENABLE_CHECKING
4026           SET_NON_DEFAULT_TEMPLATE_ARGS_COUNT
4027             (vec, TREE_VEC_LENGTH (vec));
4028 #endif
4029           TREE_VEC_ELT (vec, 0) = make_pack_expansion (t);
4030
4031           t  = make_node (NONTYPE_ARGUMENT_PACK);
4032           SET_ARGUMENT_PACK_ARGS (t, vec);
4033           TREE_TYPE (t) = type;
4034         }
4035     }
4036   return t;
4037 }
4038
4039 /* This function returns TRUE if PARM_PACK is a template parameter
4040    pack and if ARG_PACK is what template_parm_to_arg returned when
4041    passed PARM_PACK.  */
4042
4043 static bool
4044 arg_from_parm_pack_p (tree arg_pack, tree parm_pack)
4045 {
4046   /* For clarity in the comments below let's use the representation
4047      argument_pack<elements>' to denote an argument pack and its
4048      elements.
4049
4050      In the 'if' block below, we want to detect cases where
4051      ARG_PACK is argument_pack<PARM_PACK...>.  I.e, we want to
4052      check if ARG_PACK is an argument pack which sole element is
4053      the expansion of PARM_PACK.  That argument pack is typically
4054      created by template_parm_to_arg when passed a parameter
4055      pack.  */
4056
4057   if (arg_pack
4058       && TREE_VEC_LENGTH (ARGUMENT_PACK_ARGS (arg_pack)) == 1
4059       && PACK_EXPANSION_P (TREE_VEC_ELT (ARGUMENT_PACK_ARGS (arg_pack), 0)))
4060     {
4061       tree expansion = TREE_VEC_ELT (ARGUMENT_PACK_ARGS (arg_pack), 0);
4062       tree pattern = PACK_EXPANSION_PATTERN (expansion);
4063       /* So we have an argument_pack<P...>.  We want to test if P
4064          is actually PARM_PACK.  We will not use cp_tree_equal to
4065          test P and PARM_PACK because during type fixup (by
4066          fixup_template_parm) P can be a pre-fixup version of a
4067          type and PARM_PACK be its post-fixup version.
4068          cp_tree_equal would consider them as different even
4069          though we would want to consider them compatible for our
4070          precise purpose here.
4071
4072          Thus we are going to consider that P and PARM_PACK are
4073          compatible if they have the same DECL.  */
4074       if ((/* If ARG_PACK is a type parameter pack named by the
4075               same DECL as parm_pack ...  */
4076            (TYPE_P (pattern)
4077             && TYPE_P (parm_pack)
4078             && TYPE_NAME (pattern) == TYPE_NAME (parm_pack))
4079            /* ... or if PARM_PACK is a non-type parameter named by the
4080               same DECL as ARG_PACK.  Note that PARM_PACK being a
4081               non-type parameter means it's either a PARM_DECL or a
4082               TEMPLATE_PARM_INDEX.  */
4083            || (TREE_CODE (pattern) == TEMPLATE_PARM_INDEX
4084                && ((TREE_CODE (parm_pack) == PARM_DECL
4085                     && (TEMPLATE_PARM_DECL (pattern)
4086                         == TEMPLATE_PARM_DECL (DECL_INITIAL (parm_pack))))
4087                    || (TREE_CODE (parm_pack) == TEMPLATE_PARM_INDEX
4088                        && (TEMPLATE_PARM_DECL (pattern)
4089                            == TEMPLATE_PARM_DECL (parm_pack))))))
4090           && template_parameter_pack_p (pattern))
4091         return true;
4092     }
4093   return false;
4094 }
4095
4096 /* Within the declaration of a template, return all levels of template
4097    parameters that apply.  The template parameters are represented as
4098    a TREE_VEC, in the form documented in cp-tree.h for template
4099    arguments.  */
4100
4101 static tree
4102 current_template_args (void)
4103 {
4104   tree header;
4105   tree args = NULL_TREE;
4106   int length = TMPL_PARMS_DEPTH (current_template_parms);
4107   int l = length;
4108
4109   /* If there is only one level of template parameters, we do not
4110      create a TREE_VEC of TREE_VECs.  Instead, we return a single
4111      TREE_VEC containing the arguments.  */
4112   if (length > 1)
4113     args = make_tree_vec (length);
4114
4115   for (header = current_template_parms; header; header = TREE_CHAIN (header))
4116     {
4117       tree a = copy_node (TREE_VALUE (header));
4118       int i;
4119
4120       TREE_TYPE (a) = NULL_TREE;
4121       for (i = TREE_VEC_LENGTH (a) - 1; i >= 0; --i)
4122         TREE_VEC_ELT (a, i) = template_parm_to_arg (TREE_VEC_ELT (a, i));
4123
4124 #ifdef ENABLE_CHECKING
4125       SET_NON_DEFAULT_TEMPLATE_ARGS_COUNT (a, TREE_VEC_LENGTH (a));
4126 #endif
4127
4128       if (length > 1)
4129         TREE_VEC_ELT (args, --l) = a;
4130       else
4131         args = a;
4132     }
4133
4134     if (length > 1 && TREE_VEC_ELT (args, 0) == NULL_TREE)
4135       /* This can happen for template parms of a template template
4136          parameter, e.g:
4137
4138          template<template<class T, class U> class TT> struct S;
4139
4140          Consider the level of the parms of TT; T and U both have
4141          level 2; TT has no template parm of level 1. So in this case
4142          the first element of full_template_args is NULL_TREE. If we
4143          leave it like this TMPL_ARG_DEPTH on args returns 1 instead
4144          of 2. This will make tsubst wrongly consider that T and U
4145          have level 1. Instead, let's create a dummy vector as the
4146          first element of full_template_args so that TMPL_ARG_DEPTH
4147          returns the correct depth for args.  */
4148       TREE_VEC_ELT (args, 0) = make_tree_vec (1);
4149   return args;
4150 }
4151
4152 /* Update the declared TYPE by doing any lookups which were thought to be
4153    dependent, but are not now that we know the SCOPE of the declarator.  */
4154
4155 tree
4156 maybe_update_decl_type (tree orig_type, tree scope)
4157 {
4158   tree type = orig_type;
4159
4160   if (type == NULL_TREE)
4161     return type;
4162
4163   if (TREE_CODE (orig_type) == TYPE_DECL)
4164     type = TREE_TYPE (type);
4165
4166   if (scope && TYPE_P (scope) && dependent_type_p (scope)
4167       && dependent_type_p (type)
4168       /* Don't bother building up the args in this case.  */
4169       && TREE_CODE (type) != TEMPLATE_TYPE_PARM)
4170     {
4171       /* tsubst in the args corresponding to the template parameters,
4172          including auto if present.  Most things will be unchanged, but
4173          make_typename_type and tsubst_qualified_id will resolve
4174          TYPENAME_TYPEs and SCOPE_REFs that were previously dependent.  */
4175       tree args = current_template_args ();
4176       tree auto_node = type_uses_auto (type);
4177       tree pushed;
4178       if (auto_node)
4179         {
4180           tree auto_vec = make_tree_vec (1);
4181           TREE_VEC_ELT (auto_vec, 0) = auto_node;
4182           args = add_to_template_args (args, auto_vec);
4183         }
4184       pushed = push_scope (scope);
4185       type = tsubst (type, args, tf_warning_or_error, NULL_TREE);
4186       if (pushed)
4187         pop_scope (scope);