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, 2012
   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       val = iterative_hash_template_arg (PACK_EXPANSION_PATTERN (arg), val);
1538       return iterative_hash_template_arg (PACK_EXPANSION_EXTRA_ARGS (arg), val);
1539
1540     case TYPE_ARGUMENT_PACK:
1541     case NONTYPE_ARGUMENT_PACK:
1542       return iterative_hash_template_arg (ARGUMENT_PACK_ARGS (arg), val);
1543
1544     case TREE_LIST:
1545       for (; arg; arg = TREE_CHAIN (arg))
1546         val = iterative_hash_template_arg (TREE_VALUE (arg), val);
1547       return val;
1548
1549     case OVERLOAD:
1550       for (; arg; arg = OVL_NEXT (arg))
1551         val = iterative_hash_template_arg (OVL_CURRENT (arg), val);
1552       return val;
1553
1554     case CONSTRUCTOR:
1555       {
1556         tree field, value;
1557         FOR_EACH_CONSTRUCTOR_ELT (CONSTRUCTOR_ELTS (arg), i, field, value)
1558           {
1559             val = iterative_hash_template_arg (field, val);
1560             val = iterative_hash_template_arg (value, val);
1561           }
1562         return val;
1563       }
1564
1565     case PARM_DECL:
1566       if (!DECL_ARTIFICIAL (arg))
1567         {
1568           val = iterative_hash_object (DECL_PARM_INDEX (arg), val);
1569           val = iterative_hash_object (DECL_PARM_LEVEL (arg), val);
1570         }
1571       return iterative_hash_template_arg (TREE_TYPE (arg), val);
1572
1573     case TARGET_EXPR:
1574       return iterative_hash_template_arg (TARGET_EXPR_INITIAL (arg), val);
1575
1576     case PTRMEM_CST:
1577       val = iterative_hash_template_arg (PTRMEM_CST_CLASS (arg), val);
1578       return iterative_hash_template_arg (PTRMEM_CST_MEMBER (arg), val);
1579
1580     case TEMPLATE_PARM_INDEX:
1581       val = iterative_hash_template_arg
1582         (TREE_TYPE (TEMPLATE_PARM_DECL (arg)), val);
1583       val = iterative_hash_object (TEMPLATE_PARM_LEVEL (arg), val);
1584       return iterative_hash_object (TEMPLATE_PARM_IDX (arg), val);
1585
1586     case TRAIT_EXPR:
1587       val = iterative_hash_object (TRAIT_EXPR_KIND (arg), val);
1588       val = iterative_hash_template_arg (TRAIT_EXPR_TYPE1 (arg), val);
1589       return iterative_hash_template_arg (TRAIT_EXPR_TYPE2 (arg), val);
1590
1591     case BASELINK:
1592       val = iterative_hash_template_arg (BINFO_TYPE (BASELINK_BINFO (arg)),
1593                                          val);
1594       return iterative_hash_template_arg (DECL_NAME (get_first_fn (arg)),
1595                                           val);
1596
1597     case MODOP_EXPR:
1598       val = iterative_hash_template_arg (TREE_OPERAND (arg, 0), val);
1599       code = TREE_CODE (TREE_OPERAND (arg, 1));
1600       val = iterative_hash_object (code, val);
1601       return iterative_hash_template_arg (TREE_OPERAND (arg, 2), val);
1602
1603     case LAMBDA_EXPR:
1604       /* A lambda can't appear in a template arg, but don't crash on
1605          erroneous input.  */
1606       gcc_assert (seen_error ());
1607       return val;
1608
1609     case CAST_EXPR:
1610     case IMPLICIT_CONV_EXPR:
1611     case STATIC_CAST_EXPR:
1612     case REINTERPRET_CAST_EXPR:
1613     case CONST_CAST_EXPR:
1614     case DYNAMIC_CAST_EXPR:
1615     case NEW_EXPR:
1616       val = iterative_hash_template_arg (TREE_TYPE (arg), val);
1617       /* Now hash operands as usual.  */
1618       break;
1619
1620     default:
1621       break;
1622     }
1623
1624   switch (tclass)
1625     {
1626     case tcc_type:
1627       if (TYPE_CANONICAL (arg))
1628         return iterative_hash_object (TYPE_HASH (TYPE_CANONICAL (arg)),
1629                                       val);
1630       else if (TREE_CODE (arg) == DECLTYPE_TYPE)
1631         return iterative_hash_template_arg (DECLTYPE_TYPE_EXPR (arg), val);
1632       /* Otherwise just compare the types during lookup.  */
1633       return val;
1634
1635     case tcc_declaration:
1636     case tcc_constant:
1637       return iterative_hash_expr (arg, val);
1638
1639     default:
1640       gcc_assert (IS_EXPR_CODE_CLASS (tclass));
1641       {
1642         unsigned n = cp_tree_operand_length (arg);
1643         for (i = 0; i < n; ++i)
1644           val = iterative_hash_template_arg (TREE_OPERAND (arg, i), val);
1645         return val;
1646       }
1647     }
1648   gcc_unreachable ();
1649   return 0;
1650 }
1651
1652 /* Unregister the specialization SPEC as a specialization of TMPL.
1653    Replace it with NEW_SPEC, if NEW_SPEC is non-NULL.  Returns true
1654    if the SPEC was listed as a specialization of TMPL.
1655
1656    Note that SPEC has been ggc_freed, so we can't look inside it.  */
1657
1658 bool
1659 reregister_specialization (tree spec, tree tinfo, tree new_spec)
1660 {
1661   spec_entry *entry;
1662   spec_entry elt;
1663
1664   elt.tmpl = most_general_template (TI_TEMPLATE (tinfo));
1665   elt.args = TI_ARGS (tinfo);
1666   elt.spec = NULL_TREE;
1667
1668   entry = (spec_entry *) htab_find (decl_specializations, &elt);
1669   if (entry != NULL)
1670     {
1671       gcc_assert (entry->spec == spec || entry->spec == new_spec);
1672       gcc_assert (new_spec != NULL_TREE);
1673       entry->spec = new_spec;
1674       return 1;
1675     }
1676
1677   return 0;
1678 }
1679
1680 /* Compare an entry in the local specializations hash table P1 (which
1681    is really a pointer to a TREE_LIST) with P2 (which is really a
1682    DECL).  */
1683
1684 static int
1685 eq_local_specializations (const void *p1, const void *p2)
1686 {
1687   return TREE_VALUE ((const_tree) p1) == (const_tree) p2;
1688 }
1689
1690 /* Hash P1, an entry in the local specializations table.  */
1691
1692 static hashval_t
1693 hash_local_specialization (const void* p1)
1694 {
1695   return htab_hash_pointer (TREE_VALUE ((const_tree) p1));
1696 }
1697
1698 /* Like register_specialization, but for local declarations.  We are
1699    registering SPEC, an instantiation of TMPL.  */
1700
1701 static void
1702 register_local_specialization (tree spec, tree tmpl)
1703 {
1704   void **slot;
1705
1706   slot = htab_find_slot_with_hash (local_specializations, tmpl,
1707                                    htab_hash_pointer (tmpl), INSERT);
1708   *slot = build_tree_list (spec, tmpl);
1709 }
1710
1711 /* TYPE is a class type.  Returns true if TYPE is an explicitly
1712    specialized class.  */
1713
1714 bool
1715 explicit_class_specialization_p (tree type)
1716 {
1717   if (!CLASSTYPE_TEMPLATE_SPECIALIZATION (type))
1718     return false;
1719   return !uses_template_parms (CLASSTYPE_TI_ARGS (type));
1720 }
1721
1722 /* Print the list of functions at FNS, going through all the overloads
1723    for each element of the list.  Alternatively, FNS can not be a
1724    TREE_LIST, in which case it will be printed together with all the
1725    overloads.
1726
1727    MORE and *STR should respectively be FALSE and NULL when the function
1728    is called from the outside.  They are used internally on recursive
1729    calls.  print_candidates manages the two parameters and leaves NULL
1730    in *STR when it ends.  */
1731
1732 static void
1733 print_candidates_1 (tree fns, bool more, const char **str)
1734 {
1735   tree fn, fn2;
1736   char *spaces = NULL;
1737
1738   for (fn = fns; fn; fn = OVL_NEXT (fn))
1739     if (TREE_CODE (fn) == TREE_LIST)
1740       {
1741         for (fn2 = fn; fn2 != NULL_TREE; fn2 = TREE_CHAIN (fn2))
1742           print_candidates_1 (TREE_VALUE (fn2),
1743                               TREE_CHAIN (fn2) || more, str);
1744       }
1745     else
1746       {
1747         if (!*str)
1748           {
1749             /* Pick the prefix string.  */
1750             if (!more && !OVL_NEXT (fns))
1751               {
1752                 error ("candidate is: %+#D", OVL_CURRENT (fn));
1753                 continue;
1754               }
1755
1756             *str = _("candidates are:");
1757             spaces = get_spaces (*str);
1758           }
1759         error ("%s %+#D", *str, OVL_CURRENT (fn));
1760         *str = spaces ? spaces : *str;
1761       }
1762
1763   if (!more)
1764     {
1765       free (spaces);
1766       *str = NULL;
1767     }
1768 }
1769
1770 /* Print the list of candidate FNS in an error message.  FNS can also
1771    be a TREE_LIST of non-functions in the case of an ambiguous lookup.  */
1772
1773 void
1774 print_candidates (tree fns)
1775 {
1776   const char *str = NULL;
1777   print_candidates_1 (fns, false, &str);
1778   gcc_assert (str == NULL);
1779 }
1780
1781 /* Returns the template (one of the functions given by TEMPLATE_ID)
1782    which can be specialized to match the indicated DECL with the
1783    explicit template args given in TEMPLATE_ID.  The DECL may be
1784    NULL_TREE if none is available.  In that case, the functions in
1785    TEMPLATE_ID are non-members.
1786
1787    If NEED_MEMBER_TEMPLATE is nonzero the function is known to be a
1788    specialization of a member template.
1789
1790    The TEMPLATE_COUNT is the number of references to qualifying
1791    template classes that appeared in the name of the function. See
1792    check_explicit_specialization for a more accurate description.
1793
1794    TSK indicates what kind of template declaration (if any) is being
1795    declared.  TSK_TEMPLATE indicates that the declaration given by
1796    DECL, though a FUNCTION_DECL, has template parameters, and is
1797    therefore a template function.
1798
1799    The template args (those explicitly specified and those deduced)
1800    are output in a newly created vector *TARGS_OUT.
1801
1802    If it is impossible to determine the result, an error message is
1803    issued.  The error_mark_node is returned to indicate failure.  */
1804
1805 static tree
1806 determine_specialization (tree template_id,
1807                           tree decl,
1808                           tree* targs_out,
1809                           int need_member_template,
1810                           int template_count,
1811                           tmpl_spec_kind tsk)
1812 {
1813   tree fns;
1814   tree targs;
1815   tree explicit_targs;
1816   tree candidates = NULL_TREE;
1817   /* A TREE_LIST of templates of which DECL may be a specialization.
1818      The TREE_VALUE of each node is a TEMPLATE_DECL.  The
1819      corresponding TREE_PURPOSE is the set of template arguments that,
1820      when used to instantiate the template, would produce a function
1821      with the signature of DECL.  */
1822   tree templates = NULL_TREE;
1823   int header_count;
1824   cp_binding_level *b;
1825
1826   *targs_out = NULL_TREE;
1827
1828   if (template_id == error_mark_node || decl == error_mark_node)
1829     return error_mark_node;
1830
1831   fns = TREE_OPERAND (template_id, 0);
1832   explicit_targs = TREE_OPERAND (template_id, 1);
1833
1834   if (fns == error_mark_node)
1835     return error_mark_node;
1836
1837   /* Check for baselinks.  */
1838   if (BASELINK_P (fns))
1839     fns = BASELINK_FUNCTIONS (fns);
1840
1841   if (!is_overloaded_fn (fns))
1842     {
1843       error ("%qD is not a function template", fns);
1844       return error_mark_node;
1845     }
1846
1847   /* Count the number of template headers specified for this
1848      specialization.  */
1849   header_count = 0;
1850   for (b = current_binding_level;
1851        b->kind == sk_template_parms;
1852        b = b->level_chain)
1853     ++header_count;
1854
1855   for (; fns; fns = OVL_NEXT (fns))
1856     {
1857       tree fn = OVL_CURRENT (fns);
1858
1859       if (TREE_CODE (fn) == TEMPLATE_DECL)
1860         {
1861           tree decl_arg_types;
1862           tree fn_arg_types;
1863           tree insttype;
1864
1865           /* In case of explicit specialization, we need to check if
1866              the number of template headers appearing in the specialization
1867              is correct. This is usually done in check_explicit_specialization,
1868              but the check done there cannot be exhaustive when specializing
1869              member functions. Consider the following code:
1870
1871              template <> void A<int>::f(int);
1872              template <> template <> void A<int>::f(int);
1873
1874              Assuming that A<int> is not itself an explicit specialization
1875              already, the first line specializes "f" which is a non-template
1876              member function, whilst the second line specializes "f" which
1877              is a template member function. So both lines are syntactically
1878              correct, and check_explicit_specialization does not reject
1879              them.
1880
1881              Here, we can do better, as we are matching the specialization
1882              against the declarations. We count the number of template
1883              headers, and we check if they match TEMPLATE_COUNT + 1
1884              (TEMPLATE_COUNT is the number of qualifying template classes,
1885              plus there must be another header for the member template
1886              itself).
1887
1888              Notice that if header_count is zero, this is not a
1889              specialization but rather a template instantiation, so there
1890              is no check we can perform here.  */
1891           if (header_count && header_count != template_count + 1)
1892             continue;
1893
1894           /* Check that the number of template arguments at the
1895              innermost level for DECL is the same as for FN.  */
1896           if (current_binding_level->kind == sk_template_parms
1897               && !current_binding_level->explicit_spec_p
1898               && (TREE_VEC_LENGTH (DECL_INNERMOST_TEMPLATE_PARMS (fn))
1899                   != TREE_VEC_LENGTH (INNERMOST_TEMPLATE_PARMS
1900                                       (current_template_parms))))
1901             continue;
1902
1903           /* DECL might be a specialization of FN.  */
1904           decl_arg_types = TYPE_ARG_TYPES (TREE_TYPE (decl));
1905           fn_arg_types = TYPE_ARG_TYPES (TREE_TYPE (fn));
1906
1907           /* For a non-static member function, we need to make sure
1908              that the const qualification is the same.  Since
1909              get_bindings does not try to merge the "this" parameter,
1910              we must do the comparison explicitly.  */
1911           if (DECL_NONSTATIC_MEMBER_FUNCTION_P (fn)
1912               && !same_type_p (TREE_VALUE (fn_arg_types),
1913                                TREE_VALUE (decl_arg_types)))
1914             continue;
1915
1916           /* Skip the "this" parameter and, for constructors of
1917              classes with virtual bases, the VTT parameter.  A
1918              full specialization of a constructor will have a VTT
1919              parameter, but a template never will.  */
1920           decl_arg_types
1921             = skip_artificial_parms_for (decl, decl_arg_types);
1922           fn_arg_types
1923             = skip_artificial_parms_for (fn, fn_arg_types);
1924
1925           /* Check that the number of function parameters matches.
1926              For example,
1927                template <class T> void f(int i = 0);
1928                template <> void f<int>();
1929              The specialization f<int> is invalid but is not caught
1930              by get_bindings below.  */
1931           if (cxx_dialect < cxx11
1932               && list_length (fn_arg_types) != list_length (decl_arg_types))
1933             continue;
1934
1935           /* Function templates cannot be specializations; there are
1936              no partial specializations of functions.  Therefore, if
1937              the type of DECL does not match FN, there is no
1938              match.  */
1939           if (tsk == tsk_template)
1940             {
1941               if (compparms (fn_arg_types, decl_arg_types))
1942                 candidates = tree_cons (NULL_TREE, fn, candidates);
1943               continue;
1944             }
1945
1946           /* See whether this function might be a specialization of this
1947              template.  */
1948           targs = get_bindings (fn, decl, explicit_targs, /*check_ret=*/true);
1949
1950           if (!targs)
1951             /* We cannot deduce template arguments that when used to
1952                specialize TMPL will produce DECL.  */
1953             continue;
1954
1955           if (cxx_dialect >= cxx11)
1956             {
1957               /* Make sure that the deduced arguments actually work.  */
1958               insttype = tsubst (TREE_TYPE (fn), targs, tf_none, NULL_TREE);
1959               if (insttype == error_mark_node)
1960                 continue;
1961               fn_arg_types
1962                 = skip_artificial_parms_for (fn, TYPE_ARG_TYPES (insttype));
1963               if (!compparms (fn_arg_types, decl_arg_types))
1964                 continue;
1965             }
1966
1967           /* Save this template, and the arguments deduced.  */
1968           templates = tree_cons (targs, fn, templates);
1969         }
1970       else if (need_member_template)
1971         /* FN is an ordinary member function, and we need a
1972            specialization of a member template.  */
1973         ;
1974       else if (TREE_CODE (fn) != FUNCTION_DECL)
1975         /* We can get IDENTIFIER_NODEs here in certain erroneous
1976            cases.  */
1977         ;
1978       else if (!DECL_FUNCTION_MEMBER_P (fn))
1979         /* This is just an ordinary non-member function.  Nothing can
1980            be a specialization of that.  */
1981         ;
1982       else if (DECL_ARTIFICIAL (fn))
1983         /* Cannot specialize functions that are created implicitly.  */
1984         ;
1985       else
1986         {
1987           tree decl_arg_types;
1988
1989           /* This is an ordinary member function.  However, since
1990              we're here, we can assume it's enclosing class is a
1991              template class.  For example,
1992
1993                template <typename T> struct S { void f(); };
1994                template <> void S<int>::f() {}
1995
1996              Here, S<int>::f is a non-template, but S<int> is a
1997              template class.  If FN has the same type as DECL, we
1998              might be in business.  */
1999
2000           if (!DECL_TEMPLATE_INFO (fn))
2001             /* Its enclosing class is an explicit specialization
2002                of a template class.  This is not a candidate.  */
2003             continue;
2004
2005           if (!same_type_p (TREE_TYPE (TREE_TYPE (decl)),
2006                             TREE_TYPE (TREE_TYPE (fn))))
2007             /* The return types differ.  */
2008             continue;
2009
2010           /* Adjust the type of DECL in case FN is a static member.  */
2011           decl_arg_types = TYPE_ARG_TYPES (TREE_TYPE (decl));
2012           if (DECL_STATIC_FUNCTION_P (fn)
2013               && DECL_NONSTATIC_MEMBER_FUNCTION_P (decl))
2014             decl_arg_types = TREE_CHAIN (decl_arg_types);
2015
2016           if (compparms (TYPE_ARG_TYPES (TREE_TYPE (fn)),
2017                          decl_arg_types))
2018             /* They match!  */
2019             candidates = tree_cons (NULL_TREE, fn, candidates);
2020         }
2021     }
2022
2023   if (templates && TREE_CHAIN (templates))
2024     {
2025       /* We have:
2026
2027            [temp.expl.spec]
2028
2029            It is possible for a specialization with a given function
2030            signature to be instantiated from more than one function
2031            template.  In such cases, explicit specification of the
2032            template arguments must be used to uniquely identify the
2033            function template specialization being specialized.
2034
2035          Note that here, there's no suggestion that we're supposed to
2036          determine which of the candidate templates is most
2037          specialized.  However, we, also have:
2038
2039            [temp.func.order]
2040
2041            Partial ordering of overloaded function template
2042            declarations is used in the following contexts to select
2043            the function template to which a function template
2044            specialization refers:
2045
2046            -- when an explicit specialization refers to a function
2047               template.
2048
2049          So, we do use the partial ordering rules, at least for now.
2050          This extension can only serve to make invalid programs valid,
2051          so it's safe.  And, there is strong anecdotal evidence that
2052          the committee intended the partial ordering rules to apply;
2053          the EDG front end has that behavior, and John Spicer claims
2054          that the committee simply forgot to delete the wording in
2055          [temp.expl.spec].  */
2056       tree tmpl = most_specialized_instantiation (templates);
2057       if (tmpl != error_mark_node)
2058         {
2059           templates = tmpl;
2060           TREE_CHAIN (templates) = NULL_TREE;
2061         }
2062     }
2063
2064   if (templates == NULL_TREE && candidates == NULL_TREE)
2065     {
2066       error ("template-id %qD for %q+D does not match any template "
2067              "declaration", template_id, decl);
2068       if (header_count && header_count != template_count + 1)
2069         inform (input_location, "saw %d %<template<>%>, need %d for "
2070                 "specializing a member function template",
2071                 header_count, template_count + 1);
2072       return error_mark_node;
2073     }
2074   else if ((templates && TREE_CHAIN (templates))
2075            || (candidates && TREE_CHAIN (candidates))
2076            || (templates && candidates))
2077     {
2078       error ("ambiguous template specialization %qD for %q+D",
2079              template_id, decl);
2080       candidates = chainon (candidates, templates);
2081       print_candidates (candidates);
2082       return error_mark_node;
2083     }
2084
2085   /* We have one, and exactly one, match.  */
2086   if (candidates)
2087     {
2088       tree fn = TREE_VALUE (candidates);
2089       *targs_out = copy_node (DECL_TI_ARGS (fn));
2090       /* DECL is a re-declaration or partial instantiation of a template
2091          function.  */
2092       if (TREE_CODE (fn) == TEMPLATE_DECL)
2093         return fn;
2094       /* It was a specialization of an ordinary member function in a
2095          template class.  */
2096       return DECL_TI_TEMPLATE (fn);
2097     }
2098
2099   /* It was a specialization of a template.  */
2100   targs = DECL_TI_ARGS (DECL_TEMPLATE_RESULT (TREE_VALUE (templates)));
2101   if (TMPL_ARGS_HAVE_MULTIPLE_LEVELS (targs))
2102     {
2103       *targs_out = copy_node (targs);
2104       SET_TMPL_ARGS_LEVEL (*targs_out,
2105                            TMPL_ARGS_DEPTH (*targs_out),
2106                            TREE_PURPOSE (templates));
2107     }
2108   else
2109     *targs_out = TREE_PURPOSE (templates);
2110   return TREE_VALUE (templates);
2111 }
2112
2113 /* Returns a chain of parameter types, exactly like the SPEC_TYPES,
2114    but with the default argument values filled in from those in the
2115    TMPL_TYPES.  */
2116
2117 static tree
2118 copy_default_args_to_explicit_spec_1 (tree spec_types,
2119                                       tree tmpl_types)
2120 {
2121   tree new_spec_types;
2122
2123   if (!spec_types)
2124     return NULL_TREE;
2125
2126   if (spec_types == void_list_node)
2127     return void_list_node;
2128
2129   /* Substitute into the rest of the list.  */
2130   new_spec_types =
2131     copy_default_args_to_explicit_spec_1 (TREE_CHAIN (spec_types),
2132                                           TREE_CHAIN (tmpl_types));
2133
2134   /* Add the default argument for this parameter.  */
2135   return hash_tree_cons (TREE_PURPOSE (tmpl_types),
2136                          TREE_VALUE (spec_types),
2137                          new_spec_types);
2138 }
2139
2140 /* DECL is an explicit specialization.  Replicate default arguments
2141    from the template it specializes.  (That way, code like:
2142
2143      template <class T> void f(T = 3);
2144      template <> void f(double);
2145      void g () { f (); }
2146
2147    works, as required.)  An alternative approach would be to look up
2148    the correct default arguments at the call-site, but this approach
2149    is consistent with how implicit instantiations are handled.  */
2150
2151 static void
2152 copy_default_args_to_explicit_spec (tree decl)
2153 {
2154   tree tmpl;
2155   tree spec_types;
2156   tree tmpl_types;
2157   tree new_spec_types;
2158   tree old_type;
2159   tree new_type;
2160   tree t;
2161   tree object_type = NULL_TREE;
2162   tree in_charge = NULL_TREE;
2163   tree vtt = NULL_TREE;
2164
2165   /* See if there's anything we need to do.  */
2166   tmpl = DECL_TI_TEMPLATE (decl);
2167   tmpl_types = TYPE_ARG_TYPES (TREE_TYPE (DECL_TEMPLATE_RESULT (tmpl)));
2168   for (t = tmpl_types; t; t = TREE_CHAIN (t))
2169     if (TREE_PURPOSE (t))
2170       break;
2171   if (!t)
2172     return;
2173
2174   old_type = TREE_TYPE (decl);
2175   spec_types = TYPE_ARG_TYPES (old_type);
2176
2177   if (DECL_NONSTATIC_MEMBER_FUNCTION_P (decl))
2178     {
2179       /* Remove the this pointer, but remember the object's type for
2180          CV quals.  */
2181       object_type = TREE_TYPE (TREE_VALUE (spec_types));
2182       spec_types = TREE_CHAIN (spec_types);
2183       tmpl_types = TREE_CHAIN (tmpl_types);
2184
2185       if (DECL_HAS_IN_CHARGE_PARM_P (decl))
2186         {
2187           /* DECL may contain more parameters than TMPL due to the extra
2188              in-charge parameter in constructors and destructors.  */
2189           in_charge = spec_types;
2190           spec_types = TREE_CHAIN (spec_types);
2191         }
2192       if (DECL_HAS_VTT_PARM_P (decl))
2193         {
2194           vtt = spec_types;
2195           spec_types = TREE_CHAIN (spec_types);
2196         }
2197     }
2198
2199   /* Compute the merged default arguments.  */
2200   new_spec_types =
2201     copy_default_args_to_explicit_spec_1 (spec_types, tmpl_types);
2202
2203   /* Compute the new FUNCTION_TYPE.  */
2204   if (object_type)
2205     {
2206       if (vtt)
2207         new_spec_types = hash_tree_cons (TREE_PURPOSE (vtt),
2208                                          TREE_VALUE (vtt),
2209                                          new_spec_types);
2210
2211       if (in_charge)
2212         /* Put the in-charge parameter back.  */
2213         new_spec_types = hash_tree_cons (TREE_PURPOSE (in_charge),
2214                                          TREE_VALUE (in_charge),
2215                                          new_spec_types);
2216
2217       new_type = build_method_type_directly (object_type,
2218                                              TREE_TYPE (old_type),
2219                                              new_spec_types);
2220     }
2221   else
2222     new_type = build_function_type (TREE_TYPE (old_type),
2223                                     new_spec_types);
2224   new_type = cp_build_type_attribute_variant (new_type,
2225                                               TYPE_ATTRIBUTES (old_type));
2226   new_type = build_exception_variant (new_type,
2227                                       TYPE_RAISES_EXCEPTIONS (old_type));
2228   TREE_TYPE (decl) = new_type;
2229 }
2230
2231 /* Check to see if the function just declared, as indicated in
2232    DECLARATOR, and in DECL, is a specialization of a function
2233    template.  We may also discover that the declaration is an explicit
2234    instantiation at this point.
2235
2236    Returns DECL, or an equivalent declaration that should be used
2237    instead if all goes well.  Issues an error message if something is
2238    amiss.  Returns error_mark_node if the error is not easily
2239    recoverable.
2240
2241    FLAGS is a bitmask consisting of the following flags:
2242
2243    2: The function has a definition.
2244    4: The function is a friend.
2245
2246    The TEMPLATE_COUNT is the number of references to qualifying
2247    template classes that appeared in the name of the function.  For
2248    example, in
2249
2250      template <class T> struct S { void f(); };
2251      void S<int>::f();
2252
2253    the TEMPLATE_COUNT would be 1.  However, explicitly specialized
2254    classes are not counted in the TEMPLATE_COUNT, so that in
2255
2256      template <class T> struct S {};
2257      template <> struct S<int> { void f(); }
2258      template <> void S<int>::f();
2259
2260    the TEMPLATE_COUNT would be 0.  (Note that this declaration is
2261    invalid; there should be no template <>.)
2262
2263    If the function is a specialization, it is marked as such via
2264    DECL_TEMPLATE_SPECIALIZATION.  Furthermore, its DECL_TEMPLATE_INFO
2265    is set up correctly, and it is added to the list of specializations
2266    for that template.  */
2267
2268 tree
2269 check_explicit_specialization (tree declarator,
2270                                tree decl,
2271                                int template_count,
2272                                int flags)
2273 {
2274   int have_def = flags & 2;
2275   int is_friend = flags & 4;
2276   int specialization = 0;
2277   int explicit_instantiation = 0;
2278   int member_specialization = 0;
2279   tree ctype = DECL_CLASS_CONTEXT (decl);
2280   tree dname = DECL_NAME (decl);
2281   tmpl_spec_kind tsk;
2282
2283   if (is_friend)
2284     {
2285       if (!processing_specialization)
2286         tsk = tsk_none;
2287       else
2288         tsk = tsk_excessive_parms;
2289     }
2290   else
2291     tsk = current_tmpl_spec_kind (template_count);
2292
2293   switch (tsk)
2294     {
2295     case tsk_none:
2296       if (processing_specialization)
2297         {
2298           specialization = 1;
2299           SET_DECL_TEMPLATE_SPECIALIZATION (decl);
2300         }
2301       else if (TREE_CODE (declarator) == TEMPLATE_ID_EXPR)
2302         {
2303           if (is_friend)
2304             /* This could be something like:
2305
2306                template <class T> void f(T);
2307                class S { friend void f<>(int); }  */
2308             specialization = 1;
2309           else
2310             {
2311               /* This case handles bogus declarations like template <>
2312                  template <class T> void f<int>(); */
2313
2314               error ("template-id %qD in declaration of primary template",
2315                      declarator);
2316               return decl;
2317             }
2318         }
2319       break;
2320
2321     case tsk_invalid_member_spec:
2322       /* The error has already been reported in
2323          check_specialization_scope.  */
2324       return error_mark_node;
2325
2326     case tsk_invalid_expl_inst:
2327       error ("template parameter list used in explicit instantiation");
2328
2329       /* Fall through.  */
2330
2331     case tsk_expl_inst:
2332       if (have_def)
2333         error ("definition provided for explicit instantiation");
2334
2335       explicit_instantiation = 1;
2336       break;
2337
2338     case tsk_excessive_parms:
2339     case tsk_insufficient_parms:
2340       if (tsk == tsk_excessive_parms)
2341         error ("too many template parameter lists in declaration of %qD",
2342                decl);
2343       else if (template_header_count)
2344         error("too few template parameter lists in declaration of %qD", decl);
2345       else
2346         error("explicit specialization of %qD must be introduced by "
2347               "%<template <>%>", decl);
2348
2349       /* Fall through.  */
2350     case tsk_expl_spec:
2351       SET_DECL_TEMPLATE_SPECIALIZATION (decl);
2352       if (ctype)
2353         member_specialization = 1;
2354       else
2355         specialization = 1;
2356       break;
2357
2358     case tsk_template:
2359       if (TREE_CODE (declarator) == TEMPLATE_ID_EXPR)
2360         {
2361           /* This case handles bogus declarations like template <>
2362              template <class T> void f<int>(); */
2363
2364           if (uses_template_parms (declarator))
2365             error ("function template partial specialization %qD "
2366                    "is not allowed", declarator);
2367           else
2368             error ("template-id %qD in declaration of primary template",
2369                    declarator);
2370           return decl;
2371         }
2372
2373       if (ctype && CLASSTYPE_TEMPLATE_INSTANTIATION (ctype))
2374         /* This is a specialization of a member template, without
2375            specialization the containing class.  Something like:
2376
2377              template <class T> struct S {
2378                template <class U> void f (U);
2379              };
2380              template <> template <class U> void S<int>::f(U) {}
2381
2382            That's a specialization -- but of the entire template.  */
2383         specialization = 1;
2384       break;
2385
2386     default:
2387       gcc_unreachable ();
2388     }
2389
2390   if (specialization || member_specialization)
2391     {
2392       tree t = TYPE_ARG_TYPES (TREE_TYPE (decl));
2393       for (; t; t = TREE_CHAIN (t))
2394         if (TREE_PURPOSE (t))
2395           {
2396             permerror (input_location,
2397                        "default argument specified in explicit specialization");
2398             break;
2399           }
2400     }
2401
2402   if (specialization || member_specialization || explicit_instantiation)
2403     {
2404       tree tmpl = NULL_TREE;
2405       tree targs = NULL_TREE;
2406
2407       /* Make sure that the declarator is a TEMPLATE_ID_EXPR.  */
2408       if (TREE_CODE (declarator) != TEMPLATE_ID_EXPR)
2409         {
2410           tree fns;
2411
2412           gcc_assert (TREE_CODE (declarator) == IDENTIFIER_NODE);
2413           if (ctype)
2414             fns = dname;
2415           else
2416             {
2417               /* If there is no class context, the explicit instantiation
2418                  must be at namespace scope.  */
2419               gcc_assert (DECL_NAMESPACE_SCOPE_P (decl));
2420
2421               /* Find the namespace binding, using the declaration
2422                  context.  */
2423               fns = lookup_qualified_name (CP_DECL_CONTEXT (decl), dname,
2424                                            false, true);
2425               if (fns == error_mark_node || !is_overloaded_fn (fns))
2426                 {
2427                   error ("%qD is not a template function", dname);
2428                   fns = error_mark_node;
2429                 }
2430               else
2431                 {
2432                   tree fn = OVL_CURRENT (fns);
2433                   if (!is_associated_namespace (CP_DECL_CONTEXT (decl),
2434                                                 CP_DECL_CONTEXT (fn)))
2435                     error ("%qD is not declared in %qD",
2436                            decl, current_namespace);
2437                 }
2438             }
2439
2440           declarator = lookup_template_function (fns, NULL_TREE);
2441         }
2442
2443       if (declarator == error_mark_node)
2444         return error_mark_node;
2445
2446       if (ctype != NULL_TREE && TYPE_BEING_DEFINED (ctype))
2447         {
2448           if (!explicit_instantiation)
2449             /* A specialization in class scope.  This is invalid,
2450                but the error will already have been flagged by
2451                check_specialization_scope.  */
2452             return error_mark_node;
2453           else
2454             {
2455               /* It's not valid to write an explicit instantiation in
2456                  class scope, e.g.:
2457
2458                    class C { template void f(); }
2459
2460                    This case is caught by the parser.  However, on
2461                    something like:
2462
2463                    template class C { void f(); };
2464
2465                    (which is invalid) we can get here.  The error will be
2466                    issued later.  */
2467               ;
2468             }
2469
2470           return decl;
2471         }
2472       else if (ctype != NULL_TREE
2473                && (TREE_CODE (TREE_OPERAND (declarator, 0)) ==
2474                    IDENTIFIER_NODE))
2475         {
2476           /* Find the list of functions in ctype that have the same
2477              name as the declared function.  */
2478           tree name = TREE_OPERAND (declarator, 0);
2479           tree fns = NULL_TREE;
2480           int idx;
2481
2482           if (constructor_name_p (name, ctype))
2483             {
2484               int is_constructor = DECL_CONSTRUCTOR_P (decl);
2485
2486               if (is_constructor ? !TYPE_HAS_USER_CONSTRUCTOR (ctype)
2487                   : !CLASSTYPE_DESTRUCTORS (ctype))
2488                 {
2489                   /* From [temp.expl.spec]:
2490
2491                      If such an explicit specialization for the member
2492                      of a class template names an implicitly-declared
2493                      special member function (clause _special_), the
2494                      program is ill-formed.
2495
2496                      Similar language is found in [temp.explicit].  */
2497                   error ("specialization of implicitly-declared special member function");
2498                   return error_mark_node;
2499                 }
2500
2501               name = is_constructor ? ctor_identifier : dtor_identifier;
2502             }
2503
2504           if (!DECL_CONV_FN_P (decl))
2505             {
2506               idx = lookup_fnfields_1 (ctype, name);
2507               if (idx >= 0)
2508                 fns = VEC_index (tree, CLASSTYPE_METHOD_VEC (ctype), idx);
2509             }
2510           else
2511             {
2512               VEC(tree,gc) *methods;
2513               tree ovl;
2514
2515               /* For a type-conversion operator, we cannot do a
2516                  name-based lookup.  We might be looking for `operator
2517                  int' which will be a specialization of `operator T'.
2518                  So, we find *all* the conversion operators, and then
2519                  select from them.  */
2520               fns = NULL_TREE;
2521
2522               methods = CLASSTYPE_METHOD_VEC (ctype);
2523               if (methods)
2524                 for (idx = CLASSTYPE_FIRST_CONVERSION_SLOT;
2525                      VEC_iterate (tree, methods, idx, ovl);
2526                      ++idx)
2527                   {
2528                     if (!DECL_CONV_FN_P (OVL_CURRENT (ovl)))
2529                       /* There are no more conversion functions.  */
2530                       break;
2531
2532                     /* Glue all these conversion functions together
2533                        with those we already have.  */
2534                     for (; ovl; ovl = OVL_NEXT (ovl))
2535                       fns = ovl_cons (OVL_CURRENT (ovl), fns);
2536                   }
2537             }
2538
2539           if (fns == NULL_TREE)
2540             {
2541               error ("no member function %qD declared in %qT", name, ctype);
2542               return error_mark_node;
2543             }
2544           else
2545             TREE_OPERAND (declarator, 0) = fns;
2546         }
2547
2548       /* Figure out what exactly is being specialized at this point.
2549          Note that for an explicit instantiation, even one for a
2550          member function, we cannot tell apriori whether the
2551          instantiation is for a member template, or just a member
2552          function of a template class.  Even if a member template is
2553          being instantiated, the member template arguments may be
2554          elided if they can be deduced from the rest of the
2555          declaration.  */
2556       tmpl = determine_specialization (declarator, decl,
2557                                        &targs,
2558                                        member_specialization,
2559                                        template_count,
2560                                        tsk);
2561
2562       if (!tmpl || tmpl == error_mark_node)
2563         /* We couldn't figure out what this declaration was
2564            specializing.  */
2565         return error_mark_node;
2566       else
2567         {
2568           tree gen_tmpl = most_general_template (tmpl);
2569
2570           if (explicit_instantiation)
2571             {
2572               /* We don't set DECL_EXPLICIT_INSTANTIATION here; that
2573                  is done by do_decl_instantiation later.  */
2574
2575               int arg_depth = TMPL_ARGS_DEPTH (targs);
2576               int parm_depth = TMPL_PARMS_DEPTH (DECL_TEMPLATE_PARMS (tmpl));
2577
2578               if (arg_depth > parm_depth)
2579                 {
2580                   /* If TMPL is not the most general template (for
2581                      example, if TMPL is a friend template that is
2582                      injected into namespace scope), then there will
2583                      be too many levels of TARGS.  Remove some of them
2584                      here.  */
2585                   int i;
2586                   tree new_targs;
2587
2588                   new_targs = make_tree_vec (parm_depth);
2589                   for (i = arg_depth - parm_depth; i < arg_depth; ++i)
2590                     TREE_VEC_ELT (new_targs, i - (arg_depth - parm_depth))
2591                       = TREE_VEC_ELT (targs, i);
2592                   targs = new_targs;
2593                 }
2594
2595               return instantiate_template (tmpl, targs, tf_error);
2596             }
2597
2598           /* If we thought that the DECL was a member function, but it
2599              turns out to be specializing a static member function,
2600              make DECL a static member function as well.  */
2601           if (DECL_STATIC_FUNCTION_P (tmpl)
2602               && DECL_NONSTATIC_MEMBER_FUNCTION_P (decl))
2603             revert_static_member_fn (decl);
2604
2605           /* If this is a specialization of a member template of a
2606              template class, we want to return the TEMPLATE_DECL, not
2607              the specialization of it.  */
2608           if (tsk == tsk_template)
2609             {
2610               tree result = DECL_TEMPLATE_RESULT (tmpl);
2611               SET_DECL_TEMPLATE_SPECIALIZATION (tmpl);
2612               DECL_INITIAL (result) = NULL_TREE;
2613               if (have_def)
2614                 {
2615                   tree parm;
2616                   DECL_SOURCE_LOCATION (tmpl) = DECL_SOURCE_LOCATION (decl);
2617                   DECL_SOURCE_LOCATION (result)
2618                     = DECL_SOURCE_LOCATION (decl);
2619                   /* We want to use the argument list specified in the
2620                      definition, not in the original declaration.  */
2621                   DECL_ARGUMENTS (result) = DECL_ARGUMENTS (decl);
2622                   for (parm = DECL_ARGUMENTS (result); parm;
2623                        parm = DECL_CHAIN (parm))
2624                     DECL_CONTEXT (parm) = result;
2625                 }
2626               return register_specialization (tmpl, gen_tmpl, targs,
2627                                               is_friend, 0);
2628             }
2629
2630           /* Set up the DECL_TEMPLATE_INFO for DECL.  */
2631           DECL_TEMPLATE_INFO (decl) = build_template_info (tmpl, targs);
2632
2633           /* Inherit default function arguments from the template
2634              DECL is specializing.  */
2635           copy_default_args_to_explicit_spec (decl);
2636
2637           /* This specialization has the same protection as the
2638              template it specializes.  */
2639           TREE_PRIVATE (decl) = TREE_PRIVATE (gen_tmpl);
2640           TREE_PROTECTED (decl) = TREE_PROTECTED (gen_tmpl);
2641
2642           /* 7.1.1-1 [dcl.stc]
2643
2644              A storage-class-specifier shall not be specified in an
2645              explicit specialization...
2646
2647              The parser rejects these, so unless action is taken here,
2648              explicit function specializations will always appear with
2649              global linkage.
2650
2651              The action recommended by the C++ CWG in response to C++
2652              defect report 605 is to make the storage class and linkage
2653              of the explicit specialization match the templated function:
2654
2655              http://www.open-std.org/jtc1/sc22/wg21/docs/cwg_active.html#605
2656            */
2657           if (tsk == tsk_expl_spec && DECL_FUNCTION_TEMPLATE_P (gen_tmpl))
2658             {
2659               tree tmpl_func = DECL_TEMPLATE_RESULT (gen_tmpl);
2660               gcc_assert (TREE_CODE (tmpl_func) == FUNCTION_DECL);
2661
2662               /* This specialization has the same linkage and visibility as
2663                  the function template it specializes.  */
2664               TREE_PUBLIC (decl) = TREE_PUBLIC (tmpl_func);
2665               if (! TREE_PUBLIC (decl))
2666                 {
2667                   DECL_INTERFACE_KNOWN (decl) = 1;
2668                   DECL_NOT_REALLY_EXTERN (decl) = 1;
2669                 }
2670               DECL_THIS_STATIC (decl) = DECL_THIS_STATIC (tmpl_func);
2671               if (DECL_VISIBILITY_SPECIFIED (tmpl_func))
2672                 {
2673                   DECL_VISIBILITY_SPECIFIED (decl) = 1;
2674                   DECL_VISIBILITY (decl) = DECL_VISIBILITY (tmpl_func);
2675                 }
2676             }
2677
2678           /* If DECL is a friend declaration, declared using an
2679              unqualified name, the namespace associated with DECL may
2680              have been set incorrectly.  For example, in:
2681
2682                template <typename T> void f(T);
2683                namespace N {
2684                  struct S { friend void f<int>(int); }
2685                }
2686
2687              we will have set the DECL_CONTEXT for the friend
2688              declaration to N, rather than to the global namespace.  */
2689           if (DECL_NAMESPACE_SCOPE_P (decl))
2690             DECL_CONTEXT (decl) = DECL_CONTEXT (tmpl);
2691
2692           if (is_friend && !have_def)
2693             /* This is not really a declaration of a specialization.
2694                It's just the name of an instantiation.  But, it's not
2695                a request for an instantiation, either.  */
2696             SET_DECL_IMPLICIT_INSTANTIATION (decl);
2697           else if (DECL_CONSTRUCTOR_P (decl) || DECL_DESTRUCTOR_P (decl))
2698             /* This is indeed a specialization.  In case of constructors
2699                and destructors, we need in-charge and not-in-charge
2700                versions in V3 ABI.  */
2701             clone_function_decl (decl, /*update_method_vec_p=*/0);
2702
2703           /* Register this specialization so that we can find it
2704              again.  */
2705           decl = register_specialization (decl, gen_tmpl, targs, is_friend, 0);
2706         }
2707     }
2708
2709   return decl;
2710 }
2711
2712 /* Returns 1 iff PARMS1 and PARMS2 are identical sets of template
2713    parameters.  These are represented in the same format used for
2714    DECL_TEMPLATE_PARMS.  */
2715
2716 int
2717 comp_template_parms (const_tree parms1, const_tree parms2)
2718 {
2719   const_tree p1;
2720   const_tree p2;
2721
2722   if (parms1 == parms2)
2723     return 1;
2724
2725   for (p1 = parms1, p2 = parms2;
2726        p1 != NULL_TREE && p2 != NULL_TREE;
2727        p1 = TREE_CHAIN (p1), p2 = TREE_CHAIN (p2))
2728     {
2729       tree t1 = TREE_VALUE (p1);
2730       tree t2 = TREE_VALUE (p2);
2731       int i;
2732
2733       gcc_assert (TREE_CODE (t1) == TREE_VEC);
2734       gcc_assert (TREE_CODE (t2) == TREE_VEC);
2735
2736       if (TREE_VEC_LENGTH (t1) != TREE_VEC_LENGTH (t2))
2737         return 0;
2738
2739       for (i = 0; i < TREE_VEC_LENGTH (t2); ++i)
2740         {
2741           tree parm1 = TREE_VALUE (TREE_VEC_ELT (t1, i));
2742           tree parm2 = TREE_VALUE (TREE_VEC_ELT (t2, i));
2743
2744           /* If either of the template parameters are invalid, assume
2745              they match for the sake of error recovery. */
2746           if (parm1 == error_mark_node || parm2 == error_mark_node)
2747             return 1;
2748
2749           if (TREE_CODE (parm1) != TREE_CODE (parm2))
2750             return 0;
2751
2752           if (TREE_CODE (parm1) == TEMPLATE_TYPE_PARM
2753               && (TEMPLATE_TYPE_PARAMETER_PACK (parm1)
2754                   == TEMPLATE_TYPE_PARAMETER_PACK (parm2)))
2755             continue;
2756           else if (!same_type_p (TREE_TYPE (parm1), TREE_TYPE (parm2)))
2757             return 0;
2758         }
2759     }
2760
2761   if ((p1 != NULL_TREE) != (p2 != NULL_TREE))
2762     /* One set of parameters has more parameters lists than the
2763        other.  */
2764     return 0;
2765
2766   return 1;
2767 }
2768
2769 /* Determine whether PARM is a parameter pack.  */
2770
2771 bool
2772 template_parameter_pack_p (const_tree parm)
2773 {
2774   /* Determine if we have a non-type template parameter pack.  */
2775   if (TREE_CODE (parm) == PARM_DECL)
2776     return (DECL_TEMPLATE_PARM_P (parm)
2777             && TEMPLATE_PARM_PARAMETER_PACK (DECL_INITIAL (parm)));
2778   if (TREE_CODE (parm) == TEMPLATE_PARM_INDEX)
2779     return TEMPLATE_PARM_PARAMETER_PACK (parm);
2780
2781   /* If this is a list of template parameters, we could get a
2782      TYPE_DECL or a TEMPLATE_DECL.  */
2783   if (TREE_CODE (parm) == TYPE_DECL || TREE_CODE (parm) == TEMPLATE_DECL)
2784     parm = TREE_TYPE (parm);
2785
2786   /* Otherwise it must be a type template parameter.  */
2787   return ((TREE_CODE (parm) == TEMPLATE_TYPE_PARM
2788            || TREE_CODE (parm) == TEMPLATE_TEMPLATE_PARM)
2789           && TEMPLATE_TYPE_PARAMETER_PACK (parm));
2790 }
2791
2792 /* Determine if T is a function parameter pack.  */
2793
2794 bool
2795 function_parameter_pack_p (const_tree t)
2796 {
2797   if (t && TREE_CODE (t) == PARM_DECL)
2798     return FUNCTION_PARAMETER_PACK_P (t);
2799   return false;
2800 }
2801
2802 /* Return the function template declaration of PRIMARY_FUNC_TMPL_INST.
2803    PRIMARY_FUNC_TMPL_INST is a primary function template instantiation.  */
2804
2805 tree
2806 get_function_template_decl (const_tree primary_func_tmpl_inst)
2807 {
2808   if (! primary_func_tmpl_inst
2809       || TREE_CODE (primary_func_tmpl_inst) != FUNCTION_DECL
2810       || ! primary_template_instantiation_p (primary_func_tmpl_inst))
2811     return NULL;
2812
2813   return DECL_TEMPLATE_RESULT (DECL_TI_TEMPLATE (primary_func_tmpl_inst));
2814 }
2815
2816 /* Return true iff the function parameter PARAM_DECL was expanded
2817    from the function parameter pack PACK.  */
2818
2819 bool
2820 function_parameter_expanded_from_pack_p (tree param_decl, tree pack)
2821 {
2822   if (DECL_ARTIFICIAL (param_decl)
2823       || !function_parameter_pack_p (pack))
2824     return false;
2825
2826   /* The parameter pack and its pack arguments have the same
2827      DECL_PARM_INDEX.  */
2828   return DECL_PARM_INDEX (pack) == DECL_PARM_INDEX (param_decl);
2829 }
2830
2831 /* Determine whether ARGS describes a variadic template args list,
2832    i.e., one that is terminated by a template argument pack.  */
2833
2834 static bool
2835 template_args_variadic_p (tree args)
2836 {
2837   int nargs;
2838   tree last_parm;
2839
2840   if (args == NULL_TREE)
2841     return false;
2842
2843   args = INNERMOST_TEMPLATE_ARGS (args);
2844   nargs = TREE_VEC_LENGTH (args);
2845
2846   if (nargs == 0)
2847     return false;
2848
2849   last_parm = TREE_VEC_ELT (args, nargs - 1);
2850
2851   return ARGUMENT_PACK_P (last_parm);
2852 }
2853
2854 /* Generate a new name for the parameter pack name NAME (an
2855    IDENTIFIER_NODE) that incorporates its */
2856
2857 static tree
2858 make_ith_pack_parameter_name (tree name, int i)
2859 {
2860   /* Munge the name to include the parameter index.  */
2861 #define NUMBUF_LEN 128
2862   char numbuf[NUMBUF_LEN];
2863   char* newname;
2864   int newname_len;
2865
2866   snprintf (numbuf, NUMBUF_LEN, "%i", i);
2867   newname_len = IDENTIFIER_LENGTH (name)
2868                 + strlen (numbuf) + 2;
2869   newname = (char*)alloca (newname_len);
2870   snprintf (newname, newname_len,
2871             "%s#%i", IDENTIFIER_POINTER (name), i);
2872   return get_identifier (newname);
2873 }
2874
2875 /* Return true if T is a primary function, class or alias template
2876    instantiation.  */
2877
2878 bool
2879 primary_template_instantiation_p (const_tree t)
2880 {
2881   if (!t)
2882     return false;
2883
2884   if (TREE_CODE (t) == FUNCTION_DECL)
2885     return DECL_LANG_SPECIFIC (t)
2886            && DECL_TEMPLATE_INSTANTIATION (t)
2887            && PRIMARY_TEMPLATE_P (DECL_TI_TEMPLATE (t));
2888   else if (CLASS_TYPE_P (t) && !TYPE_DECL_ALIAS_P (TYPE_NAME (t)))
2889     return CLASSTYPE_TEMPLATE_INSTANTIATION (t)
2890            && PRIMARY_TEMPLATE_P (CLASSTYPE_TI_TEMPLATE (t));
2891   else if (TYPE_P (t)
2892            && TYPE_TEMPLATE_INFO (t)
2893            && PRIMARY_TEMPLATE_P (TYPE_TI_TEMPLATE (t))
2894            && DECL_TEMPLATE_INSTANTIATION (TYPE_NAME (t)))
2895     return true;
2896   return false;
2897 }
2898
2899 /* Return true if PARM is a template template parameter.  */
2900
2901 bool
2902 template_template_parameter_p (const_tree parm)
2903 {
2904   return DECL_TEMPLATE_TEMPLATE_PARM_P (parm);
2905 }
2906
2907 /* Return the template parameters of T if T is a
2908    primary template instantiation, NULL otherwise.  */
2909
2910 tree
2911 get_primary_template_innermost_parameters (const_tree t)
2912 {
2913   tree parms = NULL, template_info = NULL;
2914
2915   if ((template_info = get_template_info (t))
2916       && primary_template_instantiation_p (t))
2917     parms = INNERMOST_TEMPLATE_PARMS
2918         (DECL_TEMPLATE_PARMS (TI_TEMPLATE (template_info)));
2919
2920   return parms;
2921 }
2922
2923 /* Return the template parameters of the LEVELth level from the full list
2924    of template parameters PARMS.  */
2925
2926 tree
2927 get_template_parms_at_level (tree parms, int level)
2928 {
2929   tree p;
2930   if (!parms
2931       || TREE_CODE (parms) != TREE_LIST
2932       || level > TMPL_PARMS_DEPTH (parms))
2933     return NULL_TREE;
2934
2935   for (p = parms; p; p = TREE_CHAIN (p))
2936     if (TMPL_PARMS_DEPTH (p) == level)
2937       return p;
2938
2939   return NULL_TREE;
2940 }
2941
2942 /* Returns the template arguments of T if T is a template instantiation,
2943    NULL otherwise.  */
2944
2945 tree
2946 get_template_innermost_arguments (const_tree t)
2947 {
2948   tree args = NULL, template_info = NULL;
2949
2950   if ((template_info = get_template_info (t))
2951       && TI_ARGS (template_info))
2952     args = INNERMOST_TEMPLATE_ARGS (TI_ARGS (template_info));
2953
2954   return args;
2955 }
2956
2957 /* Return the argument pack elements of T if T is a template argument pack,
2958    NULL otherwise.  */
2959
2960 tree
2961 get_template_argument_pack_elems (const_tree t)
2962 {
2963   if (TREE_CODE (t) != TYPE_ARGUMENT_PACK
2964       && TREE_CODE (t) != NONTYPE_ARGUMENT_PACK)
2965     return NULL;
2966
2967   return ARGUMENT_PACK_ARGS (t);
2968 }
2969
2970 /* Structure used to track the progress of find_parameter_packs_r.  */
2971 struct find_parameter_pack_data
2972 {
2973   /* TREE_LIST that will contain all of the parameter packs found by
2974      the traversal.  */
2975   tree* parameter_packs;
2976
2977   /* Set of AST nodes that have been visited by the traversal.  */
2978   struct pointer_set_t *visited;
2979 };
2980
2981 /* Identifies all of the argument packs that occur in a template
2982    argument and appends them to the TREE_LIST inside DATA, which is a
2983    find_parameter_pack_data structure. This is a subroutine of
2984    make_pack_expansion and uses_parameter_packs.  */
2985 static tree
2986 find_parameter_packs_r (tree *tp, int *walk_subtrees, void* data)
2987 {
2988   tree t = *tp;
2989   struct find_parameter_pack_data* ppd =
2990     (struct find_parameter_pack_data*)data;
2991   bool parameter_pack_p = false;
2992
2993   /* Handle type aliases/typedefs.  */
2994   if (TYPE_P (t)
2995       && TYPE_NAME (t)
2996       && TREE_CODE (TYPE_NAME (t)) == TYPE_DECL
2997       && TYPE_DECL_ALIAS_P (TYPE_NAME (t)))
2998     {
2999       if (TYPE_TEMPLATE_INFO (t))
3000         cp_walk_tree (&TYPE_TI_ARGS (t),
3001                       &find_parameter_packs_r,
3002                       ppd, ppd->visited);
3003       *walk_subtrees = 0;
3004       return NULL_TREE;
3005     }
3006
3007   /* Identify whether this is a parameter pack or not.  */
3008   switch (TREE_CODE (t))
3009     {
3010     case TEMPLATE_PARM_INDEX:
3011       if (TEMPLATE_PARM_PARAMETER_PACK (t))
3012         parameter_pack_p = true;
3013       break;
3014
3015     case TEMPLATE_TYPE_PARM:
3016       t = TYPE_MAIN_VARIANT (t);
3017     case TEMPLATE_TEMPLATE_PARM:
3018       if (TEMPLATE_TYPE_PARAMETER_PACK (t))
3019         parameter_pack_p = true;
3020       break;
3021
3022     case PARM_DECL:
3023       if (FUNCTION_PARAMETER_PACK_P (t))
3024         {
3025           /* We don't want to walk into the type of a PARM_DECL,
3026              because we don't want to see the type parameter pack.  */
3027           *walk_subtrees = 0;
3028           parameter_pack_p = true;
3029         }
3030       break;
3031
3032     case BASES:
3033       parameter_pack_p = true;
3034       break;
3035     default:
3036       /* Not a parameter pack.  */
3037       break;
3038     }
3039
3040   if (parameter_pack_p)
3041     {
3042       /* Add this parameter pack to the list.  */
3043       *ppd->parameter_packs = tree_cons (NULL_TREE, t, *ppd->parameter_packs);
3044     }
3045
3046   if (TYPE_P (t))
3047     cp_walk_tree (&TYPE_CONTEXT (t),
3048                   &find_parameter_packs_r, ppd, ppd->visited);
3049
3050   /* This switch statement will return immediately if we don't find a
3051      parameter pack.  */
3052   switch (TREE_CODE (t))
3053     {
3054     case TEMPLATE_PARM_INDEX:
3055       return NULL_TREE;
3056
3057     case BOUND_TEMPLATE_TEMPLATE_PARM:
3058       /* Check the template itself.  */
3059       cp_walk_tree (&TREE_TYPE (TYPE_TI_TEMPLATE (t)),
3060                     &find_parameter_packs_r, ppd, ppd->visited);
3061       /* Check the template arguments.  */
3062       cp_walk_tree (&TYPE_TI_ARGS (t), &find_parameter_packs_r, ppd,
3063                     ppd->visited);
3064       *walk_subtrees = 0;
3065       return NULL_TREE;
3066
3067     case TEMPLATE_TYPE_PARM:
3068     case TEMPLATE_TEMPLATE_PARM:
3069       return NULL_TREE;
3070
3071     case PARM_DECL:
3072       return NULL_TREE;
3073
3074     case RECORD_TYPE:
3075       if (TYPE_PTRMEMFUNC_P (t))
3076         return NULL_TREE;
3077       /* Fall through.  */
3078
3079     case UNION_TYPE:
3080     case ENUMERAL_TYPE:
3081       if (TYPE_TEMPLATE_INFO (t))
3082         cp_walk_tree (&TI_ARGS (TYPE_TEMPLATE_INFO (t)),
3083                       &find_parameter_packs_r, ppd, ppd->visited);
3084
3085       *walk_subtrees = 0;
3086       return NULL_TREE;
3087
3088     case CONSTRUCTOR:
3089     case TEMPLATE_DECL:
3090       cp_walk_tree (&TREE_TYPE (t),
3091                     &find_parameter_packs_r, ppd, ppd->visited);
3092       return NULL_TREE;
3093
3094     case TYPENAME_TYPE:
3095       cp_walk_tree (&TYPENAME_TYPE_FULLNAME (t), &find_parameter_packs_r,
3096                    ppd, ppd->visited);
3097       *walk_subtrees = 0;
3098       return NULL_TREE;
3099
3100     case TYPE_PACK_EXPANSION:
3101     case EXPR_PACK_EXPANSION:
3102       *walk_subtrees = 0;
3103       return NULL_TREE;
3104
3105     case INTEGER_TYPE:
3106       cp_walk_tree (&TYPE_MAX_VALUE (t), &find_parameter_packs_r,
3107                     ppd, ppd->visited);
3108       *walk_subtrees = 0;
3109       return NULL_TREE;
3110
3111     case IDENTIFIER_NODE:
3112       cp_walk_tree (&TREE_TYPE (t), &find_parameter_packs_r, ppd,
3113                     ppd->visited);
3114       *walk_subtrees = 0;
3115       return NULL_TREE;
3116
3117     default:
3118       return NULL_TREE;
3119     }
3120
3121   return NULL_TREE;
3122 }
3123
3124 /* Determines if the expression or type T uses any parameter packs.  */
3125 bool
3126 uses_parameter_packs (tree t)
3127 {
3128   tree parameter_packs = NULL_TREE;
3129   struct find_parameter_pack_data ppd;
3130   ppd.parameter_packs = &parameter_packs;
3131   ppd.visited = pointer_set_create ();
3132   cp_walk_tree (&t, &find_parameter_packs_r, &ppd, ppd.visited);
3133   pointer_set_destroy (ppd.visited);
3134   return parameter_packs != NULL_TREE;
3135 }
3136
3137 /* Turn ARG, which may be an expression, type, or a TREE_LIST
3138    representation a base-class initializer into a parameter pack
3139    expansion. If all goes well, the resulting node will be an
3140    EXPR_PACK_EXPANSION, TYPE_PACK_EXPANSION, or TREE_LIST,
3141    respectively.  */
3142 tree
3143 make_pack_expansion (tree arg)
3144 {
3145   tree result;
3146   tree parameter_packs = NULL_TREE;
3147   bool for_types = false;
3148   struct find_parameter_pack_data ppd;
3149
3150   if (!arg || arg == error_mark_node)
3151     return arg;
3152
3153   if (TREE_CODE (arg) == TREE_LIST)
3154     {
3155       /* The only time we will see a TREE_LIST here is for a base
3156          class initializer.  In this case, the TREE_PURPOSE will be a
3157          _TYPE node (representing the base class expansion we're
3158          initializing) and the TREE_VALUE will be a TREE_LIST
3159          containing the initialization arguments.
3160
3161          The resulting expansion looks somewhat different from most
3162          expansions. Rather than returning just one _EXPANSION, we
3163          return a TREE_LIST whose TREE_PURPOSE is a
3164          TYPE_PACK_EXPANSION containing the bases that will be
3165          initialized.  The TREE_VALUE will be identical to the
3166          original TREE_VALUE, which is a list of arguments that will
3167          be passed to each base.  We do not introduce any new pack
3168          expansion nodes into the TREE_VALUE (although it is possible
3169          that some already exist), because the TREE_PURPOSE and
3170          TREE_VALUE all need to be expanded together with the same
3171          _EXPANSION node.  Note that the TYPE_PACK_EXPANSION in the
3172          resulting TREE_PURPOSE will mention the parameter packs in
3173          both the bases and the arguments to the bases.  */
3174       tree purpose;
3175       tree value;
3176       tree parameter_packs = NULL_TREE;
3177
3178       /* Determine which parameter packs will be used by the base
3179          class expansion.  */
3180       ppd.visited = pointer_set_create ();
3181       ppd.parameter_packs = &parameter_packs;
3182       cp_walk_tree (&TREE_PURPOSE (arg), &find_parameter_packs_r,
3183                     &ppd, ppd.visited);
3184
3185       if (parameter_packs == NULL_TREE)
3186         {
3187           error ("base initializer expansion %<%T%> contains no parameter packs", arg);
3188           pointer_set_destroy (ppd.visited);
3189           return error_mark_node;
3190         }
3191
3192       if (TREE_VALUE (arg) != void_type_node)
3193         {
3194           /* Collect the sets of parameter packs used in each of the
3195              initialization arguments.  */
3196           for (value = TREE_VALUE (arg); value; value = TREE_CHAIN (value))
3197             {
3198               /* Determine which parameter packs will be expanded in this
3199                  argument.  */
3200               cp_walk_tree (&TREE_VALUE (value), &find_parameter_packs_r,
3201                             &ppd, ppd.visited);
3202             }
3203         }
3204
3205       pointer_set_destroy (ppd.visited);
3206
3207       /* Create the pack expansion type for the base type.  */
3208       purpose = cxx_make_type (TYPE_PACK_EXPANSION);
3209       SET_PACK_EXPANSION_PATTERN (purpose, TREE_PURPOSE (arg));
3210       PACK_EXPANSION_PARAMETER_PACKS (purpose) = parameter_packs;
3211
3212       /* Just use structural equality for these TYPE_PACK_EXPANSIONS;
3213          they will rarely be compared to anything.  */
3214       SET_TYPE_STRUCTURAL_EQUALITY (purpose);
3215
3216       return tree_cons (purpose, TREE_VALUE (arg), NULL_TREE);
3217     }
3218
3219   if (TYPE_P (arg) || TREE_CODE (arg) == TEMPLATE_DECL)
3220     for_types = true;
3221
3222   /* Build the PACK_EXPANSION_* node.  */
3223   result = for_types
3224      ? cxx_make_type (TYPE_PACK_EXPANSION)
3225      : make_node (EXPR_PACK_EXPANSION);
3226   SET_PACK_EXPANSION_PATTERN (result, arg);
3227   if (TREE_CODE (result) == EXPR_PACK_EXPANSION)
3228     {
3229       /* Propagate type and const-expression information.  */
3230       TREE_TYPE (result) = TREE_TYPE (arg);
3231       TREE_CONSTANT (result) = TREE_CONSTANT (arg);
3232     }
3233   else
3234     /* Just use structural equality for these TYPE_PACK_EXPANSIONS;
3235        they will rarely be compared to anything.  */
3236     SET_TYPE_STRUCTURAL_EQUALITY (result);
3237
3238   /* Determine which parameter packs will be expanded.  */
3239   ppd.parameter_packs = &parameter_packs;
3240   ppd.visited = pointer_set_create ();
3241   cp_walk_tree (&arg, &find_parameter_packs_r, &ppd, ppd.visited);
3242   pointer_set_destroy (ppd.visited);
3243
3244   /* Make sure we found some parameter packs.  */
3245   if (parameter_packs == NULL_TREE)
3246     {
3247       if (TYPE_P (arg))
3248         error ("expansion pattern %<%T%> contains no argument packs", arg);
3249       else
3250         error ("expansion pattern %<%E%> contains no argument packs", arg);
3251       return error_mark_node;
3252     }
3253   PACK_EXPANSION_PARAMETER_PACKS (result) = parameter_packs;
3254
3255   PACK_EXPANSION_LOCAL_P (result) = at_function_scope_p ();
3256
3257   return result;
3258 }
3259
3260 /* Checks T for any "bare" parameter packs, which have not yet been
3261    expanded, and issues an error if any are found. This operation can
3262    only be done on full expressions or types (e.g., an expression
3263    statement, "if" condition, etc.), because we could have expressions like:
3264
3265      foo(f(g(h(args)))...)
3266
3267    where "args" is a parameter pack. check_for_bare_parameter_packs
3268    should not be called for the subexpressions args, h(args),
3269    g(h(args)), or f(g(h(args))), because we would produce erroneous
3270    error messages.
3271
3272    Returns TRUE and emits an error if there were bare parameter packs,
3273    returns FALSE otherwise.  */
3274 bool
3275 check_for_bare_parameter_packs (tree t)
3276 {
3277   tree parameter_packs = NULL_TREE;
3278   struct find_parameter_pack_data ppd;
3279
3280   if (!processing_template_decl || !t || t == error_mark_node)
3281     return false;
3282
3283   if (TREE_CODE (t) == TYPE_DECL)
3284     t = TREE_TYPE (t);
3285
3286   ppd.parameter_packs = &parameter_packs;
3287   ppd.visited = pointer_set_create ();
3288   cp_walk_tree (&t, &find_parameter_packs_r, &ppd, ppd.visited);
3289   pointer_set_destroy (ppd.visited);
3290
3291   if (parameter_packs)
3292     {
3293       error ("parameter packs not expanded with %<...%>:");
3294       while (parameter_packs)
3295         {
3296           tree pack = TREE_VALUE (parameter_packs);
3297           tree name = NULL_TREE;
3298
3299           if (TREE_CODE (pack) == TEMPLATE_TYPE_PARM
3300               || TREE_CODE (pack) == TEMPLATE_TEMPLATE_PARM)
3301             name = TYPE_NAME (pack);
3302           else if (TREE_CODE (pack) == TEMPLATE_PARM_INDEX)
3303             name = DECL_NAME (TEMPLATE_PARM_DECL (pack));
3304           else
3305             name = DECL_NAME (pack);
3306
3307           if (name)
3308             inform (input_location, "        %qD", name);
3309           else
3310             inform (input_location, "        <anonymous>");
3311
3312           parameter_packs = TREE_CHAIN (parameter_packs);
3313         }
3314
3315       return true;
3316     }
3317
3318   return false;
3319 }
3320
3321 /* Expand any parameter packs that occur in the template arguments in
3322    ARGS.  */
3323 tree
3324 expand_template_argument_pack (tree args)
3325 {
3326   tree result_args = NULL_TREE;
3327   int in_arg, out_arg = 0, nargs = args ? TREE_VEC_LENGTH (args) : 0;
3328   int num_result_args = -1;
3329   int non_default_args_count = -1;
3330
3331   /* First, determine if we need to expand anything, and the number of
3332      slots we'll need.  */
3333   for (in_arg = 0; in_arg < nargs; ++in_arg)
3334     {
3335       tree arg = TREE_VEC_ELT (args, in_arg);
3336       if (arg == NULL_TREE)
3337         return args;
3338       if (ARGUMENT_PACK_P (arg))
3339         {
3340           int num_packed = TREE_VEC_LENGTH (ARGUMENT_PACK_ARGS (arg));
3341           if (num_result_args < 0)
3342             num_result_args = in_arg + num_packed;
3343           else
3344             num_result_args += num_packed;
3345         }
3346       else
3347         {
3348           if (num_result_args >= 0)
3349             num_result_args++;
3350         }
3351     }
3352
3353   /* If no expansion is necessary, we're done.  */
3354   if (num_result_args < 0)
3355     return args;
3356
3357   /* Expand arguments.  */
3358   result_args = make_tree_vec (num_result_args);
3359   if (NON_DEFAULT_TEMPLATE_ARGS_COUNT (args))
3360     non_default_args_count =
3361       GET_NON_DEFAULT_TEMPLATE_ARGS_COUNT (args);
3362   for (in_arg = 0; in_arg < nargs; ++in_arg)
3363     {
3364       tree arg = TREE_VEC_ELT (args, in_arg);
3365       if (ARGUMENT_PACK_P (arg))
3366         {
3367           tree packed = ARGUMENT_PACK_ARGS (arg);
3368           int i, num_packed = TREE_VEC_LENGTH (packed);
3369           for (i = 0; i < num_packed; ++i, ++out_arg)
3370             TREE_VEC_ELT (result_args, out_arg) = TREE_VEC_ELT(packed, i);
3371           if (non_default_args_count > 0)
3372             non_default_args_count += num_packed;
3373         }
3374       else
3375         {
3376           TREE_VEC_ELT (result_args, out_arg) = arg;
3377           ++out_arg;
3378         }
3379     }
3380   if (non_default_args_count >= 0)
3381     SET_NON_DEFAULT_TEMPLATE_ARGS_COUNT (result_args, non_default_args_count);
3382   return result_args;
3383 }
3384
3385 /* Checks if DECL shadows a template parameter.
3386
3387    [temp.local]: A template-parameter shall not be redeclared within its
3388    scope (including nested scopes).
3389
3390    Emits an error and returns TRUE if the DECL shadows a parameter,
3391    returns FALSE otherwise.  */
3392
3393 bool
3394 check_template_shadow (tree decl)
3395 {
3396   tree olddecl;
3397
3398   /* If we're not in a template, we can't possibly shadow a template
3399      parameter.  */
3400   if (!current_template_parms)
3401     return true;
3402
3403   /* Figure out what we're shadowing.  */
3404   if (TREE_CODE (decl) == OVERLOAD)
3405     decl = OVL_CURRENT (decl);
3406   olddecl = innermost_non_namespace_value (DECL_NAME (decl));
3407
3408   /* If there's no previous binding for this name, we're not shadowing
3409      anything, let alone a template parameter.  */
3410   if (!olddecl)
3411     return true;
3412
3413   /* If we're not shadowing a template parameter, we're done.  Note
3414      that OLDDECL might be an OVERLOAD (or perhaps even an
3415      ERROR_MARK), so we can't just blithely assume it to be a _DECL
3416      node.  */
3417   if (!DECL_P (olddecl) || !DECL_TEMPLATE_PARM_P (olddecl))
3418     return true;
3419
3420   /* We check for decl != olddecl to avoid bogus errors for using a
3421      name inside a class.  We check TPFI to avoid duplicate errors for
3422      inline member templates.  */
3423   if (decl == olddecl
3424       || TEMPLATE_PARMS_FOR_INLINE (current_template_parms))
3425     return true;
3426
3427   error ("declaration of %q+#D", decl);
3428   error (" shadows template parm %q+#D", olddecl);
3429   return false;
3430 }
3431
3432 /* Return a new TEMPLATE_PARM_INDEX with the indicated INDEX, LEVEL,
3433    ORIG_LEVEL, DECL, and TYPE.  NUM_SIBLINGS is the total number of
3434    template parameters.  */
3435
3436 static tree
3437 build_template_parm_index (int index,
3438                            int level,
3439                            int orig_level,
3440                            int num_siblings,
3441                            tree decl,
3442                            tree type)
3443 {
3444   tree t = make_node (TEMPLATE_PARM_INDEX);
3445   TEMPLATE_PARM_IDX (t) = index;
3446   TEMPLATE_PARM_LEVEL (t) = level;
3447   TEMPLATE_PARM_ORIG_LEVEL (t) = orig_level;
3448   TEMPLATE_PARM_NUM_SIBLINGS (t) = num_siblings;
3449   TEMPLATE_PARM_DECL (t) = decl;
3450   TREE_TYPE (t) = type;
3451   TREE_CONSTANT (t) = TREE_CONSTANT (decl);
3452   TREE_READONLY (t) = TREE_READONLY (decl);
3453
3454   return t;
3455 }
3456
3457 /* Find the canonical type parameter for the given template type
3458    parameter.  Returns the canonical type parameter, which may be TYPE
3459    if no such parameter existed.  */
3460
3461 static tree
3462 canonical_type_parameter (tree type)
3463 {
3464   tree list;
3465   int idx = TEMPLATE_TYPE_IDX (type);
3466   if (!canonical_template_parms)
3467     canonical_template_parms = VEC_alloc (tree, gc, idx+1);
3468
3469   while (VEC_length (tree, canonical_template_parms) <= (unsigned)idx)
3470     VEC_safe_push (tree, gc, canonical_template_parms, NULL_TREE);
3471
3472   list = VEC_index (tree, canonical_template_parms, idx);
3473   while (list && !comptypes (type, TREE_VALUE (list), COMPARE_STRUCTURAL))
3474     list = TREE_CHAIN (list);
3475
3476   if (list)
3477     return TREE_VALUE (list);
3478   else
3479     {
3480       VEC_replace(tree, canonical_template_parms, idx,
3481                   tree_cons (NULL_TREE, type,
3482                              VEC_index (tree, canonical_template_parms, idx)));
3483       return type;
3484     }
3485 }
3486
3487 /* Return a TEMPLATE_PARM_INDEX, similar to INDEX, but whose
3488    TEMPLATE_PARM_LEVEL has been decreased by LEVELS.  If such a
3489    TEMPLATE_PARM_INDEX already exists, it is returned; otherwise, a
3490    new one is created.  */
3491
3492 static tree
3493 reduce_template_parm_level (tree index, tree type, int levels, tree args,
3494                             tsubst_flags_t complain)
3495 {
3496   if (TEMPLATE_PARM_DESCENDANTS (index) == NULL_TREE
3497       || (TEMPLATE_PARM_LEVEL (TEMPLATE_PARM_DESCENDANTS (index))
3498           != TEMPLATE_PARM_LEVEL (index) - levels)
3499       || !same_type_p (type, TREE_TYPE (TEMPLATE_PARM_DESCENDANTS (index))))
3500     {
3501       tree orig_decl = TEMPLATE_PARM_DECL (index);
3502       tree decl, t;
3503
3504       decl = build_decl (DECL_SOURCE_LOCATION (orig_decl),
3505                          TREE_CODE (orig_decl), DECL_NAME (orig_decl), type);
3506       TREE_CONSTANT (decl) = TREE_CONSTANT (orig_decl);
3507       TREE_READONLY (decl) = TREE_READONLY (orig_decl);
3508       DECL_ARTIFICIAL (decl) = 1;
3509       SET_DECL_TEMPLATE_PARM_P (decl);
3510
3511       t = build_template_parm_index (TEMPLATE_PARM_IDX (index),
3512                                      TEMPLATE_PARM_LEVEL (index) - levels,
3513                                      TEMPLATE_PARM_ORIG_LEVEL (index),
3514                                      TEMPLATE_PARM_NUM_SIBLINGS (index),
3515                                      decl, type);
3516       TEMPLATE_PARM_DESCENDANTS (index) = t;
3517       TEMPLATE_PARM_PARAMETER_PACK (t)
3518         = TEMPLATE_PARM_PARAMETER_PACK (index);
3519
3520         /* Template template parameters need this.  */
3521       if (TREE_CODE (decl) == TEMPLATE_DECL)
3522         DECL_TEMPLATE_PARMS (decl) = tsubst_template_parms
3523           (DECL_TEMPLATE_PARMS (TEMPLATE_PARM_DECL (index)),
3524            args, complain);
3525     }
3526
3527   return TEMPLATE_PARM_DESCENDANTS (index);
3528 }
3529
3530 /* Process information from new template parameter PARM and append it
3531    to the LIST being built.  This new parameter is a non-type
3532    parameter iff IS_NON_TYPE is true. This new parameter is a
3533    parameter pack iff IS_PARAMETER_PACK is true.  The location of PARM
3534    is in PARM_LOC. NUM_TEMPLATE_PARMS is the size of the template
3535    parameter list PARM belongs to. This is used used to create a
3536    proper canonical type for the type of PARM that is to be created,
3537    iff PARM is a type.  If the size is not known, this parameter shall
3538    be set to 0.  */
3539
3540 tree
3541 process_template_parm (tree list, location_t parm_loc, tree parm,
3542                        bool is_non_type, bool is_parameter_pack,
3543                        unsigned num_template_parms)
3544 {
3545   tree decl = 0;
3546   tree defval;
3547   tree err_parm_list;
3548   int idx = 0;
3549
3550   gcc_assert (TREE_CODE (parm) == TREE_LIST);
3551   defval = TREE_PURPOSE (parm);
3552
3553   if (list)
3554     {
3555       tree p = tree_last (list);
3556
3557       if (p && TREE_VALUE (p) != error_mark_node)
3558         {
3559           p = TREE_VALUE (p);