OSDN Git Service

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