OSDN Git Service

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