OSDN Git Service

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