gcc/cp/pt.c

   1 /* Handle parameterized types (templates) for GNU C++.
   2    Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998, 1999, 2000,
   3    2001, 2002, 2003, 2004, 2005, 2007, 2008, 2009, 2010, 2011
   4    Free Software Foundation, Inc.
   5    Written by Ken Raeburn (raeburn@cygnus.com) while at Watchmaker Computing.
   6    Rewritten by Jason Merrill (jason@cygnus.com).
   7
   8 This file is part of GCC.
   9
  10 GCC is free software; you can redistribute it and/or modify
  11 it under the terms of the GNU General Public License as published by
  12 the Free Software Foundation; either version 3, or (at your option)
  13 any later version.
  14
  15 GCC is distributed in the hope that it will be useful,
  16 but WITHOUT ANY WARRANTY; without even the implied warranty of
  17 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  18 GNU General Public License for more details.
  19
  20 You should have received a copy of the GNU General Public License
  21 along with GCC; see the file COPYING3.  If not see
  22 <http://www.gnu.org/licenses/>.  */
  23
  24 /* Known bugs or deficiencies include:
  25
  26      all methods must be provided in header files; can't use a source
  27      file that contains only the method templates and "just win".  */
  28
  29 #include "config.h"
  30 #include "system.h"
  31 #include "coretypes.h"
  32 #include "tm.h"
  33 #include "tree.h"
  34 #include "intl.h"
  35 #include "pointer-set.h"
  36 #include "flags.h"
  37 #include "cp-tree.h"
  38 #include "c-family/c-common.h"
  39 #include "c-family/c-objc.h"
  40 #include "cp-objcp-common.h"
  41 #include "tree-inline.h"
  42 #include "decl.h"
  43 #include "output.h"
  44 #include "toplev.h"
  45 #include "timevar.h"
  46 #include "tree-iterator.h"
  47 #include "vecprim.h"
  48
  49 /* The type of functions taking a tree, and some additional data, and
  50    returning an int.  */
  51 typedef int (*tree_fn_t) (tree, void*);
  52
  53 /* The PENDING_TEMPLATES is a TREE_LIST of templates whose
  54    instantiations have been deferred, either because their definitions
  55    were not yet available, or because we were putting off doing the work.  */
  56 struct GTY ((chain_next ("%h.next"))) pending_template {
  57   struct pending_template *next;
  58   struct tinst_level *tinst;
  59 };
  60
  61 static GTY(()) struct pending_template *pending_templates;
  62 static GTY(()) struct pending_template *last_pending_template;
  63
  64 int processing_template_parmlist;
  65 static int template_header_count;
  66
  67 static GTY(()) tree saved_trees;
  68 static VEC(int,heap) *inline_parm_levels;
  69
  70 static GTY(()) struct tinst_level *current_tinst_level;
  71
  72 static GTY(()) tree saved_access_scope;
  73
  74 /* Live only within one (recursive) call to tsubst_expr.  We use
  75    this to pass the statement expression node from the STMT_EXPR
  76    to the EXPR_STMT that is its result.  */
  77 static tree cur_stmt_expr;
  78
  79 /* A map from local variable declarations in the body of the template
  80    presently being instantiated to the corresponding instantiated
  81    local variables.  */
  82 static htab_t local_specializations;
  83
  84 typedef struct GTY(()) spec_entry
  85 {
  86   tree tmpl;
  87   tree args;
  88   tree spec;
  89 } spec_entry;
  90
  91 static GTY ((param_is (spec_entry)))
  92   htab_t decl_specializations;
  93
  94 static GTY ((param_is (spec_entry)))
  95   htab_t type_specializations;
  96
  97 /* Contains canonical template parameter types. The vector is indexed by
  98    the TEMPLATE_TYPE_IDX of the template parameter. Each element is a
  99    TREE_LIST, whose TREE_VALUEs contain the canonical template
 100    parameters of various types and levels.  */
 101 static GTY(()) VEC(tree,gc) *canonical_template_parms;
 102
 103 #define UNIFY_ALLOW_NONE 0
 104 #define UNIFY_ALLOW_MORE_CV_QUAL 1
 105 #define UNIFY_ALLOW_LESS_CV_QUAL 2
 106 #define UNIFY_ALLOW_DERIVED 4
 107 #define UNIFY_ALLOW_INTEGER 8
 108 #define UNIFY_ALLOW_OUTER_LEVEL 16
 109 #define UNIFY_ALLOW_OUTER_MORE_CV_QUAL 32
 110 #define UNIFY_ALLOW_OUTER_LESS_CV_QUAL 64
 111
 112 enum template_base_result {
 113   tbr_incomplete_type,
 114   tbr_ambiguous_baseclass,
 115   tbr_success
 116 };
 117
 118 static void push_access_scope (tree);
 119 static void pop_access_scope (tree);
 120 static void push_deduction_access_scope (tree);
 121 static void pop_deduction_access_scope (tree);
 122 static bool resolve_overloaded_unification (tree, tree, tree, tree,
 123                                             unification_kind_t, int,
 124                                             bool);
 125 static int try_one_overload (tree, tree, tree, tree, tree,
 126                              unification_kind_t, int, bool, bool);
 127 static int unify (tree, tree, tree, tree, int, bool);
 128 static void add_pending_template (tree);
 129 static tree reopen_tinst_level (struct tinst_level *);
 130 static tree tsubst_initializer_list (tree, tree);
 131 static tree get_class_bindings (tree, tree, tree);
 132 static tree coerce_template_parms (tree, tree, tree, tsubst_flags_t,
 133                                    bool, bool);
 134 static void tsubst_enum (tree, tree, tree);
 135 static tree add_to_template_args (tree, tree);
 136 static tree add_outermost_template_args (tree, tree);
 137 static bool check_instantiated_args (tree, tree, tsubst_flags_t);
 138 static int maybe_adjust_types_for_deduction (unification_kind_t, tree*, tree*,
 139                                              tree);
 140 static int type_unification_real (tree, tree, tree, const tree *,
 141                                   unsigned int, int, unification_kind_t, int,
 142                                   bool);
 143 static void note_template_header (int);
 144 static tree convert_nontype_argument_function (tree, tree);
 145 static tree convert_nontype_argument (tree, tree, tsubst_flags_t);
 146 static tree convert_template_argument (tree, tree, tree,
 147                                        tsubst_flags_t, int, tree);
 148 static int for_each_template_parm (tree, tree_fn_t, void*,
 149                                    struct pointer_set_t*, bool);
 150 static tree expand_template_argument_pack (tree);
 151 static tree build_template_parm_index (int, int, int, int, tree, tree);
 152 static bool inline_needs_template_parms (tree);
 153 static void push_inline_template_parms_recursive (tree, int);
 154 static tree retrieve_local_specialization (tree);
 155 static void register_local_specialization (tree, tree);
 156 static hashval_t hash_specialization (const void *p);
 157 static tree reduce_template_parm_level (tree, tree, int, tree, tsubst_flags_t);
 158 static int mark_template_parm (tree, void *);
 159 static int template_parm_this_level_p (tree, void *);
 160 static tree tsubst_friend_function (tree, tree);
 161 static tree tsubst_friend_class (tree, tree);
 162 static int can_complete_type_without_circularity (tree);
 163 static tree get_bindings (tree, tree, tree, bool);
 164 static int template_decl_level (tree);
 165 static int check_cv_quals_for_unify (int, tree, tree);
 166 static void template_parm_level_and_index (tree, int*, int*);
 167 static int unify_pack_expansion (tree, tree, tree,
 168                                  tree, unification_kind_t, bool, bool);
 169 static tree tsubst_template_arg (tree, tree, tsubst_flags_t, tree);
 170 static tree tsubst_template_args (tree, tree, tsubst_flags_t, tree);
 171 static tree tsubst_template_parms (tree, tree, tsubst_flags_t);
 172 static void regenerate_decl_from_template (tree, tree);
 173 static tree most_specialized_class (tree, tree, tsubst_flags_t);
 174 static tree tsubst_aggr_type (tree, tree, tsubst_flags_t, tree, int);
 175 static tree tsubst_arg_types (tree, tree, tsubst_flags_t, tree);
 176 static tree tsubst_function_type (tree, tree, tsubst_flags_t, tree);
 177 static bool check_specialization_scope (void);
 178 static tree process_partial_specialization (tree);
 179 static void set_current_access_from_decl (tree);
 180 static enum template_base_result get_template_base (tree, tree, tree, tree,
 181                                                     bool , tree *);
 182 static tree try_class_unification (tree, tree, tree, tree, bool);
 183 static int coerce_template_template_parms (tree, tree, tsubst_flags_t,
 184                                            tree, tree);
 185 static bool template_template_parm_bindings_ok_p (tree, tree);
 186 static int template_args_equal (tree, tree);
 187 static void tsubst_default_arguments (tree);
 188 static tree for_each_template_parm_r (tree *, int *, void *);
 189 static tree copy_default_args_to_explicit_spec_1 (tree, tree);
 190 static void copy_default_args_to_explicit_spec (tree);
 191 static int invalid_nontype_parm_type_p (tree, tsubst_flags_t);
 192 static int eq_local_specializations (const void *, const void *);
 193 static bool dependent_template_arg_p (tree);
 194 static bool any_template_arguments_need_structural_equality_p (tree);
 195 static bool dependent_type_p_r (tree);
 196 static tree tsubst_expr (tree, tree, tsubst_flags_t, tree, bool);
 197 static tree tsubst_copy (tree, tree, tsubst_flags_t, tree);
 198 static tree tsubst_pack_expansion (tree, tree, tsubst_flags_t, tree);
 199 static tree tsubst_decl (tree, tree, tsubst_flags_t);
 200 static void perform_typedefs_access_check (tree tmpl, tree targs);
 201 static void append_type_to_template_for_access_check_1 (tree, tree, tree,
 202                                                         location_t);
 203 static tree listify (tree);
 204 static tree listify_autos (tree, tree);
 205 static tree template_parm_to_arg (tree t);
 206 static bool arg_from_parm_pack_p (tree, tree);
 207 static tree current_template_args (void);
 208 static tree fixup_template_type_parm_type (tree, int);
 209 static tree fixup_template_parm_index (tree, tree, int);
 210 static tree tsubst_template_parm (tree, tree, tsubst_flags_t);
 211
 212 /* Make the current scope suitable for access checking when we are
 213    processing T.  T can be FUNCTION_DECL for instantiated function
 214    template, or VAR_DECL for static member variable (need by
 215    instantiate_decl).  */
 216
 217 static void
 218 push_access_scope (tree t)
 219 {
 220   gcc_assert (TREE_CODE (t) == FUNCTION_DECL
 221               || TREE_CODE (t) == VAR_DECL);
 222
 223   if (DECL_FRIEND_CONTEXT (t))
 224     push_nested_class (DECL_FRIEND_CONTEXT (t));
 225   else if (DECL_CLASS_SCOPE_P (t))
 226     push_nested_class (DECL_CONTEXT (t));
 227   else
 228     push_to_top_level ();
 229
 230   if (TREE_CODE (t) == FUNCTION_DECL)
 231     {
 232       saved_access_scope = tree_cons
 233         (NULL_TREE, current_function_decl, saved_access_scope);
 234       current_function_decl = t;
 235     }
 236 }
 237
 238 /* Restore the scope set up by push_access_scope.  T is the node we
 239    are processing.  */
 240
 241 static void
 242 pop_access_scope (tree t)
 243 {
 244   if (TREE_CODE (t) == FUNCTION_DECL)
 245     {
 246       current_function_decl = TREE_VALUE (saved_access_scope);
 247       saved_access_scope = TREE_CHAIN (saved_access_scope);
 248     }
 249
 250   if (DECL_FRIEND_CONTEXT (t) || DECL_CLASS_SCOPE_P (t))
 251     pop_nested_class ();
 252   else
 253     pop_from_top_level ();
 254 }
 255
 256 /* Do any processing required when DECL (a member template
 257    declaration) is finished.  Returns the TEMPLATE_DECL corresponding
 258    to DECL, unless it is a specialization, in which case the DECL
 259    itself is returned.  */
 260
 261 tree
 262 finish_member_template_decl (tree decl)
 263 {
 264   if (decl == error_mark_node)
 265     return error_mark_node;
 266
 267   gcc_assert (DECL_P (decl));
 268
 269   if (TREE_CODE (decl) == TYPE_DECL)
 270     {
 271       tree type;
 272
 273       type = TREE_TYPE (decl);
 274       if (type == error_mark_node)
 275         return error_mark_node;
 276       if (MAYBE_CLASS_TYPE_P (type)
 277           && CLASSTYPE_TEMPLATE_INFO (type)
 278           && !CLASSTYPE_TEMPLATE_SPECIALIZATION (type))
 279         {
 280           tree tmpl = CLASSTYPE_TI_TEMPLATE (type);
 281           check_member_template (tmpl);
 282           return tmpl;
 283         }
 284       return NULL_TREE;
 285     }
 286   else if (TREE_CODE (decl) == FIELD_DECL)
 287     error ("data member %qD cannot be a member template", decl);
 288   else if (DECL_TEMPLATE_INFO (decl))
 289     {
 290       if (!DECL_TEMPLATE_SPECIALIZATION (decl))
 291         {
 292           check_member_template (DECL_TI_TEMPLATE (decl));
 293           return DECL_TI_TEMPLATE (decl);
 294         }
 295       else
 296         return decl;
 297     }
 298   else
 299     error ("invalid member template declaration %qD", decl);
 300
 301   return error_mark_node;
 302 }
 303
 304 /* Create a template info node.  */
 305
 306 tree
 307 build_template_info (tree template_decl, tree template_args)
 308 {
 309   tree result = make_node (TEMPLATE_INFO);
 310   TI_TEMPLATE (result) = template_decl;
 311   TI_ARGS (result) = template_args;
 312   return result;
 313 }
 314
 315 /* Return the template info node corresponding to T, whatever T is.  */
 316
 317 tree
 318 get_template_info (const_tree t)
 319 {
 320   tree tinfo = NULL_TREE;
 321
 322   if (!t || t == error_mark_node)
 323     return NULL;
 324
 325   if (DECL_P (t) && DECL_LANG_SPECIFIC (t))
 326     tinfo = DECL_TEMPLATE_INFO (t);
 327
 328   if (!tinfo && DECL_IMPLICIT_TYPEDEF_P (t))
 329     t = TREE_TYPE (t);
 330
 331   if (TAGGED_TYPE_P (t))
 332     tinfo = TYPE_TEMPLATE_INFO (t);
 333   else if (TREE_CODE (t) == BOUND_TEMPLATE_TEMPLATE_PARM)
 334     tinfo = TEMPLATE_TEMPLATE_PARM_TEMPLATE_INFO (t);
 335
 336   return tinfo;
 337 }
 338
 339 /* Returns the template nesting level of the indicated class TYPE.
 340
 341    For example, in:
 342      template <class T>
 343      struct A
 344      {
 345        template <class U>
 346        struct B {};
 347      };
 348
 349    A<T>::B<U> has depth two, while A<T> has depth one.
 350    Both A<T>::B<int> and A<int>::B<U> have depth one, if
 351    they are instantiations, not specializations.
 352
 353    This function is guaranteed to return 0 if passed NULL_TREE so
 354    that, for example, `template_class_depth (current_class_type)' is
 355    always safe.  */
 356
 357 int
 358 template_class_depth (tree type)
 359 {
 360   int depth;
 361
 362   for (depth = 0;
 363        type && TREE_CODE (type) != NAMESPACE_DECL;
 364        type = (TREE_CODE (type) == FUNCTION_DECL)
 365          ? CP_DECL_CONTEXT (type) : CP_TYPE_CONTEXT (type))
 366     {
 367       tree tinfo = get_template_info (type);
 368
 369       if (tinfo && PRIMARY_TEMPLATE_P (TI_TEMPLATE (tinfo))
 370           && uses_template_parms (INNERMOST_TEMPLATE_ARGS (TI_ARGS (tinfo))))
 371         ++depth;
 372     }
 373
 374   return depth;
 375 }
 376
 377 /* Subroutine of maybe_begin_member_template_processing.
 378    Returns true if processing DECL needs us to push template parms.  */
 379
 380 static bool
 381 inline_needs_template_parms (tree decl)
 382 {
 383   if (! DECL_TEMPLATE_INFO (decl))
 384     return false;
 385
 386   return (TMPL_PARMS_DEPTH (DECL_TEMPLATE_PARMS (most_general_template (decl)))
 387           > (processing_template_decl + DECL_TEMPLATE_SPECIALIZATION (decl)));
 388 }
 389
 390 /* Subroutine of maybe_begin_member_template_processing.
 391    Push the template parms in PARMS, starting from LEVELS steps into the
 392    chain, and ending at the beginning, since template parms are listed
 393    innermost first.  */
 394
 395 static void
 396 push_inline_template_parms_recursive (tree parmlist, int levels)
 397 {
 398   tree parms = TREE_VALUE (parmlist);
 399   int i;
 400
 401   if (levels > 1)
 402     push_inline_template_parms_recursive (TREE_CHAIN (parmlist), levels - 1);
 403
 404   ++processing_template_decl;
 405   current_template_parms
 406     = tree_cons (size_int (processing_template_decl),
 407                  parms, current_template_parms);
 408   TEMPLATE_PARMS_FOR_INLINE (current_template_parms) = 1;
 409
 410   begin_scope (TREE_VEC_LENGTH (parms) ? sk_template_parms : sk_template_spec,
 411                NULL);
 412   for (i = 0; i < TREE_VEC_LENGTH (parms); ++i)
 413     {
 414       tree parm = TREE_VALUE (TREE_VEC_ELT (parms, i));
 415
 416       if (parm == error_mark_node)
 417         continue;
 418
 419       gcc_assert (DECL_P (parm));
 420
 421       switch (TREE_CODE (parm))
 422         {
 423         case TYPE_DECL:
 424         case TEMPLATE_DECL:
 425           pushdecl (parm);
 426           break;
 427
 428         case PARM_DECL:
 429           {
 430             /* Make a CONST_DECL as is done in process_template_parm.
 431                It is ugly that we recreate this here; the original
 432                version built in process_template_parm is no longer
 433                available.  */
 434             tree decl = build_decl (DECL_SOURCE_LOCATION (parm),
 435                                     CONST_DECL, DECL_NAME (parm),
 436                                     TREE_TYPE (parm));
 437             DECL_ARTIFICIAL (decl) = 1;
 438             TREE_CONSTANT (decl) = 1;
 439             TREE_READONLY (decl) = 1;
 440             DECL_INITIAL (decl) = DECL_INITIAL (parm);
 441             SET_DECL_TEMPLATE_PARM_P (decl);
 442             pushdecl (decl);
 443           }
 444           break;
 445
 446         default:
 447           gcc_unreachable ();
 448         }
 449     }
 450 }
 451
 452 /* Restore the template parameter context for a member template or
 453    a friend template defined in a class definition.  */
 454
 455 void
 456 maybe_begin_member_template_processing (tree decl)
 457 {
 458   tree parms;
 459   int levels = 0;
 460
 461   if (inline_needs_template_parms (decl))
 462     {
 463       parms = DECL_TEMPLATE_PARMS (most_general_template (decl));
 464       levels = TMPL_PARMS_DEPTH (parms) - processing_template_decl;
 465
 466       if (DECL_TEMPLATE_SPECIALIZATION (decl))
 467         {
 468           --levels;
 469           parms = TREE_CHAIN (parms);
 470         }
 471
 472       push_inline_template_parms_recursive (parms, levels);
 473     }
 474
 475   /* Remember how many levels of template parameters we pushed so that
 476      we can pop them later.  */
 477   VEC_safe_push (int, heap, inline_parm_levels, levels);
 478 }
 479
 480 /* Undo the effects of maybe_begin_member_template_processing.  */
 481
 482 void
 483 maybe_end_member_template_processing (void)
 484 {
 485   int i;
 486   int last;
 487
 488   if (VEC_length (int, inline_parm_levels) == 0)
 489     return;
 490
 491   last = VEC_pop (int, inline_parm_levels);
 492   for (i = 0; i < last; ++i)
 493     {
 494       --processing_template_decl;
 495       current_template_parms = TREE_CHAIN (current_template_parms);
 496       poplevel (0, 0, 0);
 497     }
 498 }
 499
 500 /* Return a new template argument vector which contains all of ARGS,
 501    but has as its innermost set of arguments the EXTRA_ARGS.  */
 502
 503 static tree
 504 add_to_template_args (tree args, tree extra_args)
 505 {
 506   tree new_args;
 507   int extra_depth;
 508   int i;
 509   int j;
 510
 511   if (args == NULL_TREE || extra_args == error_mark_node)
 512     return extra_args;
 513
 514   extra_depth = TMPL_ARGS_DEPTH (extra_args);
 515   new_args = make_tree_vec (TMPL_ARGS_DEPTH (args) + extra_depth);
 516
 517   for (i = 1; i <= TMPL_ARGS_DEPTH (args); ++i)
 518     SET_TMPL_ARGS_LEVEL (new_args, i, TMPL_ARGS_LEVEL (args, i));
 519
 520   for (j = 1; j <= extra_depth; ++j, ++i)
 521     SET_TMPL_ARGS_LEVEL (new_args, i, TMPL_ARGS_LEVEL (extra_args, j));
 522
 523   return new_args;
 524 }
 525
 526 /* Like add_to_template_args, but only the outermost ARGS are added to
 527    the EXTRA_ARGS.  In particular, all but TMPL_ARGS_DEPTH
 528    (EXTRA_ARGS) levels are added.  This function is used to combine
 529    the template arguments from a partial instantiation with the
 530    template arguments used to attain the full instantiation from the
 531    partial instantiation.  */
 532
 533 static tree
 534 add_outermost_template_args (tree args, tree extra_args)
 535 {
 536   tree new_args;
 537
 538   /* If there are more levels of EXTRA_ARGS than there are ARGS,
 539      something very fishy is going on.  */
 540   gcc_assert (TMPL_ARGS_DEPTH (args) >= TMPL_ARGS_DEPTH (extra_args));
 541
 542   /* If *all* the new arguments will be the EXTRA_ARGS, just return
 543      them.  */
 544   if (TMPL_ARGS_DEPTH (args) == TMPL_ARGS_DEPTH (extra_args))
 545     return extra_args;
 546
 547   /* For the moment, we make ARGS look like it contains fewer levels.  */
 548   TREE_VEC_LENGTH (args) -= TMPL_ARGS_DEPTH (extra_args);
 549
 550   new_args = add_to_template_args (args, extra_args);
 551
 552   /* Now, we restore ARGS to its full dimensions.  */
 553   TREE_VEC_LENGTH (args) += TMPL_ARGS_DEPTH (extra_args);
 554
 555   return new_args;
 556 }
 557
 558 /* Return the N levels of innermost template arguments from the ARGS.  */
 559
 560 tree
 561 get_innermost_template_args (tree args, int n)
 562 {
 563   tree new_args;
 564   int extra_levels;
 565   int i;
 566
 567   gcc_assert (n >= 0);
 568
 569   /* If N is 1, just return the innermost set of template arguments.  */
 570   if (n == 1)
 571     return TMPL_ARGS_LEVEL (args, TMPL_ARGS_DEPTH (args));
 572
 573   /* If we're not removing anything, just return the arguments we were
 574      given.  */
 575   extra_levels = TMPL_ARGS_DEPTH (args) - n;
 576   gcc_assert (extra_levels >= 0);
 577   if (extra_levels == 0)
 578     return args;
 579
 580   /* Make a new set of arguments, not containing the outer arguments.  */
 581   new_args = make_tree_vec (n);
 582   for (i = 1; i <= n; ++i)
 583     SET_TMPL_ARGS_LEVEL (new_args, i,
 584                          TMPL_ARGS_LEVEL (args, i + extra_levels));
 585
 586   return new_args;
 587 }
 588
 589 /* The inverse of get_innermost_template_args: Return all but the innermost
 590    EXTRA_LEVELS levels of template arguments from the ARGS.  */
 591
 592 static tree
 593 strip_innermost_template_args (tree args, int extra_levels)
 594 {
 595   tree new_args;
 596   int n = TMPL_ARGS_DEPTH (args) - extra_levels;
 597   int i;
 598
 599   gcc_assert (n >= 0);
 600
 601   /* If N is 1, just return the outermost set of template arguments.  */
 602   if (n == 1)
 603     return TMPL_ARGS_LEVEL (args, 1);
 604
 605   /* If we're not removing anything, just return the arguments we were
 606      given.  */
 607   gcc_assert (extra_levels >= 0);
 608   if (extra_levels == 0)
 609     return args;
 610
 611   /* Make a new set of arguments, not containing the inner arguments.  */
 612   new_args = make_tree_vec (n);
 613   for (i = 1; i <= n; ++i)
 614     SET_TMPL_ARGS_LEVEL (new_args, i,
 615                          TMPL_ARGS_LEVEL (args, i));
 616
 617   return new_args;
 618 }
 619
 620 /* We've got a template header coming up; push to a new level for storing
 621    the parms.  */
 622
 623 void
 624 begin_template_parm_list (void)
 625 {
 626   /* We use a non-tag-transparent scope here, which causes pushtag to
 627      put tags in this scope, rather than in the enclosing class or
 628      namespace scope.  This is the right thing, since we want
 629      TEMPLATE_DECLS, and not TYPE_DECLS for template classes.  For a
 630      global template class, push_template_decl handles putting the
 631      TEMPLATE_DECL into top-level scope.  For a nested template class,
 632      e.g.:
 633
 634        template <class T> struct S1 {
 635          template <class T> struct S2 {};
 636        };
 637
 638      pushtag contains special code to call pushdecl_with_scope on the
 639      TEMPLATE_DECL for S2.  */
 640   begin_scope (sk_template_parms, NULL);
 641   ++processing_template_decl;
 642   ++processing_template_parmlist;
 643   note_template_header (0);
 644 }
 645
 646 /* This routine is called when a specialization is declared.  If it is
 647    invalid to declare a specialization here, an error is reported and
 648    false is returned, otherwise this routine will return true.  */
 649
 650 static bool
 651 check_specialization_scope (void)
 652 {
 653   tree scope = current_scope ();
 654
 655   /* [temp.expl.spec]
 656
 657      An explicit specialization shall be declared in the namespace of
 658      which the template is a member, or, for member templates, in the
 659      namespace of which the enclosing class or enclosing class
 660      template is a member.  An explicit specialization of a member
 661      function, member class or static data member of a class template
 662      shall be declared in the namespace of which the class template
 663      is a member.  */
 664   if (scope && TREE_CODE (scope) != NAMESPACE_DECL)
 665     {
 666       error ("explicit specialization in non-namespace scope %qD", scope);
 667       return false;
 668     }
 669
 670   /* [temp.expl.spec]
 671
 672      In an explicit specialization declaration for a member of a class
 673      template or a member template that appears in namespace scope,
 674      the member template and some of its enclosing class templates may
 675      remain unspecialized, except that the declaration shall not
 676      explicitly specialize a class member template if its enclosing
 677      class templates are not explicitly specialized as well.  */
 678   if (current_template_parms)
 679     {
 680       error ("enclosing class templates are not explicitly specialized");
 681       return false;
 682     }
 683
 684   return true;
 685 }
 686
 687 /* We've just seen template <>.  */
 688
 689 bool
 690 begin_specialization (void)
 691 {
 692   begin_scope (sk_template_spec, NULL);
 693   note_template_header (1);
 694   return check_specialization_scope ();
 695 }
 696
 697 /* Called at then end of processing a declaration preceded by
 698    template<>.  */
 699
 700 void
 701 end_specialization (void)
 702 {
 703   finish_scope ();
 704   reset_specialization ();
 705 }
 706
 707 /* Any template <>'s that we have seen thus far are not referring to a
 708    function specialization.  */
 709
 710 void
 711 reset_specialization (void)
 712 {
 713   processing_specialization = 0;
 714   template_header_count = 0;
 715 }
 716
 717 /* We've just seen a template header.  If SPECIALIZATION is nonzero,
 718    it was of the form template <>.  */
 719
 720 static void
 721 note_template_header (int specialization)
 722 {
 723   processing_specialization = specialization;
 724   template_header_count++;
 725 }
 726
 727 /* We're beginning an explicit instantiation.  */
 728
 729 void
 730 begin_explicit_instantiation (void)
 731 {
 732   gcc_assert (!processing_explicit_instantiation);
 733   processing_explicit_instantiation = true;
 734 }
 735
 736
 737 void
 738 end_explicit_instantiation (void)
 739 {
 740   gcc_assert (processing_explicit_instantiation);
 741   processing_explicit_instantiation = false;
 742 }
 743
 744 /* An explicit specialization or partial specialization TMPL is being
 745    declared.  Check that the namespace in which the specialization is
 746    occurring is permissible.  Returns false iff it is invalid to
 747    specialize TMPL in the current namespace.  */
 748
 749 static bool
 750 check_specialization_namespace (tree tmpl)
 751 {
 752   tree tpl_ns = decl_namespace_context (tmpl);
 753
 754   /* [tmpl.expl.spec]
 755
 756      An explicit specialization shall be declared in the namespace of
 757      which the template is a member, or, for member templates, in the
 758      namespace of which the enclosing class or enclosing class
 759      template is a member.  An explicit specialization of a member
 760      function, member class or static data member of a class template
 761      shall be declared in the namespace of which the class template is
 762      a member.  */
 763   if (current_scope() != DECL_CONTEXT (tmpl)
 764       && !at_namespace_scope_p ())
 765     {
 766       error ("specialization of %qD must appear at namespace scope", tmpl);
 767       return false;
 768     }
 769   if (is_associated_namespace (current_namespace, tpl_ns))
 770     /* Same or super-using namespace.  */
 771     return true;
 772   else
 773     {
 774       permerror (input_location, "specialization of %qD in different namespace", tmpl);
 775       permerror (input_location, "  from definition of %q+#D", tmpl);
 776       return false;
 777     }
 778 }
 779
 780 /* SPEC is an explicit instantiation.  Check that it is valid to
 781    perform this explicit instantiation in the current namespace.  */
 782
 783 static void
 784 check_explicit_instantiation_namespace (tree spec)
 785 {
 786   tree ns;
 787
 788   /* DR 275: An explicit instantiation shall appear in an enclosing
 789      namespace of its template.  */
 790   ns = decl_namespace_context (spec);
 791   if (!is_ancestor (current_namespace, ns))
 792     permerror (input_location, "explicit instantiation of %qD in namespace %qD "
 793                "(which does not enclose namespace %qD)",
 794                spec, current_namespace, ns);
 795 }
 796
 797 /* The TYPE is being declared.  If it is a template type, that means it
 798    is a partial specialization.  Do appropriate error-checking.  */
 799
 800 tree
 801 maybe_process_partial_specialization (tree type)
 802 {
 803   tree context;
 804
 805   if (type == error_mark_node)
 806     return error_mark_node;
 807
 808   if (TREE_CODE (type) == BOUND_TEMPLATE_TEMPLATE_PARM)
 809     {
 810       error ("name of class shadows template template parameter %qD",
 811              TYPE_NAME (type));
 812       return error_mark_node;
 813     }
 814
 815   context = TYPE_CONTEXT (type);
 816
 817   if ((CLASS_TYPE_P (type) && CLASSTYPE_USE_TEMPLATE (type))
 818       /* Consider non-class instantiations of alias templates as
 819          well.  */
 820       || (TYPE_P (type)
 821           && TYPE_TEMPLATE_INFO (type)
 822           && DECL_LANG_SPECIFIC (TYPE_NAME (type))
 823           && DECL_USE_TEMPLATE (TYPE_NAME (type))))
 824     {
 825       /* This is for ordinary explicit specialization and partial
 826          specialization of a template class such as:
 827
 828            template <> class C<int>;
 829
 830          or:
 831
 832            template <class T> class C<T*>;
 833
 834          Make sure that `C<int>' and `C<T*>' are implicit instantiations.  */
 835
 836       if (CLASS_TYPE_P (type)
 837           && CLASSTYPE_IMPLICIT_INSTANTIATION (type)
 838           && !COMPLETE_TYPE_P (type))
 839         {
 840           check_specialization_namespace (CLASSTYPE_TI_TEMPLATE (type));
 841           SET_CLASSTYPE_TEMPLATE_SPECIALIZATION (type);
 842           if (processing_template_decl)
 843             {
 844               if (push_template_decl (TYPE_MAIN_DECL (type))
 845                   == error_mark_node)
 846                 return error_mark_node;
 847             }
 848         }
 849       else if (CLASS_TYPE_P (type)
 850                && CLASSTYPE_TEMPLATE_INSTANTIATION (type))
 851         error ("specialization of %qT after instantiation", type);
 852
 853       if (DECL_ALIAS_TEMPLATE_P (TYPE_TI_TEMPLATE (type)))
 854         {
 855           error ("partial specialization of alias template %qD",
 856                  TYPE_TI_TEMPLATE (type));
 857           return error_mark_node;
 858         }
 859     }
 860   else if (CLASS_TYPE_P (type)
 861            && !CLASSTYPE_USE_TEMPLATE (type)
 862            && CLASSTYPE_TEMPLATE_INFO (type)
 863            && context && CLASS_TYPE_P (context)
 864            && CLASSTYPE_TEMPLATE_INFO (context))
 865     {
 866       /* This is for an explicit specialization of member class
 867          template according to [temp.expl.spec/18]:
 868
 869            template <> template <class U> class C<int>::D;
 870
 871          The context `C<int>' must be an implicit instantiation.
 872          Otherwise this is just a member class template declared
 873          earlier like:
 874
 875            template <> class C<int> { template <class U> class D; };
 876            template <> template <class U> class C<int>::D;
 877
 878          In the first case, `C<int>::D' is a specialization of `C<T>::D'
 879          while in the second case, `C<int>::D' is a primary template
 880          and `C<T>::D' may not exist.  */
 881
 882       if (CLASSTYPE_IMPLICIT_INSTANTIATION (context)
 883           && !COMPLETE_TYPE_P (type))
 884         {
 885           tree t;
 886           tree tmpl = CLASSTYPE_TI_TEMPLATE (type);
 887
 888           if (current_namespace
 889               != decl_namespace_context (tmpl))
 890             {
 891               permerror (input_location, "specializing %q#T in different namespace", type);
 892               permerror (input_location, "  from definition of %q+#D", tmpl);
 893             }
 894
 895           /* Check for invalid specialization after instantiation:
 896
 897                template <> template <> class C<int>::D<int>;
 898                template <> template <class U> class C<int>::D;  */
 899
 900           for (t = DECL_TEMPLATE_INSTANTIATIONS (tmpl);
 901                t; t = TREE_CHAIN (t))
 902             {
 903               tree inst = TREE_VALUE (t);
 904               if (CLASSTYPE_TEMPLATE_SPECIALIZATION (inst))
 905                 {
 906                   /* We already have a full specialization of this partial
 907                      instantiation.  Reassign it to the new member
 908                      specialization template.  */
 909                   spec_entry elt;
 910                   spec_entry *entry;
 911                   void **slot;
 912
 913                   elt.tmpl = most_general_template (tmpl);
 914                   elt.args = CLASSTYPE_TI_ARGS (inst);
 915                   elt.spec = inst;
 916
 917                   htab_remove_elt (type_specializations, &elt);
 918
 919                   elt.tmpl = tmpl;
 920                   elt.args = INNERMOST_TEMPLATE_ARGS (elt.args);
 921
 922                   slot = htab_find_slot (type_specializations, &elt, INSERT);
 923                   entry = ggc_alloc_spec_entry ();
 924                   *entry = elt;
 925                   *slot = entry;
 926                 }
 927               else if (COMPLETE_OR_OPEN_TYPE_P (inst))
 928                 /* But if we've had an implicit instantiation, that's a
 929                    problem ([temp.expl.spec]/6).  */
 930                 error ("specialization %qT after instantiation %qT",
 931                        type, inst);
 932             }
 933
 934           /* Mark TYPE as a specialization.  And as a result, we only
 935              have one level of template argument for the innermost
 936              class template.  */
 937           SET_CLASSTYPE_TEMPLATE_SPECIALIZATION (type);
 938           CLASSTYPE_TI_ARGS (type)
 939             = INNERMOST_TEMPLATE_ARGS (CLASSTYPE_TI_ARGS (type));
 940         }
 941     }
 942   else if (processing_specialization)
 943     {
 944        /* Someday C++0x may allow for enum template specialization.  */
 945       if (cxx_dialect > cxx98 && TREE_CODE (type) == ENUMERAL_TYPE
 946           && CLASS_TYPE_P (context) && CLASSTYPE_USE_TEMPLATE (context))
 947         pedwarn (input_location, OPT_pedantic, "template specialization "
 948                  "of %qD not allowed by ISO C++", type);
 949       else
 950         {
 951           error ("explicit specialization of non-template %qT", type);
 952           return error_mark_node;
 953         }
 954     }
 955
 956   return type;
 957 }
 958
 959 /* Returns nonzero if we can optimize the retrieval of specializations
 960    for TMPL, a TEMPLATE_DECL.  In particular, for such a template, we
 961    do not use DECL_TEMPLATE_SPECIALIZATIONS at all.  */
 962
 963 static inline bool
 964 optimize_specialization_lookup_p (tree tmpl)
 965 {
 966   return (DECL_FUNCTION_TEMPLATE_P (tmpl)
 967           && DECL_CLASS_SCOPE_P (tmpl)
 968           /* DECL_CLASS_SCOPE_P holds of T::f even if T is a template
 969              parameter.  */
 970           && CLASS_TYPE_P (DECL_CONTEXT (tmpl))
 971           /* The optimized lookup depends on the fact that the
 972              template arguments for the member function template apply
 973              purely to the containing class, which is not true if the
 974              containing class is an explicit or partial
 975              specialization.  */
 976           && !CLASSTYPE_TEMPLATE_SPECIALIZATION (DECL_CONTEXT (tmpl))
 977           && !DECL_MEMBER_TEMPLATE_P (tmpl)
 978           && !DECL_CONV_FN_P (tmpl)
 979           /* It is possible to have a template that is not a member
 980              template and is not a member of a template class:
 981
 982              template <typename T>
 983              struct S { friend A::f(); };
 984
 985              Here, the friend function is a template, but the context does
 986              not have template information.  The optimized lookup relies
 987              on having ARGS be the template arguments for both the class
 988              and the function template.  */
 989           && !DECL_FRIEND_P (DECL_TEMPLATE_RESULT (tmpl)));
 990 }
 991
 992 /* Retrieve the specialization (in the sense of [temp.spec] - a
 993    specialization is either an instantiation or an explicit
 994    specialization) of TMPL for the given template ARGS.  If there is
 995    no such specialization, return NULL_TREE.  The ARGS are a vector of
 996    arguments, or a vector of vectors of arguments, in the case of
 997    templates with more than one level of parameters.
 998
 999    If TMPL is a type template and CLASS_SPECIALIZATIONS_P is true,
1000    then we search for a partial specialization matching ARGS.  This
1001    parameter is ignored if TMPL is not a class template.  */
1002
1003 static tree
1004 retrieve_specialization (tree tmpl, tree args, hashval_t hash)
1005 {
1006   if (args == error_mark_node)
1007     return NULL_TREE;
1008
1009   gcc_assert (TREE_CODE (tmpl) == TEMPLATE_DECL);
1010
1011   /* There should be as many levels of arguments as there are
1012      levels of parameters.  */
1013   gcc_assert (TMPL_ARGS_DEPTH (args)
1014               == TMPL_PARMS_DEPTH (DECL_TEMPLATE_PARMS (tmpl)));
1015
1016   if (optimize_specialization_lookup_p (tmpl))
1017     {
1018       tree class_template;
1019       tree class_specialization;
1020       VEC(tree,gc) *methods;
1021       tree fns;
1022       int idx;
1023
1024       /* The template arguments actually apply to the containing
1025          class.  Find the class specialization with those
1026          arguments.  */
1027       class_template = CLASSTYPE_TI_TEMPLATE (DECL_CONTEXT (tmpl));
1028       class_specialization
1029         = retrieve_specialization (class_template, args, 0);
1030       if (!class_specialization)
1031         return NULL_TREE;
1032       /* Now, find the appropriate entry in the CLASSTYPE_METHOD_VEC
1033          for the specialization.  */
1034       idx = class_method_index_for_fn (class_specialization, tmpl);
1035       if (idx == -1)
1036         return NULL_TREE;
1037       /* Iterate through the methods with the indicated name, looking
1038          for the one that has an instance of TMPL.  */
1039       methods = CLASSTYPE_METHOD_VEC (class_specialization);
1040       for (fns = VEC_index (tree, methods, idx); fns; fns = OVL_NEXT (fns))
1041         {
1042           tree fn = OVL_CURRENT (fns);
1043           if (DECL_TEMPLATE_INFO (fn) && DECL_TI_TEMPLATE (fn) == tmpl
1044               /* using-declarations can add base methods to the method vec,
1045                  and we don't want those here.  */
1046               && DECL_CONTEXT (fn) == class_specialization)
1047             return fn;
1048         }
1049       return NULL_TREE;
1050     }
1051   else
1052     {
1053       spec_entry *found;
1054       spec_entry elt;
1055       htab_t specializations;
1056
1057       elt.tmpl = tmpl;
1058       elt.args = args;
1059       elt.spec = NULL_TREE;
1060
1061       if (DECL_CLASS_TEMPLATE_P (tmpl))
1062         specializations = type_specializations;
1063       else
1064         specializations = decl_specializations;
1065
1066       if (hash == 0)
1067         hash = hash_specialization (&elt);
1068       found = (spec_entry *) htab_find_with_hash (specializations, &elt, hash);
1069       if (found)
1070         return found->spec;
1071     }
1072
1073   return NULL_TREE;
1074 }
1075
1076 /* Like retrieve_specialization, but for local declarations.  */
1077
1078 static tree
1079 retrieve_local_specialization (tree tmpl)
1080 {
1081   tree spec;
1082
1083   if (local_specializations == NULL)
1084     return NULL_TREE;
1085
1086   spec = (tree) htab_find_with_hash (local_specializations, tmpl,
1087                                      htab_hash_pointer (tmpl));
1088   return spec ? TREE_PURPOSE (spec) : NULL_TREE;
1089 }
1090
1091 /* Returns nonzero iff DECL is a specialization of TMPL.  */
1092
1093 int
1094 is_specialization_of (tree decl, tree tmpl)
1095 {
1096   tree t;
1097
1098   if (TREE_CODE (decl) == FUNCTION_DECL)
1099     {
1100       for (t = decl;
1101            t != NULL_TREE;
1102            t = DECL_TEMPLATE_INFO (t) ? DECL_TI_TEMPLATE (t) : NULL_TREE)
1103         if (t == tmpl)
1104           return 1;
1105     }
1106   else
1107     {
1108       gcc_assert (TREE_CODE (decl) == TYPE_DECL);
1109
1110       for (t = TREE_TYPE (decl);
1111            t != NULL_TREE;
1112            t = CLASSTYPE_USE_TEMPLATE (t)
1113              ? TREE_TYPE (CLASSTYPE_TI_TEMPLATE (t)) : NULL_TREE)
1114         if (same_type_ignoring_top_level_qualifiers_p (t, TREE_TYPE (tmpl)))
1115           return 1;
1116     }
1117
1118   return 0;
1119 }
1120
1121 /* Returns nonzero iff DECL is a specialization of friend declaration
1122    FRIEND_DECL according to [temp.friend].  */
1123
1124 bool
1125 is_specialization_of_friend (tree decl, tree friend_decl)
1126 {
1127   bool need_template = true;
1128   int template_depth;
1129
1130   gcc_assert (TREE_CODE (decl) == FUNCTION_DECL
1131               || TREE_CODE (decl) == TYPE_DECL);
1132
1133   /* For [temp.friend/6] when FRIEND_DECL is an ordinary member function
1134      of a template class, we want to check if DECL is a specialization
1135      if this.  */
1136   if (TREE_CODE (friend_decl) == FUNCTION_DECL
1137       && DECL_TEMPLATE_INFO (friend_decl)
1138       && !DECL_USE_TEMPLATE (friend_decl))
1139     {
1140       /* We want a TEMPLATE_DECL for `is_specialization_of'.  */
1141       friend_decl = DECL_TI_TEMPLATE (friend_decl);
1142       need_template = false;
1143     }
1144   else if (TREE_CODE (friend_decl) == TEMPLATE_DECL
1145            && !PRIMARY_TEMPLATE_P (friend_decl))
1146     need_template = false;
1147
1148   /* There is nothing to do if this is not a template friend.  */
1149   if (TREE_CODE (friend_decl) != TEMPLATE_DECL)
1150     return false;
1151
1152   if (is_specialization_of (decl, friend_decl))
1153     return true;
1154
1155   /* [temp.friend/6]
1156      A member of a class template may be declared to be a friend of a
1157      non-template class.  In this case, the corresponding member of
1158      every specialization of the class template is a friend of the
1159      class granting friendship.
1160
1161      For example, given a template friend declaration
1162
1163        template <class T> friend void A<T>::f();
1164
1165      the member function below is considered a friend
1166
1167        template <> struct A<int> {
1168          void f();
1169        };
1170
1171      For this type of template friend, TEMPLATE_DEPTH below will be
1172      nonzero.  To determine if DECL is a friend of FRIEND, we first
1173      check if the enclosing class is a specialization of another.  */
1174
1175   template_depth = template_class_depth (CP_DECL_CONTEXT (friend_decl));
1176   if (template_depth
1177       && DECL_CLASS_SCOPE_P (decl)
1178       && is_specialization_of (TYPE_NAME (DECL_CONTEXT (decl)),
1179                                CLASSTYPE_TI_TEMPLATE (DECL_CONTEXT (friend_decl))))
1180     {
1181       /* Next, we check the members themselves.  In order to handle
1182          a few tricky cases, such as when FRIEND_DECL's are
1183
1184            template <class T> friend void A<T>::g(T t);
1185            template <class T> template <T t> friend void A<T>::h();
1186
1187          and DECL's are
1188
1189            void A<int>::g(int);
1190            template <int> void A<int>::h();
1191
1192          we need to figure out ARGS, the template arguments from
1193          the context of DECL.  This is required for template substitution
1194          of `T' in the function parameter of `g' and template parameter
1195          of `h' in the above examples.  Here ARGS corresponds to `int'.  */
1196
1197       tree context = DECL_CONTEXT (decl);
1198       tree args = NULL_TREE;
1199       int current_depth = 0;
1200
1201       while (current_depth < template_depth)
1202         {
1203           if (CLASSTYPE_TEMPLATE_INFO (context))
1204             {
1205               if (current_depth == 0)
1206                 args = TYPE_TI_ARGS (context);
1207               else
1208                 args = add_to_template_args (TYPE_TI_ARGS (context), args);
1209               current_depth++;
1210             }
1211           context = TYPE_CONTEXT (context);
1212         }
1213
1214       if (TREE_CODE (decl) == FUNCTION_DECL)
1215         {
1216           bool is_template;
1217           tree friend_type;
1218           tree decl_type;
1219           tree friend_args_type;
1220           tree decl_args_type;
1221
1222           /* Make sure that both DECL and FRIEND_DECL are templates or
1223              non-templates.  */
1224           is_template = DECL_TEMPLATE_INFO (decl)
1225                         && PRIMARY_TEMPLATE_P (DECL_TI_TEMPLATE (decl));
1226           if (need_template ^ is_template)
1227             return false;
1228           else if (is_template)
1229             {
1230               /* If both are templates, check template parameter list.  */
1231               tree friend_parms
1232                 = tsubst_template_parms (DECL_TEMPLATE_PARMS (friend_decl),
1233                                          args, tf_none);
1234               if (!comp_template_parms
1235                      (DECL_TEMPLATE_PARMS (DECL_TI_TEMPLATE (decl)),
1236                       friend_parms))
1237                 return false;
1238
1239               decl_type = TREE_TYPE (DECL_TI_TEMPLATE (decl));
1240             }
1241           else
1242             decl_type = TREE_TYPE (decl);
1243
1244           friend_type = tsubst_function_type (TREE_TYPE (friend_decl), args,
1245                                               tf_none, NULL_TREE);
1246           if (friend_type == error_mark_node)
1247             return false;
1248
1249           /* Check if return types match.  */
1250           if (!same_type_p (TREE_TYPE (decl_type), TREE_TYPE (friend_type)))
1251             return false;
1252
1253           /* Check if function parameter types match, ignoring the
1254              `this' parameter.  */
1255           friend_args_type = TYPE_ARG_TYPES (friend_type);
1256           decl_args_type = TYPE_ARG_TYPES (decl_type);
1257           if (DECL_NONSTATIC_MEMBER_FUNCTION_P (friend_decl))
1258             friend_args_type = TREE_CHAIN (friend_args_type);
1259           if (DECL_NONSTATIC_MEMBER_FUNCTION_P (decl))
1260             decl_args_type = TREE_CHAIN (decl_args_type);
1261
1262           return compparms (decl_args_type, friend_args_type);
1263         }
1264       else
1265         {
1266           /* DECL is a TYPE_DECL */
1267           bool is_template;
1268           tree decl_type = TREE_TYPE (decl);
1269
1270           /* Make sure that both DECL and FRIEND_DECL are templates or
1271              non-templates.  */
1272           is_template
1273             = CLASSTYPE_TEMPLATE_INFO (decl_type)
1274               && PRIMARY_TEMPLATE_P (CLASSTYPE_TI_TEMPLATE (decl_type));
1275
1276           if (need_template ^ is_template)
1277             return false;
1278           else if (is_template)
1279             {
1280               tree friend_parms;
1281               /* If both are templates, check the name of the two
1282                  TEMPLATE_DECL's first because is_friend didn't.  */
1283               if (DECL_NAME (CLASSTYPE_TI_TEMPLATE (decl_type))
1284                   != DECL_NAME (friend_decl))
1285                 return false;
1286
1287               /* Now check template parameter list.  */
1288               friend_parms
1289                 = tsubst_template_parms (DECL_TEMPLATE_PARMS (friend_decl),
1290                                          args, tf_none);
1291               return comp_template_parms
1292                 (DECL_TEMPLATE_PARMS (CLASSTYPE_TI_TEMPLATE (decl_type)),
1293                  friend_parms);
1294             }
1295           else
1296             return (DECL_NAME (decl)
1297                     == DECL_NAME (friend_decl));
1298         }
1299     }
1300   return false;
1301 }
1302
1303 /* Register the specialization SPEC as a specialization of TMPL with
1304    the indicated ARGS.  IS_FRIEND indicates whether the specialization
1305    is actually just a friend declaration.  Returns SPEC, or an
1306    equivalent prior declaration, if available.  */
1307
1308 static tree
1309 register_specialization (tree spec, tree tmpl, tree args, bool is_friend,
1310                          hashval_t hash)
1311 {
1312   tree fn;
1313   void **slot = NULL;
1314   spec_entry elt;
1315
1316   gcc_assert (TREE_CODE (tmpl) == TEMPLATE_DECL && DECL_P (spec));
1317
1318   if (TREE_CODE (spec) == FUNCTION_DECL
1319       && uses_template_parms (DECL_TI_ARGS (spec)))
1320     /* This is the FUNCTION_DECL for a partial instantiation.  Don't
1321        register it; we want the corresponding TEMPLATE_DECL instead.
1322        We use `uses_template_parms (DECL_TI_ARGS (spec))' rather than
1323        the more obvious `uses_template_parms (spec)' to avoid problems
1324        with default function arguments.  In particular, given
1325        something like this:
1326
1327           template <class T> void f(T t1, T t = T())
1328
1329        the default argument expression is not substituted for in an
1330        instantiation unless and until it is actually needed.  */
1331     return spec;
1332
1333   if (optimize_specialization_lookup_p (tmpl))
1334     /* We don't put these specializations in the hash table, but we might
1335        want to give an error about a mismatch.  */
1336     fn = retrieve_specialization (tmpl, args, 0);
1337   else
1338     {
1339       elt.tmpl = tmpl;
1340       elt.args = args;
1341       elt.spec = spec;
1342
1343       if (hash == 0)
1344         hash = hash_specialization (&elt);
1345
1346       slot =
1347         htab_find_slot_with_hash (decl_specializations, &elt, hash, INSERT);
1348       if (*slot)
1349         fn = ((spec_entry *) *slot)->spec;
1350       else
1351         fn = NULL_TREE;
1352     }
1353
1354   /* We can sometimes try to re-register a specialization that we've
1355      already got.  In particular, regenerate_decl_from_template calls
1356      duplicate_decls which will update the specialization list.  But,
1357      we'll still get called again here anyhow.  It's more convenient
1358      to simply allow this than to try to prevent it.  */
1359   if (fn == spec)
1360     return spec;
1361   else if (fn && DECL_TEMPLATE_SPECIALIZATION (spec))
1362     {
1363       if (DECL_TEMPLATE_INSTANTIATION (fn))
1364         {
1365           if (DECL_ODR_USED (fn)
1366               || DECL_EXPLICIT_INSTANTIATION (fn))
1367             {
1368               error ("specialization of %qD after instantiation",
1369                      fn);
1370               return error_mark_node;
1371             }
1372           else
1373             {
1374               tree clone;
1375               /* This situation should occur only if the first
1376                  specialization is an implicit instantiation, the
1377                  second is an explicit specialization, and the
1378                  implicit instantiation has not yet been used.  That
1379                  situation can occur if we have implicitly
1380                  instantiated a member function and then specialized
1381                  it later.
1382
1383                  We can also wind up here if a friend declaration that
1384                  looked like an instantiation turns out to be a
1385                  specialization:
1386
1387                    template <class T> void foo(T);
1388                    class S { friend void foo<>(int) };
1389                    template <> void foo(int);
1390
1391                  We transform the existing DECL in place so that any
1392                  pointers to it become pointers to the updated
1393                  declaration.
1394
1395                  If there was a definition for the template, but not
1396                  for the specialization, we want this to look as if
1397                  there were no definition, and vice versa.  */
1398               DECL_INITIAL (fn) = NULL_TREE;
1399               duplicate_decls (spec, fn, is_friend);
1400               /* The call to duplicate_decls will have applied
1401                  [temp.expl.spec]:
1402
1403                    An explicit specialization of a function template
1404                    is inline only if it is explicitly declared to be,
1405                    and independently of whether its function template
1406                    is.
1407
1408                 to the primary function; now copy the inline bits to
1409                 the various clones.  */
1410               FOR_EACH_CLONE (clone, fn)
1411                 {
1412                   DECL_DECLARED_INLINE_P (clone)
1413                     = DECL_DECLARED_INLINE_P (fn);
1414                   DECL_SOURCE_LOCATION (clone)
1415                     = DECL_SOURCE_LOCATION (fn);
1416                 }
1417               check_specialization_namespace (fn);
1418
1419               return fn;
1420             }
1421         }
1422       else if (DECL_TEMPLATE_SPECIALIZATION (fn))
1423         {
1424           if (!duplicate_decls (spec, fn, is_friend) && DECL_INITIAL (spec))
1425             /* Dup decl failed, but this is a new definition. Set the
1426                line number so any errors match this new
1427                definition.  */
1428             DECL_SOURCE_LOCATION (fn) = DECL_SOURCE_LOCATION (spec);
1429
1430           return fn;
1431         }
1432     }
1433   else if (fn)
1434     return duplicate_decls (spec, fn, is_friend);
1435
1436   /* A specialization must be declared in the same namespace as the
1437      template it is specializing.  */
1438   if (DECL_TEMPLATE_SPECIALIZATION (spec)
1439       && !check_specialization_namespace (tmpl))
1440     DECL_CONTEXT (spec) = DECL_CONTEXT (tmpl);
1441
1442   if (slot != NULL /* !optimize_specialization_lookup_p (tmpl) */)
1443     {
1444       spec_entry *entry = ggc_alloc_spec_entry ();
1445       gcc_assert (tmpl && args && spec);
1446       *entry = elt;
1447       *slot = entry;
1448       if (TREE_CODE (spec) == FUNCTION_DECL && DECL_NAMESPACE_SCOPE_P (spec)
1449           && PRIMARY_TEMPLATE_P (tmpl)
1450           && DECL_SAVED_TREE (DECL_TEMPLATE_RESULT (tmpl)) == NULL_TREE)
1451         /* TMPL is a forward declaration of a template function; keep a list
1452            of all specializations in case we need to reassign them to a friend
1453            template later in tsubst_friend_function.  */
1454         DECL_TEMPLATE_INSTANTIATIONS (tmpl)
1455           = tree_cons (args, spec, DECL_TEMPLATE_INSTANTIATIONS (tmpl));
1456     }
1457
1458   return spec;
1459 }
1460
1461 /* Returns true iff two spec_entry nodes are equivalent.  Only compares the
1462    TMPL and ARGS members, ignores SPEC.  */
1463
1464 static int
1465 eq_specializations (const void *p1, const void *p2)
1466 {
1467   const spec_entry *e1 = (const spec_entry *)p1;
1468   const spec_entry *e2 = (const spec_entry *)p2;
1469
1470   return (e1->tmpl == e2->tmpl
1471           && comp_template_args (e1->args, e2->args));
1472 }
1473
1474 /* Returns a hash for a template TMPL and template arguments ARGS.  */
1475
1476 static hashval_t
1477 hash_tmpl_and_args (tree tmpl, tree args)
1478 {
1479   hashval_t val = DECL_UID (tmpl);
1480   return iterative_hash_template_arg (args, val);
1481 }
1482
1483 /* Returns a hash for a spec_entry node based on the TMPL and ARGS members,
1484    ignoring SPEC.  */
1485
1486 static hashval_t
1487 hash_specialization (const void *p)
1488 {
1489   const spec_entry *e = (const spec_entry *)p;
1490   return hash_tmpl_and_args (e->tmpl, e->args);
1491 }
1492
1493 /* Recursively calculate a hash value for a template argument ARG, for use
1494    in the hash tables of template specializations.  */
1495
1496 hashval_t
1497 iterative_hash_template_arg (tree arg, hashval_t val)
1498 {
1499   unsigned HOST_WIDE_INT i;
1500   enum tree_code code;
1501   char tclass;
1502
1503   if (arg == NULL_TREE)
1504     return iterative_hash_object (arg, val);
1505
1506   if (!TYPE_P (arg))
1507     STRIP_NOPS (arg);
1508
1509   if (TREE_CODE (arg) == ARGUMENT_PACK_SELECT)
1510     /* We can get one of these when re-hashing a previous entry in the middle
1511        of substituting into a pack expansion.  Just look through it.  */
1512     arg = ARGUMENT_PACK_SELECT_FROM_PACK (arg);
1513
1514   code = TREE_CODE (arg);
1515   tclass = TREE_CODE_CLASS (code);
1516
1517   val = iterative_hash_object (code, val);
1518
1519   switch (code)
1520     {
1521     case ERROR_MARK:
1522       return val;
1523
1524     case IDENTIFIER_NODE:
1525       return iterative_hash_object (IDENTIFIER_HASH_VALUE (arg), val);
1526
1527     case TREE_VEC:
1528       {
1529         int i, len = TREE_VEC_LENGTH (arg);
1530         for (i = 0; i < len; ++i)
1531           val = iterative_hash_template_arg (TREE_VEC_ELT (arg, i), val);
1532         return val;
1533       }
1534
1535     case TYPE_PACK_EXPANSION:
1536     case EXPR_PACK_EXPANSION:
1537       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
1864           /* In case of explicit specialization, we need to check if
1865              the number of template headers appearing in the specialization
1866              is correct. This is usually done in check_explicit_specialization,
1867              but the check done there cannot be exhaustive when specializing
1868              member functions. Consider the following code:
1869
1870              template <> void A<int>::f(int);
1871              template <> template <> void A<int>::f(int);
1872
1873              Assuming that A<int> is not itself an explicit specialization
1874              already, the first line specializes "f" which is a non-template
1875              member function, whilst the second line specializes "f" which
1876              is a template member function. So both lines are syntactically
1877              correct, and check_explicit_specialization does not reject
1878              them.
1879
1880              Here, we can do better, as we are matching the specialization
1881              against the declarations. We count the number of template
1882              headers, and we check if they match TEMPLATE_COUNT + 1
1883              (TEMPLATE_COUNT is the number of qualifying template classes,
1884              plus there must be another header for the member template
1885              itself).
1886
1887              Notice that if header_count is zero, this is not a
1888              specialization but rather a template instantiation, so there
1889              is no check we can perform here.  */
1890           if (header_count && header_count != template_count + 1)
1891             continue;
1892
1893           /* Check that the number of template arguments at the
1894              innermost level for DECL is the same as for FN.  */
1895           if (current_binding_level->kind == sk_template_parms
1896               && !current_binding_level->explicit_spec_p
1897               && (TREE_VEC_LENGTH (DECL_INNERMOST_TEMPLATE_PARMS (fn))
1898                   != TREE_VEC_LENGTH (INNERMOST_TEMPLATE_PARMS
1899                                       (current_template_parms))))
1900             continue;
1901
1902           /* DECL might be a specialization of FN.  */
1903           decl_arg_types = TYPE_ARG_TYPES (TREE_TYPE (decl));
1904           fn_arg_types = TYPE_ARG_TYPES (TREE_TYPE (fn));
1905
1906           /* For a non-static member function, we need to make sure
1907              that the const qualification is the same.  Since
1908              get_bindings does not try to merge the "this" parameter,
1909              we must do the comparison explicitly.  */
1910           if (DECL_NONSTATIC_MEMBER_FUNCTION_P (fn)
1911               && !same_type_p (TREE_VALUE (fn_arg_types),
1912                                TREE_VALUE (decl_arg_types)))
1913             continue;
1914
1915           /* Skip the "this" parameter and, for constructors of
1916              classes with virtual bases, the VTT parameter.  A
1917              full specialization of a constructor will have a VTT
1918              parameter, but a template never will.  */
1919           decl_arg_types
1920             = skip_artificial_parms_for (decl, decl_arg_types);
1921           fn_arg_types
1922             = skip_artificial_parms_for (fn, fn_arg_types);
1923
1924           /* Check that the number of function parameters matches.
1925              For example,
1926                template <class T> void f(int i = 0);
1927                template <> void f<int>();
1928              The specialization f<int> is invalid but is not caught
1929              by get_bindings below.  */
1930           if (list_length (fn_arg_types) != list_length (decl_arg_types))
1931             continue;
1932
1933           /* Function templates cannot be specializations; there are
1934              no partial specializations of functions.  Therefore, if
1935              the type of DECL does not match FN, there is no
1936              match.  */
1937           if (tsk == tsk_template)
1938             {
1939               if (compparms (fn_arg_types, decl_arg_types))
1940                 candidates = tree_cons (NULL_TREE, fn, candidates);
1941               continue;
1942             }
1943
1944           /* See whether this function might be a specialization of this
1945              template.  */
1946           targs = get_bindings (fn, decl, explicit_targs, /*check_ret=*/true);
1947
1948           if (!targs)
1949             /* We cannot deduce template arguments that when used to
1950                specialize TMPL will produce DECL.  */
1951             continue;
1952
1953           /* Save this template, and the arguments deduced.  */
1954           templates = tree_cons (targs, fn, templates);
1955         }
1956       else if (need_member_template)
1957         /* FN is an ordinary member function, and we need a
1958            specialization of a member template.  */
1959         ;
1960       else if (TREE_CODE (fn) != FUNCTION_DECL)
1961         /* We can get IDENTIFIER_NODEs here in certain erroneous
1962            cases.  */
1963         ;
1964       else if (!DECL_FUNCTION_MEMBER_P (fn))
1965         /* This is just an ordinary non-member function.  Nothing can
1966            be a specialization of that.  */
1967         ;
1968       else if (DECL_ARTIFICIAL (fn))
1969         /* Cannot specialize functions that are created implicitly.  */
1970         ;
1971       else
1972         {
1973           tree decl_arg_types;
1974
1975           /* This is an ordinary member function.  However, since
1976              we're here, we can assume it's enclosing class is a
1977              template class.  For example,
1978
1979                template <typename T> struct S { void f(); };
1980                template <> void S<int>::f() {}
1981
1982              Here, S<int>::f is a non-template, but S<int> is a
1983              template class.  If FN has the same type as DECL, we
1984              might be in business.  */
1985
1986           if (!DECL_TEMPLATE_INFO (fn))
1987             /* Its enclosing class is an explicit specialization
1988                of a template class.  This is not a candidate.  */
1989             continue;
1990
1991           if (!same_type_p (TREE_TYPE (TREE_TYPE (decl)),
1992                             TREE_TYPE (TREE_TYPE (fn))))
1993             /* The return types differ.  */
1994             continue;
1995
1996           /* Adjust the type of DECL in case FN is a static member.  */
1997           decl_arg_types = TYPE_ARG_TYPES (TREE_TYPE (decl));
1998           if (DECL_STATIC_FUNCTION_P (fn)
1999               && DECL_NONSTATIC_MEMBER_FUNCTION_P (decl))
2000             decl_arg_types = TREE_CHAIN (decl_arg_types);
2001
2002           if (compparms (TYPE_ARG_TYPES (TREE_TYPE (fn)),
2003                          decl_arg_types))
2004             /* They match!  */
2005             candidates = tree_cons (NULL_TREE, fn, candidates);
2006         }
2007     }
2008
2009   if (templates && TREE_CHAIN (templates))
2010     {
2011       /* We have:
2012
2013            [temp.expl.spec]
2014
2015            It is possible for a specialization with a given function
2016            signature to be instantiated from more than one function
2017            template.  In such cases, explicit specification of the
2018            template arguments must be used to uniquely identify the
2019            function template specialization being specialized.
2020
2021          Note that here, there's no suggestion that we're supposed to
2022          determine which of the candidate templates is most
2023          specialized.  However, we, also have:
2024
2025            [temp.func.order]
2026
2027            Partial ordering of overloaded function template
2028            declarations is used in the following contexts to select
2029            the function template to which a function template
2030            specialization refers:
2031
2032            -- when an explicit specialization refers to a function
2033               template.
2034
2035          So, we do use the partial ordering rules, at least for now.
2036          This extension can only serve to make invalid programs valid,
2037          so it's safe.  And, there is strong anecdotal evidence that
2038          the committee intended the partial ordering rules to apply;
2039          the EDG front end has that behavior, and John Spicer claims
2040          that the committee simply forgot to delete the wording in
2041          [temp.expl.spec].  */
2042       tree tmpl = most_specialized_instantiation (templates);
2043       if (tmpl != error_mark_node)
2044         {
2045           templates = tmpl;
2046           TREE_CHAIN (templates) = NULL_TREE;
2047         }
2048     }
2049
2050   if (templates == NULL_TREE && candidates == NULL_TREE)
2051     {
2052       error ("template-id %qD for %q+D does not match any template "
2053              "declaration", template_id, decl);
2054       if (header_count && header_count != template_count + 1)
2055         inform (input_location, "saw %d %<template<>%>, need %d for "
2056                 "specializing a member function template",
2057                 header_count, template_count + 1);
2058       return error_mark_node;
2059     }
2060   else if ((templates && TREE_CHAIN (templates))
2061            || (candidates && TREE_CHAIN (candidates))
2062            || (templates && candidates))
2063     {
2064       error ("ambiguous template specialization %qD for %q+D",
2065              template_id, decl);
2066       candidates = chainon (candidates, templates);
2067       print_candidates (candidates);
2068       return error_mark_node;
2069     }
2070
2071   /* We have one, and exactly one, match.  */
2072   if (candidates)
2073     {
2074       tree fn = TREE_VALUE (candidates);
2075       *targs_out = copy_node (DECL_TI_ARGS (fn));
2076       /* DECL is a re-declaration or partial instantiation of a template
2077          function.  */
2078       if (TREE_CODE (fn) == TEMPLATE_DECL)
2079         return fn;
2080       /* It was a specialization of an ordinary member function in a
2081          template class.  */
2082       return DECL_TI_TEMPLATE (fn);
2083     }
2084
2085   /* It was a specialization of a template.  */
2086   targs = DECL_TI_ARGS (DECL_TEMPLATE_RESULT (TREE_VALUE (templates)));
2087   if (TMPL_ARGS_HAVE_MULTIPLE_LEVELS (targs))
2088     {
2089       *targs_out = copy_node (targs);
2090       SET_TMPL_ARGS_LEVEL (*targs_out,
2091                            TMPL_ARGS_DEPTH (*targs_out),
2092                            TREE_PURPOSE (templates));
2093     }
2094   else
2095     *targs_out = TREE_PURPOSE (templates);
2096   return TREE_VALUE (templates);
2097 }
2098
2099 /* Returns a chain of parameter types, exactly like the SPEC_TYPES,
2100    but with the default argument values filled in from those in the
2101    TMPL_TYPES.  */
2102
2103 static tree
2104 copy_default_args_to_explicit_spec_1 (tree spec_types,
2105                                       tree tmpl_types)
2106 {
2107   tree new_spec_types;
2108
2109   if (!spec_types)
2110     return NULL_TREE;
2111
2112   if (spec_types == void_list_node)
2113     return void_list_node;
2114
2115   /* Substitute into the rest of the list.  */
2116   new_spec_types =
2117     copy_default_args_to_explicit_spec_1 (TREE_CHAIN (spec_types),
2118                                           TREE_CHAIN (tmpl_types));
2119
2120   /* Add the default argument for this parameter.  */
2121   return hash_tree_cons (TREE_PURPOSE (tmpl_types),
2122                          TREE_VALUE (spec_types),
2123                          new_spec_types);
2124 }
2125
2126 /* DECL is an explicit specialization.  Replicate default arguments
2127    from the template it specializes.  (That way, code like:
2128
2129      template <class T> void f(T = 3);
2130      template <> void f(double);
2131      void g () { f (); }
2132
2133    works, as required.)  An alternative approach would be to look up
2134    the correct default arguments at the call-site, but this approach
2135    is consistent with how implicit instantiations are handled.  */
2136
2137 static void
2138 copy_default_args_to_explicit_spec (tree decl)
2139 {
2140   tree tmpl;
2141   tree spec_types;
2142   tree tmpl_types;
2143   tree new_spec_types;
2144   tree old_type;
2145   tree new_type;
2146   tree t;
2147   tree object_type = NULL_TREE;
2148   tree in_charge = NULL_TREE;
2149   tree vtt = NULL_TREE;
2150
2151   /* See if there's anything we need to do.  */
2152   tmpl = DECL_TI_TEMPLATE (decl);
2153   tmpl_types = TYPE_ARG_TYPES (TREE_TYPE (DECL_TEMPLATE_RESULT (tmpl)));
2154   for (t = tmpl_types; t; t = TREE_CHAIN (t))
2155     if (TREE_PURPOSE (t))
2156       break;
2157   if (!t)
2158     return;
2159
2160   old_type = TREE_TYPE (decl);
2161   spec_types = TYPE_ARG_TYPES (old_type);
2162
2163   if (DECL_NONSTATIC_MEMBER_FUNCTION_P (decl))
2164     {
2165       /* Remove the this pointer, but remember the object's type for
2166          CV quals.  */
2167       object_type = TREE_TYPE (TREE_VALUE (spec_types));
2168       spec_types = TREE_CHAIN (spec_types);
2169       tmpl_types = TREE_CHAIN (tmpl_types);
2170
2171       if (DECL_HAS_IN_CHARGE_PARM_P (decl))
2172         {
2173           /* DECL may contain more parameters than TMPL due to the extra
2174              in-charge parameter in constructors and destructors.  */
2175           in_charge = spec_types;
2176           spec_types = TREE_CHAIN (spec_types);
2177         }
2178       if (DECL_HAS_VTT_PARM_P (decl))
2179         {
2180           vtt = spec_types;
2181           spec_types = TREE_CHAIN (spec_types);
2182         }
2183     }
2184
2185   /* Compute the merged default arguments.  */
2186   new_spec_types =
2187     copy_default_args_to_explicit_spec_1 (spec_types, tmpl_types);
2188
2189   /* Compute the new FUNCTION_TYPE.  */
2190   if (object_type)
2191     {
2192       if (vtt)
2193         new_spec_types = hash_tree_cons (TREE_PURPOSE (vtt),
2194                                          TREE_VALUE (vtt),
2195                                          new_spec_types);
2196
2197       if (in_charge)
2198         /* Put the in-charge parameter back.  */
2199         new_spec_types = hash_tree_cons (TREE_PURPOSE (in_charge),
2200                                          TREE_VALUE (in_charge),
2201                                          new_spec_types);
2202
2203       new_type = build_method_type_directly (object_type,
2204                                              TREE_TYPE (old_type),
2205                                              new_spec_types);
2206     }
2207   else
2208     new_type = build_function_type (TREE_TYPE (old_type),
2209                                     new_spec_types);
2210   new_type = cp_build_type_attribute_variant (new_type,
2211                                               TYPE_ATTRIBUTES (old_type));
2212   new_type = build_exception_variant (new_type,
2213                                       TYPE_RAISES_EXCEPTIONS (old_type));
2214   TREE_TYPE (decl) = new_type;
2215 }
2216
2217 /* Check to see if the function just declared, as indicated in
2218    DECLARATOR, and in DECL, is a specialization of a function
2219    template.  We may also discover that the declaration is an explicit
2220    instantiation at this point.
2221
2222    Returns DECL, or an equivalent declaration that should be used
2223    instead if all goes well.  Issues an error message if something is
2224    amiss.  Returns error_mark_node if the error is not easily
2225    recoverable.
2226
2227    FLAGS is a bitmask consisting of the following flags:
2228
2229    2: The function has a definition.
2230    4: The function is a friend.
2231
2232    The TEMPLATE_COUNT is the number of references to qualifying
2233    template classes that appeared in the name of the function.  For
2234    example, in
2235
2236      template <class T> struct S { void f(); };
2237      void S<int>::f();
2238
2239    the TEMPLATE_COUNT would be 1.  However, explicitly specialized
2240    classes are not counted in the TEMPLATE_COUNT, so that in
2241
2242      template <class T> struct S {};
2243      template <> struct S<int> { void f(); }
2244      template <> void S<int>::f();
2245
2246    the TEMPLATE_COUNT would be 0.  (Note that this declaration is
2247    invalid; there should be no template <>.)
2248
2249    If the function is a specialization, it is marked as such via
2250    DECL_TEMPLATE_SPECIALIZATION.  Furthermore, its DECL_TEMPLATE_INFO
2251    is set up correctly, and it is added to the list of specializations
2252    for that template.  */
2253
2254 tree
2255 check_explicit_specialization (tree declarator,
2256                                tree decl,
2257                                int template_count,
2258                                int flags)
2259 {
2260   int have_def = flags & 2;
2261   int is_friend = flags & 4;
2262   int specialization = 0;
2263   int explicit_instantiation = 0;
2264   int member_specialization = 0;
2265   tree ctype = DECL_CLASS_CONTEXT (decl);
2266   tree dname = DECL_NAME (decl);
2267   tmpl_spec_kind tsk;
2268
2269   if (is_friend)
2270     {
2271       if (!processing_specialization)
2272         tsk = tsk_none;
2273       else
2274         tsk = tsk_excessive_parms;
2275     }
2276   else
2277     tsk = current_tmpl_spec_kind (template_count);
2278
2279   switch (tsk)
2280     {
2281     case tsk_none:
2282       if (processing_specialization)
2283         {
2284           specialization = 1;
2285           SET_DECL_TEMPLATE_SPECIALIZATION (decl);
2286         }
2287       else if (TREE_CODE (declarator) == TEMPLATE_ID_EXPR)
2288         {
2289           if (is_friend)
2290             /* This could be something like:
2291
2292                template <class T> void f(T);
2293                class S { friend void f<>(int); }  */
2294             specialization = 1;
2295           else
2296             {
2297               /* This case handles bogus declarations like template <>
2298                  template <class T> void f<int>(); */
2299
2300               error ("template-id %qD in declaration of primary template",
2301                      declarator);
2302               return decl;
2303             }
2304         }
2305       break;
2306
2307     case tsk_invalid_member_spec:
2308       /* The error has already been reported in
2309          check_specialization_scope.  */
2310       return error_mark_node;
2311
2312     case tsk_invalid_expl_inst:
2313       error ("template parameter list used in explicit instantiation");
2314
2315       /* Fall through.  */
2316
2317     case tsk_expl_inst:
2318       if (have_def)
2319         error ("definition provided for explicit instantiation");
2320
2321       explicit_instantiation = 1;
2322       break;
2323
2324     case tsk_excessive_parms:
2325     case tsk_insufficient_parms:
2326       if (tsk == tsk_excessive_parms)
2327         error ("too many template parameter lists in declaration of %qD",
2328                decl);
2329       else if (template_header_count)
2330         error("too few template parameter lists in declaration of %qD", decl);
2331       else
2332         error("explicit specialization of %qD must be introduced by "
2333               "%<template <>%>", decl);
2334
2335       /* Fall through.  */
2336     case tsk_expl_spec:
2337       SET_DECL_TEMPLATE_SPECIALIZATION (decl);
2338       if (ctype)
2339         member_specialization = 1;
2340       else
2341         specialization = 1;
2342       break;
2343
2344     case tsk_template:
2345       if (TREE_CODE (declarator) == TEMPLATE_ID_EXPR)
2346         {
2347           /* This case handles bogus declarations like template <>
2348              template <class T> void f<int>(); */
2349
2350           if (uses_template_parms (declarator))
2351             error ("function template partial specialization %qD "
2352                    "is not allowed", declarator);
2353           else
2354             error ("template-id %qD in declaration of primary template",
2355                    declarator);
2356           return decl;
2357         }
2358
2359       if (ctype && CLASSTYPE_TEMPLATE_INSTANTIATION (ctype))
2360         /* This is a specialization of a member template, without
2361            specialization the containing class.  Something like:
2362
2363              template <class T> struct S {
2364                template <class U> void f (U);
2365              };
2366              template <> template <class U> void S<int>::f(U) {}
2367
2368            That's a specialization -- but of the entire template.  */
2369         specialization = 1;
2370       break;
2371
2372     default:
2373       gcc_unreachable ();
2374     }
2375
2376   if (specialization || member_specialization)
2377     {
2378       tree t = TYPE_ARG_TYPES (TREE_TYPE (decl));
2379       for (; t; t = TREE_CHAIN (t))
2380         if (TREE_PURPOSE (t))
2381           {
2382             permerror (input_location,
2383                        "default argument specified in explicit specialization");
2384             break;
2385           }
2386     }
2387
2388   if (specialization || member_specialization || explicit_instantiation)
2389     {
2390       tree tmpl = NULL_TREE;
2391       tree targs = NULL_TREE;
2392
2393       /* Make sure that the declarator is a TEMPLATE_ID_EXPR.  */
2394       if (TREE_CODE (declarator) != TEMPLATE_ID_EXPR)
2395         {
2396           tree fns;
2397
2398           gcc_assert (TREE_CODE (declarator) == IDENTIFIER_NODE);
2399           if (ctype)
2400             fns = dname;
2401           else
2402             {
2403               /* If there is no class context, the explicit instantiation
2404                  must be at namespace scope.  */
2405               gcc_assert (DECL_NAMESPACE_SCOPE_P (decl));
2406
2407               /* Find the namespace binding, using the declaration
2408                  context.  */
2409               fns = lookup_qualified_name (CP_DECL_CONTEXT (decl), dname,
2410                                            false, true);
2411               if (fns == error_mark_node || !is_overloaded_fn (fns))
2412                 {
2413                   error ("%qD is not a template function", dname);
2414                   fns = error_mark_node;
2415                 }
2416               else
2417                 {
2418                   tree fn = OVL_CURRENT (fns);
2419                   if (!is_associated_namespace (CP_DECL_CONTEXT (decl),
2420                                                 CP_DECL_CONTEXT (fn)))
2421                     error ("%qD is not declared in %qD",
2422                            decl, current_namespace);
2423                 }
2424             }
2425
2426           declarator = lookup_template_function (fns, NULL_TREE);
2427         }
2428
2429       if (declarator == error_mark_node)
2430         return error_mark_node;
2431
2432       if (ctype != NULL_TREE && TYPE_BEING_DEFINED (ctype))
2433         {
2434           if (!explicit_instantiation)
2435             /* A specialization in class scope.  This is invalid,
2436                but the error will already have been flagged by
2437                check_specialization_scope.  */
2438             return error_mark_node;
2439           else
2440             {
2441               /* It's not valid to write an explicit instantiation in
2442                  class scope, e.g.:
2443
2444                    class C { template void f(); }
2445
2446                    This case is caught by the parser.  However, on
2447                    something like:
2448
2449                    template class C { void f(); };
2450
2451                    (which is invalid) we can get here.  The error will be
2452                    issued later.  */
2453               ;
2454             }
2455
2456           return decl;
2457         }
2458       else if (ctype != NULL_TREE
2459                && (TREE_CODE (TREE_OPERAND (declarator, 0)) ==
2460                    IDENTIFIER_NODE))
2461         {
2462           /* Find the list of functions in ctype that have the same
2463              name as the declared function.  */
2464           tree name = TREE_OPERAND (declarator, 0);
2465           tree fns = NULL_TREE;
2466           int idx;
2467
2468           if (constructor_name_p (name, ctype))
2469             {
2470               int is_constructor = DECL_CONSTRUCTOR_P (decl);
2471
2472               if (is_constructor ? !TYPE_HAS_USER_CONSTRUCTOR (ctype)
2473                   : !CLASSTYPE_DESTRUCTORS (ctype))
2474                 {
2475                   /* From [temp.expl.spec]:
2476
2477                      If such an explicit specialization for the member
2478                      of a class template names an implicitly-declared
2479                      special member function (clause _special_), the
2480                      program is ill-formed.
2481
2482                      Similar language is found in [temp.explicit].  */
2483                   error ("specialization of implicitly-declared special member function");
2484                   return error_mark_node;
2485                 }
2486
2487               name = is_constructor ? ctor_identifier : dtor_identifier;
2488             }
2489
2490           if (!DECL_CONV_FN_P (decl))
2491             {
2492               idx = lookup_fnfields_1 (ctype, name);
2493               if (idx >= 0)
2494                 fns = VEC_index (tree, CLASSTYPE_METHOD_VEC (ctype), idx);
2495             }
2496           else
2497             {
2498               VEC(tree,gc) *methods;
2499               tree ovl;
2500
2501               /* For a type-conversion operator, we cannot do a
2502                  name-based lookup.  We might be looking for `operator
2503                  int' which will be a specialization of `operator T'.
2504                  So, we find *all* the conversion operators, and then
2505                  select from them.  */
2506               fns = NULL_TREE;
2507
2508               methods = CLASSTYPE_METHOD_VEC (ctype);
2509               if (methods)
2510                 for (idx = CLASSTYPE_FIRST_CONVERSION_SLOT;
2511                      VEC_iterate (tree, methods, idx, ovl);
2512                      ++idx)
2513                   {
2514                     if (!DECL_CONV_FN_P (OVL_CURRENT (ovl)))
2515                       /* There are no more conversion functions.  */
2516                       break;
2517
2518                     /* Glue all these conversion functions together
2519                        with those we already have.  */
2520                     for (; ovl; ovl = OVL_NEXT (ovl))
2521                       fns = ovl_cons (OVL_CURRENT (ovl), fns);
2522                   }
2523             }
2524
2525           if (fns == NULL_TREE)
2526             {
2527               error ("no member function %qD declared in %qT", name, ctype);
2528               return error_mark_node;
2529             }
2530           else
2531             TREE_OPERAND (declarator, 0) = fns;
2532         }
2533
2534       /* Figure out what exactly is being specialized at this point.
2535          Note that for an explicit instantiation, even one for a
2536          member function, we cannot tell apriori whether the
2537          instantiation is for a member template, or just a member
2538          function of a template class.  Even if a member template is
2539          being instantiated, the member template arguments may be
2540          elided if they can be deduced from the rest of the
2541          declaration.  */
2542       tmpl = determine_specialization (declarator, decl,
2543                                        &targs,
2544                                        member_specialization,
2545                                        template_count,
2546                                        tsk);
2547
2548       if (!tmpl || tmpl == error_mark_node)
2549         /* We couldn't figure out what this declaration was
2550            specializing.  */
2551         return error_mark_node;
2552       else
2553         {
2554           tree gen_tmpl = most_general_template (tmpl);
2555
2556           if (explicit_instantiation)
2557             {
2558               /* We don't set DECL_EXPLICIT_INSTANTIATION here; that
2559                  is done by do_decl_instantiation later.  */
2560
2561               int arg_depth = TMPL_ARGS_DEPTH (targs);
2562               int parm_depth = TMPL_PARMS_DEPTH (DECL_TEMPLATE_PARMS (tmpl));
2563
2564               if (arg_depth > parm_depth)
2565                 {
2566                   /* If TMPL is not the most general template (for
2567                      example, if TMPL is a friend template that is
2568                      injected into namespace scope), then there will
2569                      be too many levels of TARGS.  Remove some of them
2570                      here.  */
2571                   int i;
2572                   tree new_targs;
2573
2574                   new_targs = make_tree_vec (parm_depth);
2575                   for (i = arg_depth - parm_depth; i < arg_depth; ++i)
2576                     TREE_VEC_ELT (new_targs, i - (arg_depth - parm_depth))
2577                       = TREE_VEC_ELT (targs, i);
2578                   targs = new_targs;
2579                 }
2580
2581               return instantiate_template (tmpl, targs, tf_error);
2582             }
2583
2584           /* If we thought that the DECL was a member function, but it
2585              turns out to be specializing a static member function,
2586              make DECL a static member function as well.  */
2587           if (DECL_STATIC_FUNCTION_P (tmpl)
2588               && DECL_NONSTATIC_MEMBER_FUNCTION_P (decl))
2589             revert_static_member_fn (decl);
2590
2591           /* If this is a specialization of a member template of a
2592              template class, we want to return the TEMPLATE_DECL, not
2593              the specialization of it.  */
2594           if (tsk == tsk_template)
2595             {
2596               tree result = DECL_TEMPLATE_RESULT (tmpl);
2597               SET_DECL_TEMPLATE_SPECIALIZATION (tmpl);
2598               DECL_INITIAL (result) = NULL_TREE;
2599               if (have_def)
2600                 {
2601                   tree parm;
2602                   DECL_SOURCE_LOCATION (tmpl) = DECL_SOURCE_LOCATION (decl);
2603                   DECL_SOURCE_LOCATION (result)
2604                     = DECL_SOURCE_LOCATION (decl);
2605                   /* We want to use the argument list specified in the
2606                      definition, not in the original declaration.  */
2607                   DECL_ARGUMENTS (result) = DECL_ARGUMENTS (decl);
2608                   for (parm = DECL_ARGUMENTS (result); parm;
2609                        parm = DECL_CHAIN (parm))
2610                     DECL_CONTEXT (parm) = result;
2611                 }
2612               return register_specialization (tmpl, gen_tmpl, targs,
2613                                               is_friend, 0);
2614             }
2615
2616           /* Set up the DECL_TEMPLATE_INFO for DECL.  */
2617           DECL_TEMPLATE_INFO (decl) = build_template_info (tmpl, targs);
2618
2619           /* Inherit default function arguments from the template
2620              DECL is specializing.  */
2621           copy_default_args_to_explicit_spec (decl);
2622
2623           /* This specialization has the same protection as the
2624              template it specializes.  */
2625           TREE_PRIVATE (decl) = TREE_PRIVATE (gen_tmpl);
2626           TREE_PROTECTED (decl) = TREE_PROTECTED (gen_tmpl);
2627
2628           /* 7.1.1-1 [dcl.stc]
2629
2630              A storage-class-specifier shall not be specified in an
2631              explicit specialization...
2632
2633              The parser rejects these, so unless action is taken here,
2634              explicit function specializations will always appear with
2635              global linkage.
2636
2637              The action recommended by the C++ CWG in response to C++
2638              defect report 605 is to make the storage class and linkage
2639              of the explicit specialization match the templated function:
2640
2641              http://www.open-std.org/jtc1/sc22/wg21/docs/cwg_active.html#605
2642            */
2643           if (tsk == tsk_expl_spec && DECL_FUNCTION_TEMPLATE_P (gen_tmpl))
2644             {
2645               tree tmpl_func = DECL_TEMPLATE_RESULT (gen_tmpl);
2646               gcc_assert (TREE_CODE (tmpl_func) == FUNCTION_DECL);
2647
2648               /* This specialization has the same linkage and visibility as
2649                  the function template it specializes.  */
2650               TREE_PUBLIC (decl) = TREE_PUBLIC (tmpl_func);
2651               if (! TREE_PUBLIC (decl))
2652                 {
2653                   DECL_INTERFACE_KNOWN (decl) = 1;
2654                   DECL_NOT_REALLY_EXTERN (decl) = 1;
2655                 }
2656               DECL_THIS_STATIC (decl) = DECL_THIS_STATIC (tmpl_func);
2657               if (DECL_VISIBILITY_SPECIFIED (tmpl_func))
2658                 {
2659                   DECL_VISIBILITY_SPECIFIED (decl) = 1;
2660                   DECL_VISIBILITY (decl) = DECL_VISIBILITY (tmpl_func);
2661                 }
2662             }
2663
2664           /* If DECL is a friend declaration, declared using an
2665              unqualified name, the namespace associated with DECL may
2666              have been set incorrectly.  For example, in:
2667
2668                template <typename T> void f(T);
2669                namespace N {
2670                  struct S { friend void f<int>(int); }
2671                }
2672
2673              we will have set the DECL_CONTEXT for the friend
2674              declaration to N, rather than to the global namespace.  */
2675           if (DECL_NAMESPACE_SCOPE_P (decl))
2676             DECL_CONTEXT (decl) = DECL_CONTEXT (tmpl);
2677
2678           if (is_friend && !have_def)
2679             /* This is not really a declaration of a specialization.
2680                It's just the name of an instantiation.  But, it's not
2681                a request for an instantiation, either.  */
2682             SET_DECL_IMPLICIT_INSTANTIATION (decl);
2683           else if (DECL_CONSTRUCTOR_P (decl) || DECL_DESTRUCTOR_P (decl))
2684             /* This is indeed a specialization.  In case of constructors
2685                and destructors, we need in-charge and not-in-charge
2686                versions in V3 ABI.  */
2687             clone_function_decl (decl, /*update_method_vec_p=*/0);
2688
2689           /* Register this specialization so that we can find it
2690              again.  */
2691           decl = register_specialization (decl, gen_tmpl, targs, is_friend, 0);
2692         }
2693     }
2694
2695   return decl;
2696 }
2697
2698 /* Returns 1 iff PARMS1 and PARMS2 are identical sets of template
2699    parameters.  These are represented in the same format used for
2700    DECL_TEMPLATE_PARMS.  */
2701
2702 int
2703 comp_template_parms (const_tree parms1, const_tree parms2)
2704 {
2705   const_tree p1;
2706   const_tree p2;
2707
2708   if (parms1 == parms2)
2709     return 1;
2710
2711   for (p1 = parms1, p2 = parms2;
2712        p1 != NULL_TREE && p2 != NULL_TREE;
2713        p1 = TREE_CHAIN (p1), p2 = TREE_CHAIN (p2))
2714     {
2715       tree t1 = TREE_VALUE (p1);
2716       tree t2 = TREE_VALUE (p2);
2717       int i;
2718
2719       gcc_assert (TREE_CODE (t1) == TREE_VEC);
2720       gcc_assert (TREE_CODE (t2) == TREE_VEC);
2721
2722       if (TREE_VEC_LENGTH (t1) != TREE_VEC_LENGTH (t2))
2723         return 0;
2724
2725       for (i = 0; i < TREE_VEC_LENGTH (t2); ++i)
2726         {
2727           tree parm1 = TREE_VALUE (TREE_VEC_ELT (t1, i));
2728           tree parm2 = TREE_VALUE (TREE_VEC_ELT (t2, i));
2729
2730           /* If either of the template parameters are invalid, assume
2731              they match for the sake of error recovery. */
2732           if (parm1 == error_mark_node || parm2 == error_mark_node)
2733             return 1;
2734
2735           if (TREE_CODE (parm1) != TREE_CODE (parm2))
2736             return 0;
2737
2738           if (TREE_CODE (parm1) == TEMPLATE_TYPE_PARM
2739               && (TEMPLATE_TYPE_PARAMETER_PACK (parm1)
2740                   == TEMPLATE_TYPE_PARAMETER_PACK (parm2)))
2741             continue;
2742           else if (!same_type_p (TREE_TYPE (parm1), TREE_TYPE (parm2)))
2743             return 0;
2744         }
2745     }
2746
2747   if ((p1 != NULL_TREE) != (p2 != NULL_TREE))
2748     /* One set of parameters has more parameters lists than the
2749        other.  */
2750     return 0;
2751
2752   return 1;
2753 }
2754
2755 /* Determine whether PARM is a parameter pack.  */
2756
2757 bool
2758 template_parameter_pack_p (const_tree parm)
2759 {
2760   /* Determine if we have a non-type template parameter pack.  */
2761   if (TREE_CODE (parm) == PARM_DECL)
2762     return (DECL_TEMPLATE_PARM_P (parm)
2763             && TEMPLATE_PARM_PARAMETER_PACK (DECL_INITIAL (parm)));
2764   if (TREE_CODE (parm) == TEMPLATE_PARM_INDEX)
2765     return TEMPLATE_PARM_PARAMETER_PACK (parm);
2766
2767   /* If this is a list of template parameters, we could get a
2768      TYPE_DECL or a TEMPLATE_DECL.  */
2769   if (TREE_CODE (parm) == TYPE_DECL || TREE_CODE (parm) == TEMPLATE_DECL)
2770     parm = TREE_TYPE (parm);
2771
2772   /* Otherwise it must be a type template parameter.  */
2773   return ((TREE_CODE (parm) == TEMPLATE_TYPE_PARM
2774            || TREE_CODE (parm) == TEMPLATE_TEMPLATE_PARM)
2775           && TEMPLATE_TYPE_PARAMETER_PACK (parm));
2776 }
2777
2778 /* Determine if T is a function parameter pack.  */
2779
2780 bool
2781 function_parameter_pack_p (const_tree t)
2782 {
2783   if (t && TREE_CODE (t) == PARM_DECL)
2784     return FUNCTION_PARAMETER_PACK_P (t);
2785   return false;
2786 }
2787
2788 /* Return the function template declaration of PRIMARY_FUNC_TMPL_INST.
2789    PRIMARY_FUNC_TMPL_INST is a primary function template instantiation.  */
2790
2791 tree
2792 get_function_template_decl (const_tree primary_func_tmpl_inst)
2793 {
2794   if (! primary_func_tmpl_inst
2795       || TREE_CODE (primary_func_tmpl_inst) != FUNCTION_DECL
2796       || ! primary_template_instantiation_p (primary_func_tmpl_inst))
2797     return NULL;
2798
2799   return DECL_TEMPLATE_RESULT (DECL_TI_TEMPLATE (primary_func_tmpl_inst));
2800 }
2801
2802 /* Return true iff the function parameter PARAM_DECL was expanded
2803    from the function parameter pack PACK.  */
2804
2805 bool
2806 function_parameter_expanded_from_pack_p (tree param_decl, tree pack)
2807 {
2808   if (DECL_ARTIFICIAL (param_decl)
2809       || !function_parameter_pack_p (pack))
2810     return false;
2811
2812   /* The parameter pack and its pack arguments have the same
2813      DECL_PARM_INDEX.  */
2814   return DECL_PARM_INDEX (pack) == DECL_PARM_INDEX (param_decl);
2815 }
2816
2817 /* Determine whether ARGS describes a variadic template args list,
2818    i.e., one that is terminated by a template argument pack.  */
2819
2820 static bool
2821 template_args_variadic_p (tree args)
2822 {
2823   int nargs;
2824   tree last_parm;
2825
2826   if (args == NULL_TREE)
2827     return false;
2828
2829   args = INNERMOST_TEMPLATE_ARGS (args);
2830   nargs = TREE_VEC_LENGTH (args);
2831
2832   if (nargs == 0)
2833     return false;
2834
2835   last_parm = TREE_VEC_ELT (args, nargs - 1);
2836
2837   return ARGUMENT_PACK_P (last_parm);
2838 }
2839
2840 /* Generate a new name for the parameter pack name NAME (an
2841    IDENTIFIER_NODE) that incorporates its */
2842
2843 static tree
2844 make_ith_pack_parameter_name (tree name, int i)
2845 {
2846   /* Munge the name to include the parameter index.  */
2847 #define NUMBUF_LEN 128
2848   char numbuf[NUMBUF_LEN];
2849   char* newname;
2850   int newname_len;
2851
2852   snprintf (numbuf, NUMBUF_LEN, "%i", i);
2853   newname_len = IDENTIFIER_LENGTH (name)
2854                 + strlen (numbuf) + 2;
2855   newname = (char*)alloca (newname_len);
2856   snprintf (newname, newname_len,
2857             "%s#%i", IDENTIFIER_POINTER (name), i);
2858   return get_identifier (newname);
2859 }
2860
2861 /* Return true if T is a primary function, class or alias template
2862    instantiation.  */
2863
2864 bool
2865 primary_template_instantiation_p (const_tree t)
2866 {
2867   if (!t)
2868     return false;
2869
2870   if (TREE_CODE (t) == FUNCTION_DECL)
2871     return DECL_LANG_SPECIFIC (t)
2872            && DECL_TEMPLATE_INSTANTIATION (t)
2873            && PRIMARY_TEMPLATE_P (DECL_TI_TEMPLATE (t));
2874   else if (CLASS_TYPE_P (t) && !TYPE_DECL_ALIAS_P (TYPE_NAME (t)))
2875     return CLASSTYPE_TEMPLATE_INSTANTIATION (t)
2876            && PRIMARY_TEMPLATE_P (CLASSTYPE_TI_TEMPLATE (t));
2877   else if (TYPE_P (t)
2878            && TYPE_TEMPLATE_INFO (t)
2879            && PRIMARY_TEMPLATE_P (TYPE_TI_TEMPLATE (t))
2880            && DECL_TEMPLATE_INSTANTIATION (TYPE_NAME (t)))
2881     return true;
2882   return false;
2883 }
2884
2885 /* Return true if PARM is a template template parameter.  */
2886
2887 bool
2888 template_template_parameter_p (const_tree parm)
2889 {
2890   return DECL_TEMPLATE_TEMPLATE_PARM_P (parm);
2891 }
2892
2893 /* Return the template parameters of T if T is a
2894    primary template instantiation, NULL otherwise.  */
2895
2896 tree
2897 get_primary_template_innermost_parameters (const_tree t)
2898 {
2899   tree parms = NULL, template_info = NULL;
2900
2901   if ((template_info = get_template_info (t))
2902       && primary_template_instantiation_p (t))
2903     parms = INNERMOST_TEMPLATE_PARMS
2904         (DECL_TEMPLATE_PARMS (TI_TEMPLATE (template_info)));
2905
2906   return parms;
2907 }
2908
2909 /* Return the template parameters of the LEVELth level from the full list
2910    of template parameters PARMS.  */
2911
2912 tree
2913 get_template_parms_at_level (tree parms, int level)
2914 {
2915   tree p;
2916   if (!parms
2917       || TREE_CODE (parms) != TREE_LIST
2918       || level > TMPL_PARMS_DEPTH (parms))
2919     return NULL_TREE;
2920
2921   for (p = parms; p; p = TREE_CHAIN (p))
2922     if (TMPL_PARMS_DEPTH (p) == level)
2923       return p;
2924
2925   return NULL_TREE;
2926 }
2927
2928 /* Returns the template arguments of T if T is a template instantiation,
2929    NULL otherwise.  */
2930
2931 tree
2932 get_template_innermost_arguments (const_tree t)
2933 {
2934   tree args = NULL, template_info = NULL;
2935
2936   if ((template_info = get_template_info (t))
2937       && TI_ARGS (template_info))
2938     args = INNERMOST_TEMPLATE_ARGS (TI_ARGS (template_info));
2939
2940   return args;
2941 }
2942
2943 /* Return the argument pack elements of T if T is a template argument pack,
2944    NULL otherwise.  */
2945
2946 tree
2947 get_template_argument_pack_elems (const_tree t)
2948 {
2949   if (TREE_CODE (t) != TYPE_ARGUMENT_PACK
2950       && TREE_CODE (t) != NONTYPE_ARGUMENT_PACK)
2951     return NULL;
2952
2953   return ARGUMENT_PACK_ARGS (t);
2954 }
2955
2956 /* Structure used to track the progress of find_parameter_packs_r.  */
2957 struct find_parameter_pack_data
2958 {
2959   /* TREE_LIST that will contain all of the parameter packs found by
2960      the traversal.  */
2961   tree* parameter_packs;
2962
2963   /* Set of AST nodes that have been visited by the traversal.  */
2964   struct pointer_set_t *visited;
2965 };
2966
2967 /* Identifies all of the argument packs that occur in a template
2968    argument and appends them to the TREE_LIST inside DATA, which is a
2969    find_parameter_pack_data structure. This is a subroutine of
2970    make_pack_expansion and uses_parameter_packs.  */
2971 static tree
2972 find_parameter_packs_r (tree *tp, int *walk_subtrees, void* data)
2973 {
2974   tree t = *tp;
2975   struct find_parameter_pack_data* ppd =
2976     (struct find_parameter_pack_data*)data;
2977   bool parameter_pack_p = false;
2978
2979   /* Handle type aliases/typedefs.  */
2980   if (TYPE_P (t)
2981       && TYPE_NAME (t)
2982       && TREE_CODE (TYPE_NAME (t)) == TYPE_DECL
2983       && TYPE_DECL_ALIAS_P (TYPE_NAME (t)))
2984     {
2985       if (TYPE_TEMPLATE_INFO (t))
2986         cp_walk_tree (&TYPE_TI_ARGS (t),
2987                       &find_parameter_packs_r,
2988                       ppd, ppd->visited);
2989       *walk_subtrees = 0;
2990       return NULL_TREE;
2991     }
2992
2993   /* Identify whether this is a parameter pack or not.  */
2994   switch (TREE_CODE (t))
2995     {
2996     case TEMPLATE_PARM_INDEX:
2997       if (TEMPLATE_PARM_PARAMETER_PACK (t))
2998         parameter_pack_p = true;
2999       break;
3000
3001     case TEMPLATE_TYPE_PARM:
3002       t = TYPE_MAIN_VARIANT (t);
3003     case TEMPLATE_TEMPLATE_PARM:
3004       if (TEMPLATE_TYPE_PARAMETER_PACK (t))
3005         parameter_pack_p = true;
3006       break;
3007
3008     case PARM_DECL:
3009       if (FUNCTION_PARAMETER_PACK_P (t))
3010         {
3011           /* We don't want to walk into the type of a PARM_DECL,
3012              because we don't want to see the type parameter pack.  */
3013           *walk_subtrees = 0;
3014           parameter_pack_p = true;
3015         }
3016       break;
3017
3018     case BASES:
3019       parameter_pack_p = true;
3020       break;
3021     default:
3022       /* Not a parameter pack.  */
3023       break;
3024     }
3025
3026   if (parameter_pack_p)
3027     {
3028       /* Add this parameter pack to the list.  */
3029       *ppd->parameter_packs = tree_cons (NULL_TREE, t, *ppd->parameter_packs);
3030     }
3031
3032   if (TYPE_P (t))
3033     cp_walk_tree (&TYPE_CONTEXT (t),
3034                   &find_parameter_packs_r, ppd, ppd->visited);
3035
3036   /* This switch statement will return immediately if we don't find a
3037      parameter pack.  */
3038   switch (TREE_CODE (t))
3039     {
3040     case TEMPLATE_PARM_INDEX:
3041       return NULL_TREE;
3042
3043     case BOUND_TEMPLATE_TEMPLATE_PARM:
3044       /* Check the template itself.  */
3045       cp_walk_tree (&TREE_TYPE (TYPE_TI_TEMPLATE (t)),
3046                     &find_parameter_packs_r, ppd, ppd->visited);
3047       /* Check the template arguments.  */
3048       cp_walk_tree (&TYPE_TI_ARGS (t), &find_parameter_packs_r, ppd,
3049                     ppd->visited);
3050       *walk_subtrees = 0;
3051       return NULL_TREE;
3052
3053     case TEMPLATE_TYPE_PARM:
3054     case TEMPLATE_TEMPLATE_PARM:
3055       return NULL_TREE;
3056
3057     case PARM_DECL:
3058       return NULL_TREE;
3059
3060     case RECORD_TYPE:
3061       if (TYPE_PTRMEMFUNC_P (t))
3062         return NULL_TREE;
3063       /* Fall through.  */
3064
3065     case UNION_TYPE:
3066     case ENUMERAL_TYPE:
3067       if (TYPE_TEMPLATE_INFO (t))
3068         cp_walk_tree (&TI_ARGS (TYPE_TEMPLATE_INFO (t)),
3069                       &find_parameter_packs_r, ppd, ppd->visited);
3070
3071       *walk_subtrees = 0;
3072       return NULL_TREE;
3073
3074     case CONSTRUCTOR:
3075     case TEMPLATE_DECL:
3076       cp_walk_tree (&TREE_TYPE (t),
3077                     &find_parameter_packs_r, ppd, ppd->visited);
3078       return NULL_TREE;
3079
3080     case TYPENAME_TYPE:
3081       cp_walk_tree (&TYPENAME_TYPE_FULLNAME (t), &find_parameter_packs_r,
3082                    ppd, ppd->visited);
3083       *walk_subtrees = 0;
3084       return NULL_TREE;
3085
3086     case TYPE_PACK_EXPANSION:
3087     case EXPR_PACK_EXPANSION:
3088       *walk_subtrees = 0;
3089       return NULL_TREE;
3090
3091     case INTEGER_TYPE:
3092       cp_walk_tree (&TYPE_MAX_VALUE (t), &find_parameter_packs_r,
3093                     ppd, ppd->visited);
3094       *walk_subtrees = 0;
3095       return NULL_TREE;
3096
3097     case IDENTIFIER_NODE:
3098       cp_walk_tree (&TREE_TYPE (t), &find_parameter_packs_r, ppd,
3099                     ppd->visited);
3100       *walk_subtrees = 0;
3101       return NULL_TREE;
3102
3103     default:
3104       return NULL_TREE;
3105     }
3106
3107   return NULL_TREE;
3108 }
3109
3110 /* Determines if the expression or type T uses any parameter packs.  */
3111 bool
3112 uses_parameter_packs (tree t)
3113 {
3114   tree parameter_packs = NULL_TREE;
3115   struct find_parameter_pack_data ppd;
3116   ppd.parameter_packs = &parameter_packs;
3117   ppd.visited = pointer_set_create ();
3118   cp_walk_tree (&t, &find_parameter_packs_r, &ppd, ppd.visited);
3119   pointer_set_destroy (ppd.visited);
3120   return parameter_packs != NULL_TREE;
3121 }
3122
3123 /* Turn ARG, which may be an expression, type, or a TREE_LIST
3124    representation a base-class initializer into a parameter pack
3125    expansion. If all goes well, the resulting node will be an
3126    EXPR_PACK_EXPANSION, TYPE_PACK_EXPANSION, or TREE_LIST,
3127    respectively.  */
3128 tree
3129 make_pack_expansion (tree arg)
3130 {
3131   tree result;
3132   tree parameter_packs = NULL_TREE;
3133   bool for_types = false;
3134   struct find_parameter_pack_data ppd;
3135
3136   if (!arg || arg == error_mark_node)
3137     return arg;
3138
3139   if (TREE_CODE (arg) == TREE_LIST)
3140     {
3141       /* The only time we will see a TREE_LIST here is for a base
3142          class initializer.  In this case, the TREE_PURPOSE will be a
3143          _TYPE node (representing the base class expansion we're
3144          initializing) and the TREE_VALUE will be a TREE_LIST
3145          containing the initialization arguments.
3146
3147          The resulting expansion looks somewhat different from most
3148          expansions. Rather than returning just one _EXPANSION, we
3149          return a TREE_LIST whose TREE_PURPOSE is a
3150          TYPE_PACK_EXPANSION containing the bases that will be
3151          initialized.  The TREE_VALUE will be identical to the
3152          original TREE_VALUE, which is a list of arguments that will
3153          be passed to each base.  We do not introduce any new pack
3154          expansion nodes into the TREE_VALUE (although it is possible
3155          that some already exist), because the TREE_PURPOSE and
3156          TREE_VALUE all need to be expanded together with the same
3157          _EXPANSION node.  Note that the TYPE_PACK_EXPANSION in the
3158          resulting TREE_PURPOSE will mention the parameter packs in
3159          both the bases and the arguments to the bases.  */
3160       tree purpose;
3161       tree value;
3162       tree parameter_packs = NULL_TREE;
3163
3164       /* Determine which parameter packs will be used by the base
3165          class expansion.  */
3166       ppd.visited = pointer_set_create ();
3167       ppd.parameter_packs = &parameter_packs;
3168       cp_walk_tree (&TREE_PURPOSE (arg), &find_parameter_packs_r,
3169                     &ppd, ppd.visited);
3170
3171       if (parameter_packs == NULL_TREE)
3172         {
3173           error ("base initializer expansion %<%T%> contains no parameter packs", arg);
3174           pointer_set_destroy (ppd.visited);
3175           return error_mark_node;
3176         }
3177
3178       if (TREE_VALUE (arg) != void_type_node)
3179         {
3180           /* Collect the sets of parameter packs used in each of the
3181              initialization arguments.  */
3182           for (value = TREE_VALUE (arg); value; value = TREE_CHAIN (value))
3183             {
3184               /* Determine which parameter packs will be expanded in this
3185                  argument.  */
3186               cp_walk_tree (&TREE_VALUE (value), &find_parameter_packs_r,
3187                             &ppd, ppd.visited);
3188             }
3189         }
3190
3191       pointer_set_destroy (ppd.visited);
3192
3193       /* Create the pack expansion type for the base type.  */
3194       purpose = cxx_make_type (TYPE_PACK_EXPANSION);
3195       SET_PACK_EXPANSION_PATTERN (purpose, TREE_PURPOSE (arg));
3196       PACK_EXPANSION_PARAMETER_PACKS (purpose) = parameter_packs;
3197
3198       /* Just use structural equality for these TYPE_PACK_EXPANSIONS;
3199          they will rarely be compared to anything.  */
3200       SET_TYPE_STRUCTURAL_EQUALITY (purpose);
3201
3202       return tree_cons (purpose, TREE_VALUE (arg), NULL_TREE);
3203     }
3204
3205   if (TYPE_P (arg) || TREE_CODE (arg) == TEMPLATE_DECL)
3206     for_types = true;
3207
3208   /* Build the PACK_EXPANSION_* node.  */
3209   result = for_types
3210      ? cxx_make_type (TYPE_PACK_EXPANSION)
3211      : make_node (EXPR_PACK_EXPANSION);
3212   SET_PACK_EXPANSION_PATTERN (result, arg);
3213   if (TREE_CODE (result) == EXPR_PACK_EXPANSION)
3214     {
3215       /* Propagate type and const-expression information.  */
3216       TREE_TYPE (result) = TREE_TYPE (arg);
3217       TREE_CONSTANT (result) = TREE_CONSTANT (arg);
3218     }
3219   else
3220     /* Just use structural equality for these TYPE_PACK_EXPANSIONS;
3221        they will rarely be compared to anything.  */
3222     SET_TYPE_STRUCTURAL_EQUALITY (result);
3223
3224   /* Determine which parameter packs will be expanded.  */
3225   ppd.parameter_packs = &parameter_packs;
3226   ppd.visited = pointer_set_create ();
3227   cp_walk_tree (&arg, &find_parameter_packs_r, &ppd, ppd.visited);
3228   pointer_set_destroy (ppd.visited);
3229
3230   /* Make sure we found some parameter packs.  */
3231   if (parameter_packs == NULL_TREE)
3232     {
3233       if (TYPE_P (arg))
3234         error ("expansion pattern %<%T%> contains no argument packs", arg);
3235       else
3236         error ("expansion pattern %<%E%> contains no argument packs", arg);
3237       return error_mark_node;
3238     }
3239   PACK_EXPANSION_PARAMETER_PACKS (result) = parameter_packs;
3240
3241   return result;
3242 }
3243
3244 /* Checks T for any "bare" parameter packs, which have not yet been
3245    expanded, and issues an error if any are found. This operation can
3246    only be done on full expressions or types (e.g., an expression
3247    statement, "if" condition, etc.), because we could have expressions like:
3248
3249      foo(f(g(h(args)))...)
3250
3251    where "args" is a parameter pack. check_for_bare_parameter_packs
3252    should not be called for the subexpressions args, h(args),
3253    g(h(args)), or f(g(h(args))), because we would produce erroneous
3254    error messages.
3255
3256    Returns TRUE and emits an error if there were bare parameter packs,
3257    returns FALSE otherwise.  */
3258 bool
3259 check_for_bare_parameter_packs (tree t)
3260 {
3261   tree parameter_packs = NULL_TREE;
3262   struct find_parameter_pack_data ppd;
3263
3264   if (!processing_template_decl || !t || t == error_mark_node)
3265     return false;
3266
3267   if (TREE_CODE (t) == TYPE_DECL)
3268     t = TREE_TYPE (t);
3269
3270   ppd.parameter_packs = &parameter_packs;
3271   ppd.visited = pointer_set_create ();
3272   cp_walk_tree (&t, &find_parameter_packs_r, &ppd, ppd.visited);
3273   pointer_set_destroy (ppd.visited);
3274
3275   if (parameter_packs)
3276     {
3277       error ("parameter packs not expanded with %<...%>:");
3278       while (parameter_packs)
3279         {
3280           tree pack = TREE_VALUE (parameter_packs);
3281           tree name = NULL_TREE;
3282
3283           if (TREE_CODE (pack) == TEMPLATE_TYPE_PARM
3284               || TREE_CODE (pack) == TEMPLATE_TEMPLATE_PARM)
3285             name = TYPE_NAME (pack);
3286           else if (TREE_CODE (pack) == TEMPLATE_PARM_INDEX)
3287             name = DECL_NAME (TEMPLATE_PARM_DECL (pack));
3288           else
3289             name = DECL_NAME (pack);
3290
3291           if (name)
3292             inform (input_location, "        %qD", name);
3293           else
3294             inform (input_location, "        <anonymous>");
3295
3296           parameter_packs = TREE_CHAIN (parameter_packs);
3297         }
3298
3299       return true;
3300     }
3301
3302   return false;
3303 }
3304
3305 /* Expand any parameter packs that occur in the template arguments in
3306    ARGS.  */
3307 tree
3308 expand_template_argument_pack (tree args)
3309 {
3310   tree result_args = NULL_TREE;
3311   int in_arg, out_arg = 0, nargs = args ? TREE_VEC_LENGTH (args) : 0;
3312   int num_result_args = -1;
3313   int non_default_args_count = -1;
3314
3315   /* First, determine if we need to expand anything, and the number of
3316      slots we'll need.  */
3317   for (in_arg = 0; in_arg < nargs; ++in_arg)
3318     {
3319       tree arg = TREE_VEC_ELT (args, in_arg);
3320       if (arg == NULL_TREE)
3321         return args;
3322       if (ARGUMENT_PACK_P (arg))
3323         {
3324           int num_packed = TREE_VEC_LENGTH (ARGUMENT_PACK_ARGS (arg));
3325           if (num_result_args < 0)
3326             num_result_args = in_arg + num_packed;
3327           else
3328             num_result_args += num_packed;
3329         }
3330       else
3331         {
3332           if (num_result_args >= 0)
3333             num_result_args++;
3334         }
3335     }
3336
3337   /* If no expansion is necessary, we're done.  */
3338   if (num_result_args < 0)
3339     return args;
3340
3341   /* Expand arguments.  */
3342   result_args = make_tree_vec (num_result_args);
3343   if (NON_DEFAULT_TEMPLATE_ARGS_COUNT (args))
3344     non_default_args_count =
3345       GET_NON_DEFAULT_TEMPLATE_ARGS_COUNT (args);
3346   for (in_arg = 0; in_arg < nargs; ++in_arg)
3347     {
3348       tree arg = TREE_VEC_ELT (args, in_arg);
3349       if (ARGUMENT_PACK_P (arg))
3350         {
3351           tree packed = ARGUMENT_PACK_ARGS (arg);
3352           int i, num_packed = TREE_VEC_LENGTH (packed);
3353           for (i = 0; i < num_packed; ++i, ++out_arg)
3354             TREE_VEC_ELT (result_args, out_arg) = TREE_VEC_ELT(packed, i);
3355           if (non_default_args_count > 0)
3356             non_default_args_count += num_packed;
3357         }
3358       else
3359         {
3360           TREE_VEC_ELT (result_args, out_arg) = arg;
3361           ++out_arg;
3362         }
3363     }
3364   if (non_default_args_count >= 0)
3365     SET_NON_DEFAULT_TEMPLATE_ARGS_COUNT (result_args, non_default_args_count);
3366   return result_args;
3367 }
3368
3369 /* Checks if DECL shadows a template parameter.
3370
3371    [temp.local]: A template-parameter shall not be redeclared within its
3372    scope (including nested scopes).
3373
3374    Emits an error and returns TRUE if the DECL shadows a parameter,
3375    returns FALSE otherwise.  */
3376
3377 bool
3378 check_template_shadow (tree decl)
3379 {
3380   tree olddecl;
3381
3382   /* If we're not in a template, we can't possibly shadow a template
3383      parameter.  */
3384   if (!current_template_parms)
3385     return true;
3386
3387   /* Figure out what we're shadowing.  */
3388   if (TREE_CODE (decl) == OVERLOAD)
3389     decl = OVL_CURRENT (decl);
3390   olddecl = innermost_non_namespace_value (DECL_NAME (decl));
3391
3392   /* If there's no previous binding for this name, we're not shadowing
3393      anything, let alone a template parameter.  */
3394   if (!olddecl)
3395     return true;
3396
3397   /* If we're not shadowing a template parameter, we're done.  Note
3398      that OLDDECL might be an OVERLOAD (or perhaps even an
3399      ERROR_MARK), so we can't just blithely assume it to be a _DECL
3400      node.  */
3401   if (!DECL_P (olddecl) || !DECL_TEMPLATE_PARM_P (olddecl))
3402     return true;
3403
3404   /* We check for decl != olddecl to avoid bogus errors for using a
3405      name inside a class.  We check TPFI to avoid duplicate errors for
3406      inline member templates.  */
3407   if (decl == olddecl
3408       || TEMPLATE_PARMS_FOR_INLINE (current_template_parms))
3409     return true;
3410
3411   error ("declaration of %q+#D", decl);
3412   error (" shadows template parm %q+#D", olddecl);
3413   return false;
3414 }
3415
3416 /* Return a new TEMPLATE_PARM_INDEX with the indicated INDEX, LEVEL,
3417    ORIG_LEVEL, DECL, and TYPE.  NUM_SIBLINGS is the total number of
3418    template parameters.  */
3419
3420 static tree
3421 build_template_parm_index (int index,
3422                            int level,
3423                            int orig_level,
3424                            int num_siblings,
3425                            tree decl,
3426                            tree type)
3427 {
3428   tree t = make_node (TEMPLATE_PARM_INDEX);
3429   TEMPLATE_PARM_IDX (t) = index;
3430   TEMPLATE_PARM_LEVEL (t) = level;
3431   TEMPLATE_PARM_ORIG_LEVEL (t) = orig_level;
3432   TEMPLATE_PARM_NUM_SIBLINGS (t) = num_siblings;
3433   TEMPLATE_PARM_DECL (t) = decl;
3434   TREE_TYPE (t) = type;
3435   TREE_CONSTANT (t) = TREE_CONSTANT (decl);
3436   TREE_READONLY (t) = TREE_READONLY (decl);
3437
3438   return t;
3439 }
3440
3441 /* Find the canonical type parameter for the given template type
3442    parameter.  Returns the canonical type parameter, which may be TYPE
3443    if no such parameter existed.  */
3444
3445 static tree
3446 canonical_type_parameter (tree type)
3447 {
3448   tree list;
3449   int idx = TEMPLATE_TYPE_IDX (type);
3450   if (!canonical_template_parms)
3451     canonical_template_parms = VEC_alloc (tree, gc, idx+1);
3452
3453   while (VEC_length (tree, canonical_template_parms) <= (unsigned)idx)
3454     VEC_safe_push (tree, gc, canonical_template_parms, NULL_TREE);
3455
3456   list = VEC_index (tree, canonical_template_parms, idx);
3457   while (list && !comptypes (type, TREE_VALUE (list), COMPARE_STRUCTURAL))
3458     list = TREE_CHAIN (list);
3459
3460   if (list)
3461     return TREE_VALUE (list);
3462   else
3463     {
3464       VEC_replace(tree, canonical_template_parms, idx,
3465                   tree_cons (NULL_TREE, type,
3466                              VEC_index (tree, canonical_template_parms, idx)));
3467       return type;
3468     }
3469 }
3470
3471 /* Return a TEMPLATE_PARM_INDEX, similar to INDEX, but whose
3472    TEMPLATE_PARM_LEVEL has been decreased by LEVELS.  If such a
3473    TEMPLATE_PARM_INDEX already exists, it is returned; otherwise, a
3474    new one is created.  */
3475
3476 static tree
3477 reduce_template_parm_level (tree index, tree type, int levels, tree args,
3478                             tsubst_flags_t complain)
3479 {
3480   if (TEMPLATE_PARM_DESCENDANTS (index) == NULL_TREE
3481       || (TEMPLATE_PARM_LEVEL (TEMPLATE_PARM_DESCENDANTS (index))
3482           != TEMPLATE_PARM_LEVEL (index) - levels)
3483       || !same_type_p (type, TREE_TYPE (TEMPLATE_PARM_DESCENDANTS (index))))
3484     {
3485       tree orig_decl = TEMPLATE_PARM_DECL (index);
3486       tree decl, t;
3487
3488       decl = build_decl (DECL_SOURCE_LOCATION (orig_decl),
3489                          TREE_CODE (orig_decl), DECL_NAME (orig_decl), type);
3490       TREE_CONSTANT (decl) = TREE_CONSTANT (orig_decl);
3491       TREE_READONLY (decl) = TREE_READONLY (orig_decl);
3492       DECL_ARTIFICIAL (decl) = 1;
3493       SET_DECL_TEMPLATE_PARM_P (decl);
3494
3495       t = build_template_parm_index (TEMPLATE_PARM_IDX (index),
3496                                      TEMPLATE_PARM_LEVEL (index) - levels,
3497                                      TEMPLATE_PARM_ORIG_LEVEL (index),
3498                                      TEMPLATE_PARM_NUM_SIBLINGS (index),
3499                                      decl, type);
3500       TEMPLATE_PARM_DESCENDANTS (index) = t;
3501       TEMPLATE_PARM_PARAMETER_PACK (t)
3502         = TEMPLATE_PARM_PARAMETER_PACK (index);
3503
3504         /* Template template parameters need this.  */
3505       if (TREE_CODE (decl) == TEMPLATE_DECL)
3506         DECL_TEMPLATE_PARMS (decl) = tsubst_template_parms
3507           (DECL_TEMPLATE_PARMS (TEMPLATE_PARM_DECL (index)),
3508            args, complain);
3509     }
3510
3511   return TEMPLATE_PARM_DESCENDANTS (index);
3512 }
3513
3514 /* Process information from new template parameter PARM and append it
3515    to the LIST being built.  This new parameter is a non-type
3516    parameter iff IS_NON_TYPE is true. This new parameter is a
3517    parameter pack iff IS_PARAMETER_PACK is true.  The location of PARM
3518    is in PARM_LOC. NUM_TEMPLATE_PARMS is the size of the template
3519    parameter list PARM belongs to. This is used used to create a
3520    proper canonical type for the type of PARM that is to be created,
3521    iff PARM is a type.  If the size is not known, this parameter shall
3522    be set to 0.  */
3523
3524 tree
3525 process_template_parm (tree list, location_t parm_loc, tree parm,
3526                        bool is_non_type, bool is_parameter_pack,
3527                        unsigned num_template_parms)
3528 {
3529   tree decl = 0;
3530   tree defval;
3531   tree err_parm_list;
3532   int idx = 0;
3533
3534   gcc_assert (TREE_CODE (parm) == TREE_LIST);
3535   defval = TREE_PURPOSE (parm);
3536
3537   if (list)
3538     {
3539       tree p = tree_last (list);
3540
3541       if (p && TREE_VALUE (p) != error_mark_node)
3542         {
3543           p = TREE_VALUE (p);
3544           if (TREE_CODE (p) == TYPE_DECL || TREE_CODE (p) == TEMPLATE_DECL)
3545             idx = TEMPLATE_TYPE_IDX (TREE_TYPE (p));
3546           else
3547             idx = TEMPLATE_PARM_IDX (DECL_INITIAL (p));
3548         }
3549
3550       ++idx;
3551     }
3552   else
3553     idx = 0;
3554
3555   if (is_non_type)
3556     {
3557       parm = TREE_VALUE (parm);
3558
3559       SET_DECL_TEMPLATE_PARM_P (parm);
3560
3561       if (TREE_TYPE (parm) == error_mark_node)
3562         {