OSDN Git Service

8ae4ed511cc4260d6e8bc54aed69a39eead12cc5
[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               SET_DECL_TEMPLATE_SPECIALIZATION (tmpl);
2221               DECL_INITIAL (DECL_TEMPLATE_RESULT (tmpl)) = NULL_TREE;
2222               if (have_def)
2223                 {
2224                   DECL_SOURCE_LOCATION (tmpl) = DECL_SOURCE_LOCATION (decl);
2225                   DECL_SOURCE_LOCATION (DECL_TEMPLATE_RESULT (tmpl))
2226                     = DECL_SOURCE_LOCATION (decl);
2227                   /* We want to use the argument list specified in the
2228                      definition, not in the original declaration.  */
2229                   DECL_ARGUMENTS (DECL_TEMPLATE_RESULT (tmpl))
2230                     = DECL_ARGUMENTS (decl);
2231                 }
2232               return tmpl;
2233             }
2234
2235           /* Set up the DECL_TEMPLATE_INFO for DECL.  */
2236           DECL_TEMPLATE_INFO (decl) = tree_cons (tmpl, targs, NULL_TREE);
2237
2238           /* Inherit default function arguments from the template
2239              DECL is specializing.  */
2240           copy_default_args_to_explicit_spec (decl);
2241
2242           /* This specialization has the same protection as the
2243              template it specializes.  */
2244           TREE_PRIVATE (decl) = TREE_PRIVATE (gen_tmpl);
2245           TREE_PROTECTED (decl) = TREE_PROTECTED (gen_tmpl);
2246
2247           /* 7.1.1-1 [dcl.stc]
2248
2249              A storage-class-specifier shall not be specified in an
2250              explicit specialization...
2251
2252              The parser rejects these, so unless action is taken here,
2253              explicit function specializations will always appear with
2254              global linkage.
2255
2256              The action recommended by the C++ CWG in response to C++
2257              defect report 605 is to make the storage class and linkage
2258              of the explicit specialization match the templated function:
2259
2260              http://www.open-std.org/jtc1/sc22/wg21/docs/cwg_active.html#605
2261            */
2262           if (tsk == tsk_expl_spec && DECL_FUNCTION_TEMPLATE_P (gen_tmpl))
2263             {
2264               tree tmpl_func = DECL_TEMPLATE_RESULT (gen_tmpl);
2265               gcc_assert (TREE_CODE (tmpl_func) == FUNCTION_DECL);
2266
2267               /* This specialization has the same linkage and visibility as
2268                  the function template it specializes.  */
2269               TREE_PUBLIC (decl) = TREE_PUBLIC (tmpl_func);
2270               if (! TREE_PUBLIC (decl))
2271                 {
2272                   DECL_INTERFACE_KNOWN (decl) = 1;
2273                   DECL_NOT_REALLY_EXTERN (decl) = 1;
2274                 }
2275               DECL_THIS_STATIC (decl) = DECL_THIS_STATIC (tmpl_func);
2276               if (DECL_VISIBILITY_SPECIFIED (tmpl_func))
2277                 {
2278                   DECL_VISIBILITY_SPECIFIED (decl) = 1;
2279                   DECL_VISIBILITY (decl) = DECL_VISIBILITY (tmpl_func);
2280                 }
2281             }
2282
2283           /* If DECL is a friend declaration, declared using an
2284              unqualified name, the namespace associated with DECL may
2285              have been set incorrectly.  For example, in:
2286
2287                template <typename T> void f(T);
2288                namespace N {
2289                  struct S { friend void f<int>(int); }
2290                }
2291
2292              we will have set the DECL_CONTEXT for the friend
2293              declaration to N, rather than to the global namespace.  */
2294           if (DECL_NAMESPACE_SCOPE_P (decl))
2295             DECL_CONTEXT (decl) = DECL_CONTEXT (tmpl);
2296
2297           if (is_friend && !have_def)
2298             /* This is not really a declaration of a specialization.
2299                It's just the name of an instantiation.  But, it's not
2300                a request for an instantiation, either.  */
2301             SET_DECL_IMPLICIT_INSTANTIATION (decl);
2302           else if (DECL_CONSTRUCTOR_P (decl) || DECL_DESTRUCTOR_P (decl))
2303             /* This is indeed a specialization.  In case of constructors
2304                and destructors, we need in-charge and not-in-charge
2305                versions in V3 ABI.  */
2306             clone_function_decl (decl, /*update_method_vec_p=*/0);
2307
2308           /* Register this specialization so that we can find it
2309              again.  */
2310           decl = register_specialization (decl, gen_tmpl, targs, is_friend);
2311         }
2312     }
2313
2314   return decl;
2315 }
2316
2317 /* Returns 1 iff PARMS1 and PARMS2 are identical sets of template
2318    parameters.  These are represented in the same format used for
2319    DECL_TEMPLATE_PARMS.  */
2320
2321 int
2322 comp_template_parms (const_tree parms1, const_tree parms2)
2323 {
2324   const_tree p1;
2325   const_tree p2;
2326
2327   if (parms1 == parms2)
2328     return 1;
2329
2330   for (p1 = parms1, p2 = parms2;
2331        p1 != NULL_TREE && p2 != NULL_TREE;
2332        p1 = TREE_CHAIN (p1), p2 = TREE_CHAIN (p2))
2333     {
2334       tree t1 = TREE_VALUE (p1);
2335       tree t2 = TREE_VALUE (p2);
2336       int i;
2337
2338       gcc_assert (TREE_CODE (t1) == TREE_VEC);
2339       gcc_assert (TREE_CODE (t2) == TREE_VEC);
2340
2341       if (TREE_VEC_LENGTH (t1) != TREE_VEC_LENGTH (t2))
2342         return 0;
2343
2344       for (i = 0; i < TREE_VEC_LENGTH (t2); ++i)
2345         {
2346           tree parm1 = TREE_VALUE (TREE_VEC_ELT (t1, i));
2347           tree parm2 = TREE_VALUE (TREE_VEC_ELT (t2, i));
2348
2349           /* If either of the template parameters are invalid, assume
2350              they match for the sake of error recovery. */
2351           if (parm1 == error_mark_node || parm2 == error_mark_node)
2352             return 1;
2353
2354           if (TREE_CODE (parm1) != TREE_CODE (parm2))
2355             return 0;
2356
2357           if (TREE_CODE (parm1) == TEMPLATE_TYPE_PARM
2358               && (TEMPLATE_TYPE_PARAMETER_PACK (parm1)
2359                   == TEMPLATE_TYPE_PARAMETER_PACK (parm2)))
2360             continue;
2361           else if (!same_type_p (TREE_TYPE (parm1), TREE_TYPE (parm2)))
2362             return 0;
2363         }
2364     }
2365
2366   if ((p1 != NULL_TREE) != (p2 != NULL_TREE))
2367     /* One set of parameters has more parameters lists than the
2368        other.  */
2369     return 0;
2370
2371   return 1;
2372 }
2373
2374 /* Determine whether PARM is a parameter pack.  */
2375 bool 
2376 template_parameter_pack_p (const_tree parm)
2377 {
2378   /* Determine if we have a non-type template parameter pack.  */
2379   if (TREE_CODE (parm) == PARM_DECL)
2380     return (DECL_TEMPLATE_PARM_P (parm) 
2381             && TEMPLATE_PARM_PARAMETER_PACK (DECL_INITIAL (parm)));
2382
2383   /* If this is a list of template parameters, we could get a
2384      TYPE_DECL or a TEMPLATE_DECL.  */ 
2385   if (TREE_CODE (parm) == TYPE_DECL || TREE_CODE (parm) == TEMPLATE_DECL)
2386     parm = TREE_TYPE (parm);
2387
2388   return ((TREE_CODE (parm) == TEMPLATE_TYPE_PARM
2389            || TREE_CODE (parm) == TEMPLATE_TEMPLATE_PARM)
2390           && TEMPLATE_TYPE_PARAMETER_PACK (parm));
2391 }
2392
2393 /* Determine whether ARGS describes a variadic template args list,
2394    i.e., one that is terminated by a template argument pack.  */
2395 static bool 
2396 template_args_variadic_p (tree args)
2397 {
2398   int nargs;
2399   tree last_parm;
2400
2401   if (args == NULL_TREE)
2402     return false;
2403
2404   args = INNERMOST_TEMPLATE_ARGS (args);
2405   nargs = TREE_VEC_LENGTH (args);
2406
2407   if (nargs == 0)
2408     return false;
2409
2410   last_parm = TREE_VEC_ELT (args, nargs - 1);
2411
2412   return ARGUMENT_PACK_P (last_parm);
2413 }
2414
2415 /* Generate a new name for the parameter pack name NAME (an
2416    IDENTIFIER_NODE) that incorporates its */
2417 static tree
2418 make_ith_pack_parameter_name (tree name, int i)
2419 {
2420   /* Munge the name to include the parameter index.  */
2421   char numbuf[128];
2422   char* newname;
2423   
2424   sprintf(numbuf, "%i", i);
2425   newname = (char*)alloca (IDENTIFIER_LENGTH (name) + strlen(numbuf) + 2);
2426   sprintf(newname, "%s#%i", IDENTIFIER_POINTER (name), i);
2427   return get_identifier (newname);
2428 }
2429
2430 /* Structure used to track the progress of find_parameter_packs_r.  */
2431 struct find_parameter_pack_data 
2432 {
2433   /* TREE_LIST that will contain all of the parameter packs found by
2434      the traversal.  */
2435   tree* parameter_packs;
2436
2437   /* Set of AST nodes that have been visited by the traversal.  */
2438   struct pointer_set_t *visited;
2439 };
2440
2441 /* Identifies all of the argument packs that occur in a template
2442    argument and appends them to the TREE_LIST inside DATA, which is a
2443    find_parameter_pack_data structure. This is a subroutine of
2444    make_pack_expansion and uses_parameter_packs.  */
2445 static tree
2446 find_parameter_packs_r (tree *tp, int *walk_subtrees, void* data)
2447 {
2448   tree t = *tp;
2449   struct find_parameter_pack_data* ppd = 
2450     (struct find_parameter_pack_data*)data;
2451   bool parameter_pack_p = false;
2452
2453   /* Identify whether this is a parameter pack or not.  */
2454   switch (TREE_CODE (t))
2455     {
2456     case TEMPLATE_PARM_INDEX:
2457       if (TEMPLATE_PARM_PARAMETER_PACK (t))
2458         parameter_pack_p = true;
2459       break;
2460
2461     case TEMPLATE_TYPE_PARM:
2462     case TEMPLATE_TEMPLATE_PARM:
2463       if (TEMPLATE_TYPE_PARAMETER_PACK (t))
2464         parameter_pack_p = true;
2465       break;
2466
2467     case PARM_DECL:
2468       if (FUNCTION_PARAMETER_PACK_P (t))
2469         {
2470           /* We don't want to walk into the type of a PARM_DECL,
2471              because we don't want to see the type parameter pack.  */
2472           *walk_subtrees = 0;
2473           parameter_pack_p = true;
2474         }
2475       break;
2476
2477     default:
2478       /* Not a parameter pack.  */
2479       break;
2480     }
2481
2482   if (parameter_pack_p)
2483     {
2484       /* Add this parameter pack to the list.  */
2485       *ppd->parameter_packs = tree_cons (NULL_TREE, t, *ppd->parameter_packs);
2486     }
2487
2488   if (TYPE_P (t))
2489     cp_walk_tree (&TYPE_CONTEXT (t), 
2490                   &find_parameter_packs_r, ppd, ppd->visited);
2491
2492   /* This switch statement will return immediately if we don't find a
2493      parameter pack.  */
2494   switch (TREE_CODE (t)) 
2495     {
2496     case TEMPLATE_PARM_INDEX:
2497       return NULL_TREE;
2498
2499     case BOUND_TEMPLATE_TEMPLATE_PARM:
2500       /* Check the template itself.  */
2501       cp_walk_tree (&TREE_TYPE (TYPE_TI_TEMPLATE (t)), 
2502                     &find_parameter_packs_r, ppd, ppd->visited);
2503       /* Check the template arguments.  */
2504       cp_walk_tree (&TYPE_TI_ARGS (t), &find_parameter_packs_r, ppd, 
2505                     ppd->visited);
2506       *walk_subtrees = 0;
2507       return NULL_TREE;
2508
2509     case TEMPLATE_TYPE_PARM:
2510     case TEMPLATE_TEMPLATE_PARM:
2511       return NULL_TREE;
2512
2513     case PARM_DECL:
2514       return NULL_TREE;
2515
2516     case RECORD_TYPE:
2517       if (TYPE_PTRMEMFUNC_P (t))
2518         return NULL_TREE;
2519       /* Fall through.  */
2520
2521     case UNION_TYPE:
2522     case ENUMERAL_TYPE:
2523       if (TYPE_TEMPLATE_INFO (t))
2524         cp_walk_tree (&TREE_VALUE (TYPE_TEMPLATE_INFO (t)), 
2525                       &find_parameter_packs_r, ppd, ppd->visited);
2526
2527       *walk_subtrees = 0;
2528       return NULL_TREE;
2529
2530     case TEMPLATE_DECL:
2531       cp_walk_tree (&TREE_TYPE (t),
2532                     &find_parameter_packs_r, ppd, ppd->visited);
2533       return NULL_TREE;
2534  
2535     case TYPENAME_TYPE:
2536       cp_walk_tree (&TYPENAME_TYPE_FULLNAME (t), &find_parameter_packs_r,
2537                    ppd, ppd->visited);
2538       *walk_subtrees = 0;
2539       return NULL_TREE;
2540       
2541     case TYPE_PACK_EXPANSION:
2542     case EXPR_PACK_EXPANSION:
2543       *walk_subtrees = 0;
2544       return NULL_TREE;
2545
2546     case INTEGER_TYPE:
2547       cp_walk_tree (&TYPE_MAX_VALUE (t), &find_parameter_packs_r, 
2548                     ppd, ppd->visited);
2549       *walk_subtrees = 0;
2550       return NULL_TREE;
2551
2552     case IDENTIFIER_NODE:
2553       cp_walk_tree (&TREE_TYPE (t), &find_parameter_packs_r, ppd, 
2554                     ppd->visited);
2555       *walk_subtrees = 0;
2556       return NULL_TREE;
2557
2558     default:
2559       return NULL_TREE;
2560     }
2561
2562   return NULL_TREE;
2563 }
2564
2565 /* Determines if the expression or type T uses any parameter packs.  */
2566 bool
2567 uses_parameter_packs (tree t)
2568 {
2569   tree parameter_packs = NULL_TREE;
2570   struct find_parameter_pack_data ppd;
2571   ppd.parameter_packs = &parameter_packs;
2572   ppd.visited = pointer_set_create ();
2573   cp_walk_tree (&t, &find_parameter_packs_r, &ppd, ppd.visited);
2574   pointer_set_destroy (ppd.visited);
2575   return parameter_packs != NULL_TREE;
2576 }
2577
2578 /* Turn ARG, which may be an expression, type, or a TREE_LIST
2579    representation a base-class initializer into a parameter pack
2580    expansion. If all goes well, the resulting node will be an
2581    EXPR_PACK_EXPANSION, TYPE_PACK_EXPANSION, or TREE_LIST,
2582    respectively.  */
2583 tree 
2584 make_pack_expansion (tree arg)
2585 {
2586   tree result;
2587   tree parameter_packs = NULL_TREE;
2588   bool for_types = false;
2589   struct find_parameter_pack_data ppd;
2590
2591   if (!arg || arg == error_mark_node)
2592     return arg;
2593
2594   if (TREE_CODE (arg) == TREE_LIST)
2595     {
2596       /* The only time we will see a TREE_LIST here is for a base
2597          class initializer.  In this case, the TREE_PURPOSE will be a
2598          _TYPE node (representing the base class expansion we're
2599          initializing) and the TREE_VALUE will be a TREE_LIST
2600          containing the initialization arguments. 
2601
2602          The resulting expansion looks somewhat different from most
2603          expansions. Rather than returning just one _EXPANSION, we
2604          return a TREE_LIST whose TREE_PURPOSE is a
2605          TYPE_PACK_EXPANSION containing the bases that will be
2606          initialized.  The TREE_VALUE will be identical to the
2607          original TREE_VALUE, which is a list of arguments that will
2608          be passed to each base.  We do not introduce any new pack
2609          expansion nodes into the TREE_VALUE (although it is possible
2610          that some already exist), because the TREE_PURPOSE and
2611          TREE_VALUE all need to be expanded together with the same
2612          _EXPANSION node.  Note that the TYPE_PACK_EXPANSION in the
2613          resulting TREE_PURPOSE will mention the parameter packs in
2614          both the bases and the arguments to the bases.  */
2615       tree purpose;
2616       tree value;
2617       tree parameter_packs = NULL_TREE;
2618
2619       /* Determine which parameter packs will be used by the base
2620          class expansion.  */
2621       ppd.visited = pointer_set_create ();
2622       ppd.parameter_packs = &parameter_packs;
2623       cp_walk_tree (&TREE_PURPOSE (arg), &find_parameter_packs_r, 
2624                     &ppd, ppd.visited);
2625
2626       if (parameter_packs == NULL_TREE)
2627         {
2628           error ("base initializer expansion %<%T%> contains no parameter packs", arg);
2629           pointer_set_destroy (ppd.visited);
2630           return error_mark_node;
2631         }
2632
2633       if (TREE_VALUE (arg) != void_type_node)
2634         {
2635           /* Collect the sets of parameter packs used in each of the
2636              initialization arguments.  */
2637           for (value = TREE_VALUE (arg); value; value = TREE_CHAIN (value))
2638             {
2639               /* Determine which parameter packs will be expanded in this
2640                  argument.  */
2641               cp_walk_tree (&TREE_VALUE (value), &find_parameter_packs_r, 
2642                             &ppd, ppd.visited);
2643             }
2644         }
2645
2646       pointer_set_destroy (ppd.visited);
2647
2648       /* Create the pack expansion type for the base type.  */
2649       purpose = make_node (TYPE_PACK_EXPANSION);
2650       SET_PACK_EXPANSION_PATTERN (purpose, TREE_PURPOSE (arg));
2651       PACK_EXPANSION_PARAMETER_PACKS (purpose) = parameter_packs;
2652
2653       /* Just use structural equality for these TYPE_PACK_EXPANSIONS;
2654          they will rarely be compared to anything.  */
2655       SET_TYPE_STRUCTURAL_EQUALITY (purpose);
2656
2657       return tree_cons (purpose, TREE_VALUE (arg), NULL_TREE);
2658     }
2659
2660   if (TYPE_P (arg) || TREE_CODE (arg) == TEMPLATE_DECL)
2661     for_types = true;
2662
2663   /* Build the PACK_EXPANSION_* node.  */
2664   result = make_node (for_types ? TYPE_PACK_EXPANSION : EXPR_PACK_EXPANSION);
2665   SET_PACK_EXPANSION_PATTERN (result, arg);
2666   if (TREE_CODE (result) == EXPR_PACK_EXPANSION)
2667     {
2668       /* Propagate type and const-expression information.  */
2669       TREE_TYPE (result) = TREE_TYPE (arg);
2670       TREE_CONSTANT (result) = TREE_CONSTANT (arg);
2671     }
2672   else
2673     /* Just use structural equality for these TYPE_PACK_EXPANSIONS;
2674        they will rarely be compared to anything.  */
2675     SET_TYPE_STRUCTURAL_EQUALITY (result);
2676
2677   /* Determine which parameter packs will be expanded.  */
2678   ppd.parameter_packs = &parameter_packs;
2679   ppd.visited = pointer_set_create ();
2680   cp_walk_tree (&arg, &find_parameter_packs_r, &ppd, ppd.visited);
2681   pointer_set_destroy (ppd.visited);
2682
2683   /* Make sure we found some parameter packs.  */
2684   if (parameter_packs == NULL_TREE)
2685     {
2686       if (TYPE_P (arg))
2687         error ("expansion pattern %<%T%> contains no argument packs", arg);
2688       else
2689         error ("expansion pattern %<%E%> contains no argument packs", arg);
2690       return error_mark_node;
2691     }
2692   PACK_EXPANSION_PARAMETER_PACKS (result) = parameter_packs;
2693
2694   return result;
2695 }
2696
2697 /* Checks T for any "bare" parameter packs, which have not yet been
2698    expanded, and issues an error if any are found. This operation can
2699    only be done on full expressions or types (e.g., an expression
2700    statement, "if" condition, etc.), because we could have expressions like:
2701
2702      foo(f(g(h(args)))...)
2703
2704    where "args" is a parameter pack. check_for_bare_parameter_packs
2705    should not be called for the subexpressions args, h(args),
2706    g(h(args)), or f(g(h(args))), because we would produce erroneous
2707    error messages. 
2708
2709    Returns TRUE and emits an error if there were bare parameter packs,
2710    returns FALSE otherwise.  */
2711 bool 
2712 check_for_bare_parameter_packs (tree t)
2713 {
2714   tree parameter_packs = NULL_TREE;
2715   struct find_parameter_pack_data ppd;
2716
2717   if (!processing_template_decl || !t || t == error_mark_node)
2718     return false;
2719
2720   if (TREE_CODE (t) == TYPE_DECL)
2721     t = TREE_TYPE (t);
2722
2723   ppd.parameter_packs = &parameter_packs;
2724   ppd.visited = pointer_set_create ();
2725   cp_walk_tree (&t, &find_parameter_packs_r, &ppd, ppd.visited);
2726   pointer_set_destroy (ppd.visited);
2727
2728   if (parameter_packs) 
2729     {
2730       error ("parameter packs not expanded with %<...%>:");
2731       while (parameter_packs)
2732         {
2733           tree pack = TREE_VALUE (parameter_packs);
2734           tree name = NULL_TREE;
2735
2736           if (TREE_CODE (pack) == TEMPLATE_TYPE_PARM
2737               || TREE_CODE (pack) == TEMPLATE_TEMPLATE_PARM)
2738             name = TYPE_NAME (pack);
2739           else if (TREE_CODE (pack) == TEMPLATE_PARM_INDEX)
2740             name = DECL_NAME (TEMPLATE_PARM_DECL (pack));
2741           else
2742             name = DECL_NAME (pack);
2743
2744           if (name)
2745             inform (input_location, "        %qD", name);
2746           else
2747             inform (input_location, "        <anonymous>");
2748
2749           parameter_packs = TREE_CHAIN (parameter_packs);
2750         }
2751
2752       return true;
2753     }
2754
2755   return false;
2756 }
2757
2758 /* Expand any parameter packs that occur in the template arguments in
2759    ARGS.  */
2760 tree
2761 expand_template_argument_pack (tree args)
2762 {
2763   tree result_args = NULL_TREE;
2764   int in_arg, out_arg = 0, nargs = args ? TREE_VEC_LENGTH (args) : 0;
2765   int num_result_args = -1;
2766
2767   /* First, determine if we need to expand anything, and the number of
2768      slots we'll need.  */
2769   for (in_arg = 0; in_arg < nargs; ++in_arg)
2770     {
2771       tree arg = TREE_VEC_ELT (args, in_arg);
2772       if (ARGUMENT_PACK_P (arg))
2773         {
2774           int num_packed = TREE_VEC_LENGTH (ARGUMENT_PACK_ARGS (arg));
2775           if (num_result_args < 0)
2776             num_result_args = in_arg + num_packed;
2777           else
2778             num_result_args += num_packed;
2779         }
2780       else
2781         {
2782           if (num_result_args >= 0)
2783             num_result_args++;
2784         }
2785     }
2786
2787   /* If no expansion is necessary, we're done.  */
2788   if (num_result_args < 0)
2789     return args;
2790
2791   /* Expand arguments.  */
2792   result_args = make_tree_vec (num_result_args);
2793   for (in_arg = 0; in_arg < nargs; ++in_arg)
2794     {
2795       tree arg = TREE_VEC_ELT (args, in_arg);
2796       if (ARGUMENT_PACK_P (arg))
2797         {
2798           tree packed = ARGUMENT_PACK_ARGS (arg);
2799           int i, num_packed = TREE_VEC_LENGTH (packed);
2800           for (i = 0; i < num_packed; ++i, ++out_arg)
2801             TREE_VEC_ELT (result_args, out_arg) = TREE_VEC_ELT(packed, i);
2802         }
2803       else
2804         {
2805           TREE_VEC_ELT (result_args, out_arg) = arg;
2806           ++out_arg;
2807         }
2808     }
2809
2810   return result_args;
2811 }
2812
2813 /* Checks if DECL shadows a template parameter.
2814
2815    [temp.local]: A template-parameter shall not be redeclared within its
2816    scope (including nested scopes).
2817
2818    Emits an error and returns TRUE if the DECL shadows a parameter,
2819    returns FALSE otherwise.  */
2820
2821 bool
2822 check_template_shadow (tree decl)
2823 {
2824   tree olddecl;
2825
2826   /* If we're not in a template, we can't possibly shadow a template
2827      parameter.  */
2828   if (!current_template_parms)
2829     return true;
2830
2831   /* Figure out what we're shadowing.  */
2832   if (TREE_CODE (decl) == OVERLOAD)
2833     decl = OVL_CURRENT (decl);
2834   olddecl = innermost_non_namespace_value (DECL_NAME (decl));
2835
2836   /* If there's no previous binding for this name, we're not shadowing
2837      anything, let alone a template parameter.  */
2838   if (!olddecl)
2839     return true;
2840
2841   /* If we're not shadowing a template parameter, we're done.  Note
2842      that OLDDECL might be an OVERLOAD (or perhaps even an
2843      ERROR_MARK), so we can't just blithely assume it to be a _DECL
2844      node.  */
2845   if (!DECL_P (olddecl) || !DECL_TEMPLATE_PARM_P (olddecl))
2846     return true;
2847
2848   /* We check for decl != olddecl to avoid bogus errors for using a
2849      name inside a class.  We check TPFI to avoid duplicate errors for
2850      inline member templates.  */
2851   if (decl == olddecl
2852       || TEMPLATE_PARMS_FOR_INLINE (current_template_parms))
2853     return true;
2854
2855   error ("declaration of %q+#D", decl);
2856   error (" shadows template parm %q+#D", olddecl);
2857   return false;
2858 }
2859
2860 /* Return a new TEMPLATE_PARM_INDEX with the indicated INDEX, LEVEL,
2861    ORIG_LEVEL, DECL, and TYPE.  */
2862
2863 static tree
2864 build_template_parm_index (int index,
2865                            int level,
2866                            int orig_level,
2867                            tree decl,
2868                            tree type)
2869 {
2870   tree t = make_node (TEMPLATE_PARM_INDEX);
2871   TEMPLATE_PARM_IDX (t) = index;
2872   TEMPLATE_PARM_LEVEL (t) = level;
2873   TEMPLATE_PARM_ORIG_LEVEL (t) = orig_level;
2874   TEMPLATE_PARM_DECL (t) = decl;
2875   TREE_TYPE (t) = type;
2876   TREE_CONSTANT (t) = TREE_CONSTANT (decl);
2877   TREE_READONLY (t) = TREE_READONLY (decl);
2878
2879   return t;
2880 }
2881
2882 /* Find the canonical type parameter for the given template type
2883    parameter.  Returns the canonical type parameter, which may be TYPE
2884    if no such parameter existed.  */
2885 static tree
2886 canonical_type_parameter (tree type)
2887 {
2888   tree list;
2889   int idx = TEMPLATE_TYPE_IDX (type);
2890   if (!canonical_template_parms)
2891     canonical_template_parms = VEC_alloc (tree, gc, idx+1);
2892
2893   while (VEC_length (tree, canonical_template_parms) <= (unsigned)idx)
2894     VEC_safe_push (tree, gc, canonical_template_parms, NULL_TREE);
2895
2896   list = VEC_index (tree, canonical_template_parms, idx);
2897   while (list && !comptypes (type, TREE_VALUE (list), COMPARE_STRUCTURAL))
2898     list = TREE_CHAIN (list);
2899
2900   if (list)
2901     return TREE_VALUE (list);
2902   else
2903     {
2904       VEC_replace(tree, canonical_template_parms, idx,
2905                   tree_cons (NULL_TREE, type, 
2906                              VEC_index (tree, canonical_template_parms, idx)));
2907       return type;
2908     }
2909 }
2910
2911 /* Return a TEMPLATE_PARM_INDEX, similar to INDEX, but whose
2912    TEMPLATE_PARM_LEVEL has been decreased by LEVELS.  If such a
2913    TEMPLATE_PARM_INDEX already exists, it is returned; otherwise, a
2914    new one is created.  */
2915
2916 static tree
2917 reduce_template_parm_level (tree index, tree type, int levels, tree args,
2918                             tsubst_flags_t complain)
2919 {
2920   if (TEMPLATE_PARM_DESCENDANTS (index) == NULL_TREE
2921       || (TEMPLATE_PARM_LEVEL (TEMPLATE_PARM_DESCENDANTS (index))
2922           != TEMPLATE_PARM_LEVEL (index) - levels))
2923     {
2924       tree orig_decl = TEMPLATE_PARM_DECL (index);
2925       tree decl, t;
2926
2927       decl = build_decl (TREE_CODE (orig_decl), DECL_NAME (orig_decl), type);
2928       TREE_CONSTANT (decl) = TREE_CONSTANT (orig_decl);
2929       TREE_READONLY (decl) = TREE_READONLY (orig_decl);
2930       DECL_ARTIFICIAL (decl) = 1;
2931       SET_DECL_TEMPLATE_PARM_P (decl);
2932
2933       t = build_template_parm_index (TEMPLATE_PARM_IDX (index),
2934                                      TEMPLATE_PARM_LEVEL (index) - levels,
2935                                      TEMPLATE_PARM_ORIG_LEVEL (index),
2936                                      decl, type);
2937       TEMPLATE_PARM_DESCENDANTS (index) = t;
2938       TEMPLATE_PARM_PARAMETER_PACK (t) 
2939         = TEMPLATE_PARM_PARAMETER_PACK (index);
2940
2941         /* Template template parameters need this.  */
2942       if (TREE_CODE (decl) == TEMPLATE_DECL)
2943         DECL_TEMPLATE_PARMS (decl) = tsubst_template_parms
2944           (DECL_TEMPLATE_PARMS (TEMPLATE_PARM_DECL (index)),
2945            args, complain);
2946     }
2947
2948   return TEMPLATE_PARM_DESCENDANTS (index);
2949 }
2950
2951 /* Process information from new template parameter PARM and append it to the
2952    LIST being built.  This new parameter is a non-type parameter iff
2953    IS_NON_TYPE is true. This new parameter is a parameter
2954    pack iff IS_PARAMETER_PACK is true.  */
2955
2956 tree
2957 process_template_parm (tree list, tree parm, bool is_non_type, 
2958                        bool is_parameter_pack)
2959 {
2960   tree decl = 0;
2961   tree defval;
2962   tree err_parm_list;
2963   int idx = 0;
2964
2965   gcc_assert (TREE_CODE (parm) == TREE_LIST);
2966   defval = TREE_PURPOSE (parm);
2967
2968   if (list)
2969     {
2970       tree p = tree_last (list);
2971
2972       if (p && TREE_VALUE (p) != error_mark_node)
2973         {
2974           p = TREE_VALUE (p);
2975           if (TREE_CODE (p) == TYPE_DECL || TREE_CODE (p) == TEMPLATE_DECL)
2976             idx = TEMPLATE_TYPE_IDX (TREE_TYPE (p));
2977           else
2978             idx = TEMPLATE_PARM_IDX (DECL_INITIAL (p));
2979         }
2980
2981       ++idx;
2982     }
2983   else
2984     idx = 0;
2985
2986   if (is_non_type)
2987     {
2988       parm = TREE_VALUE (parm);
2989
2990       SET_DECL_TEMPLATE_PARM_P (parm);
2991
2992       if (TREE_TYPE (parm) == error_mark_node)
2993         {
2994           err_parm_list = build_tree_list (defval, parm);
2995           TREE_VALUE (err_parm_list) = error_mark_node;
2996            return chainon (list, err_parm_list);
2997         }
2998       else
2999       {
3000         /* [temp.param]
3001
3002            The top-level cv-qualifiers on the template-parameter are
3003            ignored when determining its type.  */
3004         TREE_TYPE (parm) = TYPE_MAIN_VARIANT (TREE_TYPE (parm));
3005         if (invalid_nontype_parm_type_p (TREE_TYPE (parm), 1))
3006           {
3007             err_parm_list = build_tree_list (defval, parm);
3008             TREE_VALUE (err_parm_list) = error_mark_node;
3009              return chainon (list, err_parm_list);
3010           }
3011
3012         if (uses_parameter_packs (TREE_TYPE (parm)) && !is_parameter_pack)
3013           {
3014             /* This template parameter is not a parameter pack, but it
3015                should be. Complain about "bare" parameter packs.  */
3016             check_for_bare_parameter_packs (TREE_TYPE (parm));
3017             
3018             /* Recover by calling this a parameter pack.  */
3019             is_parameter_pack = true;
3020           }
3021       }
3022
3023       /* A template parameter is not modifiable.  */
3024       TREE_CONSTANT (parm) = 1;
3025       TREE_READONLY (parm) = 1;
3026       decl = build_decl (CONST_DECL, DECL_NAME (parm), TREE_TYPE (parm));
3027       TREE_CONSTANT (decl) = 1;
3028       TREE_READONLY (decl) = 1;
3029       DECL_INITIAL (parm) = DECL_INITIAL (decl)
3030         = build_template_parm_index (idx, processing_template_decl,
3031                                      processing_template_decl,
3032                                      decl, TREE_TYPE (parm));
3033
3034       TEMPLATE_PARM_PARAMETER_PACK (DECL_INITIAL (parm)) 
3035         = is_parameter_pack;
3036     }
3037   else
3038     {
3039       tree t;
3040       parm = TREE_VALUE (TREE_VALUE (parm));
3041
3042       if (parm && TREE_CODE (parm) == TEMPLATE_DECL)
3043         {
3044           t = cxx_make_type (TEMPLATE_TEMPLATE_PARM);
3045           /* This is for distinguishing between real templates and template
3046              template parameters */
3047           TREE_TYPE (parm) = t;
3048           TREE_TYPE (DECL_TEMPLATE_RESULT (parm)) = t;
3049           decl = parm;
3050         }
3051       else
3052         {
3053           t = cxx_make_type (TEMPLATE_TYPE_PARM);
3054           /* parm is either IDENTIFIER_NODE or NULL_TREE.  */
3055           decl = build_decl (TYPE_DECL, parm, t);
3056         }
3057
3058       TYPE_NAME (t) = decl;
3059       TYPE_STUB_DECL (t) = decl;
3060       parm = decl;
3061       TEMPLATE_TYPE_PARM_INDEX (t)
3062         = build_template_parm_index (idx, processing_template_decl,
3063                                      processing_template_decl,
3064                                      decl, TREE_TYPE (parm));
3065       TEMPLATE_TYPE_PARAMETER_PACK (t) = is_parameter_pack;
3066       TYPE_CANONICAL (t) = canonical_type_parameter (t);
3067     }
3068   DECL_ARTIFICIAL (decl) = 1;
3069   SET_DECL_TEMPLATE_PARM_P (decl);
3070   pushdecl (decl);
3071   parm = build_tree_list (defval, parm);
3072   return chainon (list, parm);
3073 }
3074
3075 /* The end of a template parameter list has been reached.  Process the
3076    tree list into a parameter vector, converting each parameter into a more
3077    useful form.  Type parameters are saved as IDENTIFIER_NODEs, and others
3078    as PARM_DECLs.  */
3079
3080 tree
3081 end_template_parm_list (tree parms)
3082 {
3083   int nparms;
3084   tree parm, next;
3085   tree saved_parmlist = make_tree_vec (list_length (parms));
3086
3087   current_template_parms
3088     = tree_cons (size_int (processing_template_decl),
3089                  saved_parmlist, current_template_parms);
3090
3091   for (parm = parms, nparms = 0; parm; parm = next, nparms++)
3092     {
3093       next = TREE_CHAIN (parm);
3094       TREE_VEC_ELT (saved_parmlist, nparms) = parm;
3095       TREE_CHAIN (parm) = NULL_TREE;
3096     }
3097
3098   --processing_template_parmlist;
3099
3100   return saved_parmlist;
3101 }
3102
3103 /* end_template_decl is called after a template declaration is seen.  */
3104
3105 void
3106 end_template_decl (void)
3107 {
3108   reset_specialization ();
3109
3110   if (! processing_template_decl)
3111     return;
3112
3113   /* This matches the pushlevel in begin_template_parm_list.  */
3114   finish_scope ();
3115
3116   --processing_template_decl;
3117   current_template_parms = TREE_CHAIN (current_template_parms);
3118 }
3119
3120 /* Within the declaration of a template, return all levels of template
3121    parameters that apply.  The template parameters are represented as
3122    a TREE_VEC, in the form documented in cp-tree.h for template
3123    arguments.  */
3124
3125 static tree
3126 current_template_args (void)
3127 {
3128   tree header;
3129   tree args = NULL_TREE;
3130   int length = TMPL_PARMS_DEPTH (current_template_parms);
3131   int l = length;
3132
3133   /* If there is only one level of template parameters, we do not
3134      create a TREE_VEC of TREE_VECs.  Instead, we return a single
3135      TREE_VEC containing the arguments.  */
3136   if (length > 1)
3137     args = make_tree_vec (length);
3138
3139   for (header = current_template_parms; header; header = TREE_CHAIN (header))
3140     {
3141       tree a = copy_node (TREE_VALUE (header));
3142       int i;
3143
3144       TREE_TYPE (a) = NULL_TREE;
3145       for (i = TREE_VEC_LENGTH (a) - 1; i >= 0; --i)
3146         {
3147           tree t = TREE_VEC_ELT (a, i);
3148
3149           /* T will be a list if we are called from within a
3150              begin/end_template_parm_list pair, but a vector directly
3151              if within a begin/end_member_template_processing pair.  */
3152           if (TREE_CODE (t) == TREE_LIST)
3153             {
3154               t = TREE_VALUE (t);
3155
3156               if (!error_operand_p (t))
3157                 {
3158                   if (TREE_CODE (t) == TYPE_DECL
3159                       || TREE_CODE (t) == TEMPLATE_DECL)
3160                     {
3161                       t = TREE_TYPE (t);
3162                       
3163                       if (TEMPLATE_TYPE_PARAMETER_PACK (t))
3164                         {
3165                           /* Turn this argument into a TYPE_ARGUMENT_PACK
3166                              with a single element, which expands T.  */
3167                           tree vec = make_tree_vec (1);
3168                           TREE_VEC_ELT (vec, 0) = make_pack_expansion (t);
3169                           
3170                           t = make_node (TYPE_ARGUMENT_PACK);
3171                           SET_ARGUMENT_PACK_ARGS (t, vec);
3172                         }
3173                     }
3174                   else
3175                     {
3176                       t = DECL_INITIAL (t);
3177                       
3178                       if (TEMPLATE_PARM_PARAMETER_PACK (t))
3179                         {
3180                           /* Turn this argument into a NONTYPE_ARGUMENT_PACK
3181                              with a single element, which expands T.  */
3182                           tree vec = make_tree_vec (1);
3183                           tree type = TREE_TYPE (TEMPLATE_PARM_DECL (t));
3184                           TREE_VEC_ELT (vec, 0) = make_pack_expansion (t);
3185                           
3186                           t  = make_node (NONTYPE_ARGUMENT_PACK);
3187                           SET_ARGUMENT_PACK_ARGS (t, vec);
3188                           TREE_TYPE (t) = type;
3189                         }
3190                     }
3191                   TREE_VEC_ELT (a, i) = t;
3192                 }
3193             }
3194         }
3195
3196       if (length > 1)
3197         TREE_VEC_ELT (args, --l) = a;
3198       else
3199         args = a;
3200     }
3201
3202   return args;
3203 }
3204
3205 /* Return a TEMPLATE_DECL corresponding to DECL, using the indicated
3206    template PARMS.  If MEMBER_TEMPLATE_P is true, the new template is
3207    a member template.  Used by push_template_decl below.  */
3208
3209 static tree
3210 build_template_decl (tree decl, tree parms, bool member_template_p)
3211 {
3212   tree tmpl = build_lang_decl (TEMPLATE_DECL, DECL_NAME (decl), NULL_TREE);
3213   DECL_TEMPLATE_PARMS (tmpl) = parms;
3214   DECL_CONTEXT (tmpl) = DECL_CONTEXT (decl);
3215   DECL_MEMBER_TEMPLATE_P (tmpl) = member_template_p;
3216   if (DECL_LANG_SPECIFIC (decl))
3217     {
3218       DECL_STATIC_FUNCTION_P (tmpl) = DECL_STATIC_FUNCTION_P (decl);
3219       DECL_CONSTRUCTOR_P (tmpl) = DECL_CONSTRUCTOR_P (decl);
3220       DECL_DESTRUCTOR_P (tmpl) = DECL_DESTRUCTOR_P (decl);
3221       DECL_NONCONVERTING_P (tmpl) = DECL_NONCONVERTING_P (decl);
3222       DECL_ASSIGNMENT_OPERATOR_P (tmpl) = DECL_ASSIGNMENT_OPERATOR_P (decl);
3223       if (DECL_OVERLOADED_OPERATOR_P (decl))
3224         SET_OVERLOADED_OPERATOR_CODE (tmpl,
3225                                       DECL_OVERLOADED_OPERATOR_P (decl));
3226     }
3227
3228   return tmpl;
3229 }
3230
3231 struct template_parm_data
3232 {
3233   /* The level of the template parameters we are currently
3234      processing.  */
3235   int level;
3236
3237   /* The index of the specialization argument we are currently
3238      processing.  */
3239   int current_arg;
3240
3241   /* An array whose size is the number of template parameters.  The
3242      elements are nonzero if the parameter has been used in any one
3243      of the arguments processed so far.  */
3244   int* parms;
3245
3246   /* An array whose size is the number of template arguments.  The
3247      elements are nonzero if the argument makes use of template
3248      parameters of this level.  */
3249   int* arg_uses_template_parms;
3250 };
3251
3252 /* Subroutine of push_template_decl used to see if each template
3253    parameter in a partial specialization is used in the explicit
3254    argument list.  If T is of the LEVEL given in DATA (which is
3255    treated as a template_parm_data*), then DATA->PARMS is marked
3256    appropriately.  */
3257
3258 static int
3259 mark_template_parm (tree t, void* data)
3260 {
3261   int level;
3262   int idx;
3263   struct template_parm_data* tpd = (struct template_parm_data*) data;
3264
3265   if (TREE_CODE (t) == TEMPLATE_PARM_INDEX)
3266     {
3267       level = TEMPLATE_PARM_LEVEL (t);
3268       idx = TEMPLATE_PARM_IDX (t);
3269     }
3270   else
3271     {
3272       level = TEMPLATE_TYPE_LEVEL (t);
3273       idx = TEMPLATE_TYPE_IDX (t);
3274     }
3275
3276   if (level == tpd->level)
3277     {
3278       tpd->parms[idx] = 1;
3279       tpd->arg_uses_template_parms[tpd->current_arg] = 1;
3280     }
3281
3282   /* Return zero so that for_each_template_parm will continue the
3283      traversal of the tree; we want to mark *every* template parm.  */
3284   return 0;
3285 }
3286
3287 /* Process the partial specialization DECL.  */
3288
3289 static tree
3290 process_partial_specialization (tree decl)
3291 {
3292   tree type = TREE_TYPE (decl);
3293   tree maintmpl = CLASSTYPE_TI_TEMPLATE (type);
3294   tree specargs = CLASSTYPE_TI_ARGS (type);
3295   tree inner_args = INNERMOST_TEMPLATE_ARGS (specargs);
3296   tree main_inner_parms = DECL_INNERMOST_TEMPLATE_PARMS (maintmpl);
3297   tree inner_parms;
3298   int nargs = TREE_VEC_LENGTH (inner_args);
3299   int ntparms;
3300   int  i;
3301   int did_error_intro = 0;
3302   struct template_parm_data tpd;
3303   struct template_parm_data tpd2;
3304
3305   gcc_assert (current_template_parms);
3306
3307   inner_parms = INNERMOST_TEMPLATE_PARMS (current_template_parms);
3308   ntparms = TREE_VEC_LENGTH (inner_parms);
3309
3310   /* We check that each of the template parameters given in the
3311      partial specialization is used in the argument list to the
3312      specialization.  For example:
3313
3314        template <class T> struct S;
3315        template <class T> struct S<T*>;
3316
3317      The second declaration is OK because `T*' uses the template
3318      parameter T, whereas
3319
3320        template <class T> struct S<int>;
3321
3322      is no good.  Even trickier is:
3323
3324        template <class T>
3325        struct S1
3326        {
3327           template <class U>
3328           struct S2;
3329           template <class U>
3330           struct S2<T>;
3331        };
3332
3333      The S2<T> declaration is actually invalid; it is a
3334      full-specialization.  Of course,
3335
3336           template <class U>
3337           struct S2<T (*)(U)>;
3338
3339      or some such would have been OK.  */
3340   tpd.level = TMPL_PARMS_DEPTH (current_template_parms);
3341   tpd.parms = (int *) alloca (sizeof (int) * ntparms);
3342   memset (tpd.parms, 0, sizeof (int) * ntparms);
3343
3344   tpd.arg_uses_template_parms = (int *) alloca (sizeof (int) * nargs);
3345   memset (tpd.arg_uses_template_parms, 0, sizeof (int) * nargs);
3346   for (i = 0; i < nargs; ++i)
3347     {
3348       tpd.current_arg = i;
3349       for_each_template_parm (TREE_VEC_ELT (inner_args, i),
3350                               &mark_template_parm,
3351                               &tpd,
3352                               NULL,
3353                               /*include_nondeduced_p=*/false);
3354     }
3355   for (i = 0; i < ntparms; ++i)
3356     if (tpd.parms[i] == 0)
3357       {
3358         /* One of the template parms was not used in the
3359            specialization.  */
3360         if (!did_error_intro)
3361           {
3362             error ("template parameters not used in partial specialization:");
3363             did_error_intro = 1;
3364           }
3365
3366         error ("        %qD", TREE_VALUE (TREE_VEC_ELT (inner_parms, i)));
3367       }
3368
3369   /* [temp.class.spec]
3370
3371      The argument list of the specialization shall not be identical to
3372      the implicit argument list of the primary template.  */
3373   if (comp_template_args
3374       (inner_args,
3375        INNERMOST_TEMPLATE_ARGS (CLASSTYPE_TI_ARGS (TREE_TYPE
3376                                                    (maintmpl)))))
3377     error ("partial specialization %qT does not specialize any template arguments", type);
3378
3379   /* [temp.class.spec]
3380
3381      A partially specialized non-type argument expression shall not
3382      involve template parameters of the partial specialization except
3383      when the argument expression is a simple identifier.
3384
3385      The type of a template parameter corresponding to a specialized
3386      non-type argument shall not be dependent on a parameter of the
3387      specialization. 
3388
3389      Also, we verify that pack expansions only occur at the
3390      end of the argument list.  */
3391   gcc_assert (nargs == DECL_NTPARMS (maintmpl));
3392   tpd2.parms = 0;
3393   for (i = 0; i < nargs; ++i)
3394     {
3395       tree parm = TREE_VALUE (TREE_VEC_ELT (main_inner_parms, i));
3396       tree arg = TREE_VEC_ELT (inner_args, i);
3397       tree packed_args = NULL_TREE;
3398       int j, len = 1;
3399
3400       if (ARGUMENT_PACK_P (arg))
3401         {
3402           /* Extract the arguments from the argument pack. We'll be
3403              iterating over these in the following loop.  */
3404           packed_args = ARGUMENT_PACK_ARGS (arg);
3405           len = TREE_VEC_LENGTH (packed_args);
3406         }
3407
3408       for (j = 0; j < len; j++)
3409         {
3410           if (packed_args)
3411             /* Get the Jth argument in the parameter pack.  */
3412             arg = TREE_VEC_ELT (packed_args, j);
3413
3414           if (PACK_EXPANSION_P (arg))
3415             {
3416               /* Pack expansions must come at the end of the
3417                  argument list.  */
3418               if ((packed_args && j < len - 1)
3419                   || (!packed_args && i < nargs - 1))
3420                 {
3421                   if (TREE_CODE (arg) == EXPR_PACK_EXPANSION)
3422                     error ("parameter pack argument %qE must be at the end of the template argument list", arg);
3423                   else
3424                     error ("parameter pack argument %qT must be at the end of the template argument list", arg);
3425
3426                   if (packed_args)
3427                     TREE_VEC_ELT (packed_args, j) = error_mark_node;
3428                 }
3429             }
3430
3431           if (TREE_CODE (arg) == EXPR_PACK_EXPANSION)
3432             /* We only care about the pattern.  */
3433             arg = PACK_EXPANSION_PATTERN (arg);
3434
3435           if (/* These first two lines are the `non-type' bit.  */
3436               !TYPE_P (arg)
3437               && TREE_CODE (arg) != TEMPLATE_DECL
3438               /* This next line is the `argument expression is not just a
3439                  simple identifier' condition and also the `specialized
3440                  non-type argument' bit.  */
3441               && TREE_CODE (arg) != TEMPLATE_PARM_INDEX)
3442             {
3443               if ((!packed_args && tpd.arg_uses_template_parms[i])
3444                   || (packed_args && uses_template_parms (arg)))
3445                 error ("template argument %qE involves template parameter(s)",
3446                        arg);
3447               else 
3448                 {
3449                   /* Look at the corresponding template parameter,
3450                      marking which template parameters its type depends
3451                      upon.  */
3452                   tree type = TREE_TYPE (parm);
3453
3454                   if (!tpd2.parms)
3455                     {
3456                       /* We haven't yet initialized TPD2.  Do so now.  */
3457                       tpd2.arg_uses_template_parms 
3458                         = (int *) alloca (sizeof (int) * nargs);
3459                       /* The number of parameters here is the number in the
3460                          main template, which, as checked in the assertion
3461                          above, is NARGS.  */
3462                       tpd2.parms = (int *) alloca (sizeof (int) * nargs);
3463                       tpd2.level = 
3464                         TMPL_PARMS_DEPTH (DECL_TEMPLATE_PARMS (maintmpl));
3465                     }
3466
3467                   /* Mark the template parameters.  But this time, we're
3468                      looking for the template parameters of the main
3469                      template, not in the specialization.  */
3470                   tpd2.current_arg = i;
3471                   tpd2.arg_uses_template_parms[i] = 0;
3472                   memset (tpd2.parms, 0, sizeof (int) * nargs);
3473                   for_each_template_parm (type,
3474                                           &mark_template_parm,
3475                                           &tpd2,
3476                                           NULL,
3477                                           /*include_nondeduced_p=*/false);
3478
3479                   if (tpd2.arg_uses_template_parms [i])
3480                     {
3481                       /* The type depended on some template parameters.
3482                          If they are fully specialized in the
3483                          specialization, that's OK.  */
3484                       int j;
3485                       for (j = 0; j < nargs; ++j)
3486                         if (tpd2.parms[j] != 0
3487                             && tpd.arg_uses_template_parms [j])
3488                           {
3489                             error ("type %qT of template argument %qE depends "
3490                                    "on template parameter(s)", 
3491                                    type,
3492                                    arg);
3493                             break;
3494                           }
3495                     }
3496                 }
3497             }
3498         }
3499     }
3500
3501   if (retrieve_specialization (maintmpl, specargs,
3502                                /*class_specializations_p=*/true))
3503     /* We've already got this specialization.  */
3504     return decl;
3505
3506   DECL_TEMPLATE_SPECIALIZATIONS (maintmpl)
3507     = tree_cons (specargs, inner_parms,
3508                  DECL_TEMPLATE_SPECIALIZATIONS (maintmpl));
3509   TREE_TYPE (DECL_TEMPLATE_SPECIALIZATIONS (maintmpl)) = type;
3510   return decl;
3511 }
3512
3513 /* Check that a template declaration's use of default arguments and
3514    parameter packs is not invalid.  Here, PARMS are the template
3515    parameters.  IS_PRIMARY is nonzero if DECL is the thing declared by
3516    a primary template.  IS_PARTIAL is nonzero if DECL is a partial
3517    specialization.
3518    
3519
3520    IS_FRIEND_DECL is nonzero if DECL is a friend function template
3521    declaration (but not a definition); 1 indicates a declaration, 2
3522    indicates a redeclaration. When IS_FRIEND_DECL=2, no errors are
3523    emitted for extraneous default arguments.
3524
3525    Returns TRUE if there were no errors found, FALSE otherwise. */
3526
3527 bool
3528 check_default_tmpl_args (tree decl, tree parms, int is_primary, 
3529                          int is_partial, int is_friend_decl)
3530 {
3531   const char *msg;
3532   int last_level_to_check;
3533   tree parm_level;
3534   bool no_errors = true;
3535
3536   /* [temp.param]
3537
3538      A default template-argument shall not be specified in a
3539      function template declaration or a function template definition, nor
3540      in the template-parameter-list of the definition of a member of a
3541      class template.  */
3542
3543   if (TREE_CODE (CP_DECL_CONTEXT (decl)) == FUNCTION_DECL)
3544     /* You can't have a function template declaration in a local
3545        scope, nor you can you define a member of a class template in a
3546        local scope.  */
3547     return true;
3548
3549   if (current_class_type
3550       && !TYPE_BEING_DEFINED (current_class_type)
3551       && DECL_LANG_SPECIFIC (decl)
3552       /* If this is either a friend defined in the scope of the class
3553          or a member function.  */
3554       && (DECL_FUNCTION_MEMBER_P (decl)
3555           ? same_type_p (DECL_CONTEXT (decl), current_class_type)
3556           : DECL_FRIEND_CONTEXT (decl)
3557           ? same_type_p (DECL_FRIEND_CONTEXT (decl), current_class_type)
3558           : false)
3559       /* And, if it was a member function, it really was defined in
3560          the scope of the class.  */
3561       && (!DECL_FUNCTION_MEMBER_P (decl)
3562           || DECL_INITIALIZED_IN_CLASS_P (decl)))
3563     /* We already checked these parameters when the template was
3564        declared, so there's no need to do it again now.  This function
3565        was defined in class scope, but we're processing it's body now
3566        that the class is complete.  */
3567     return true;
3568
3569   /* Core issue 226 (C++0x only): the following only applies to class
3570      templates.  */
3571   if ((cxx_dialect == cxx98) || TREE_CODE (decl) != FUNCTION_DECL)
3572     {
3573       /* [temp.param]
3574
3575          If a template-parameter has a default template-argument, all
3576          subsequent template-parameters shall have a default
3577          template-argument supplied.  */
3578       for (parm_level = parms; parm_level; parm_level = TREE_CHAIN (parm_level))
3579         {
3580           tree inner_parms = TREE_VALUE (parm_level);
3581           int ntparms = TREE_VEC_LENGTH (inner_parms);
3582           int seen_def_arg_p = 0;
3583           int i;
3584
3585           for (i = 0; i < ntparms; ++i)
3586             {
3587               tree parm = TREE_VEC_ELT (inner_parms, i);
3588
3589               if (parm == error_mark_node)
3590                 continue;
3591
3592               if (TREE_PURPOSE (parm))
3593                 seen_def_arg_p = 1;
3594               else if (seen_def_arg_p
3595                        && !template_parameter_pack_p (TREE_VALUE (parm)))
3596                 {
3597                   error ("no default argument for %qD", TREE_VALUE (parm));
3598                   /* For better subsequent error-recovery, we indicate that
3599                      there should have been a default argument.  */
3600                   TREE_PURPOSE (parm) = error_mark_node;
3601                   no_errors = false;
3602                 }
3603               else if (is_primary
3604                        && !is_partial
3605                        && !is_friend_decl
3606                        /* Don't complain about an enclosing partial
3607                           specialization.  */
3608                        && parm_level == parms
3609                        && TREE_CODE (decl) == TYPE_DECL
3610                        && i < ntparms - 1
3611                        && template_parameter_pack_p (TREE_VALUE (parm)))
3612                 {
3613                   /* A primary class template can only have one
3614                      parameter pack, at the end of the template
3615                      parameter list.  */
3616
3617                   if (TREE_CODE (TREE_VALUE (parm)) == PARM_DECL)
3618                     error ("parameter pack %qE must be at the end of the"
3619                            " template parameter list", TREE_VALUE (parm));
3620                   else
3621                     error ("parameter pack %qT must be at the end of the"
3622                            " template parameter list", 
3623                            TREE_TYPE (TREE_VALUE (parm)));
3624
3625                   TREE_VALUE (TREE_VEC_ELT (inner_parms, i)) 
3626                     = error_mark_node;
3627                   no_errors = false;
3628                 }
3629             }
3630         }
3631     }
3632
3633   if (((cxx_dialect == cxx98) && TREE_CODE (decl) != TYPE_DECL)
3634       || is_partial 
3635       || !is_primary
3636       || is_friend_decl)
3637     /* For an ordinary class template, default template arguments are
3638        allowed at the innermost level, e.g.:
3639          template <class T = int>
3640          struct S {};
3641        but, in a partial specialization, they're not allowed even
3642        there, as we have in [temp.class.spec]:
3643
3644          The template parameter list of a specialization shall not
3645          contain default template argument values.
3646
3647        So, for a partial specialization, or for a function template
3648        (in C++98/C++03), we look at all of them.  */
3649     ;
3650   else
3651     /* But, for a primary class template that is not a partial
3652        specialization we look at all template parameters except the
3653        innermost ones.  */
3654     parms = TREE_CHAIN (parms);
3655
3656   /* Figure out what error message to issue.  */
3657   if (is_friend_decl == 2)
3658     msg = "default template arguments may not be used in function template friend re-declaration";
3659   else if (is_friend_decl)
3660     msg = "default template arguments may not be used in function template friend declarations";
3661   else if (TREE_CODE (decl) == FUNCTION_DECL && (cxx_dialect == cxx98))
3662     msg = "default template arguments may not be used in function templates";
3663   else if (is_partial)
3664     msg = "default template arguments may not be used in partial specializations";
3665   else
3666     msg = "default argument for template parameter for class enclosing %qD";
3667
3668   if (current_class_type && TYPE_BEING_DEFINED (current_class_type))
3669     /* If we're inside a class definition, there's no need to
3670        examine the parameters to the class itself.  On the one
3671        hand, they will be checked when the class is defined, and,
3672        on the other, default arguments are valid in things like:
3673          template <class T = double>
3674          struct S { template <class U> void f(U); };
3675        Here the default argument for `S' has no bearing on the
3676        declaration of `f'.  */
3677     last_level_to_check = template_class_depth (current_class_type) + 1;
3678   else
3679     /* Check everything.  */
3680     last_level_to_check = 0;
3681
3682   for (parm_level = parms;
3683        parm_level && TMPL_PARMS_DEPTH (parm_level) >= last_level_to_check;
3684        parm_level = TREE_CHAIN (parm_level))
3685     {
3686       tree inner_parms = TREE_VALUE (parm_level);
3687       int i;
3688       int ntparms;
3689
3690       ntparms = TREE_VEC_LENGTH (inner_parms);
3691       for (i = 0; i < ntparms; ++i)
3692         {
3693           if (TREE_VEC_ELT (inner_parms, i) == error_mark_node)
3694             continue;
3695
3696           if (TREE_PURPOSE (TREE_VEC_ELT (inner_parms, i)))
3697             {
3698               if (msg)
3699                 {
3700                   no_errors = false;
3701                   if (is_friend_decl == 2)
3702                     return no_errors;
3703
3704                   error (msg, decl);
3705                   msg = 0;
3706                 }
3707
3708               /* Clear out the default argument so that we are not
3709                  confused later.  */
3710               TREE_PURPOSE (TREE_VEC_ELT (inner_parms, i)) = NULL_TREE;
3711             }
3712         }
3713
3714       /* At this point, if we're still interested in issuing messages,
3715          they must apply to classes surrounding the object declared.  */
3716       if (msg)
3717         msg = "default argument for template parameter for class enclosing %qD";
3718     }
3719
3720   return no_errors;
3721 }
3722
3723 /* Worker for push_template_decl_real, called via
3724    for_each_template_parm.  DATA is really an int, indicating the
3725    level of the parameters we are interested in.  If T is a template
3726    parameter of that level, return nonzero.  */
3727
3728 static int
3729 template_parm_this_level_p (tree t, void* data)
3730 {
3731   int this_level = *(int *)data;
3732   int level;
3733
3734   if (TREE_CODE (t) == TEMPLATE_PARM_INDEX)
3735     level = TEMPLATE_PARM_LEVEL (t);
3736   else
3737     level = TEMPLATE_TYPE_LEVEL (t);
3738   return level == this_level;
3739 }
3740
3741 /* Creates a TEMPLATE_DECL for the indicated DECL using the template
3742    parameters given by current_template_args, or reuses a
3743    previously existing one, if appropriate.  Returns the DECL, or an
3744    equivalent one, if it is replaced via a call to duplicate_decls.
3745
3746    If IS_FRIEND is true, DECL is a friend declaration.  */
3747
3748 tree
3749 push_template_decl_real (tree decl, bool is_friend)
3750 {
3751   tree tmpl;
3752   tree args;
3753   tree info;
3754   tree ctx;
3755   int primary;
3756   int is_partial;
3757   int new_template_p = 0;
3758   /* True if the template is a member template, in the sense of
3759      [temp.mem].  */
3760   bool member_template_p = false;
3761
3762   if (decl == error_mark_node || !current_template_parms)
3763     return error_mark_node;
3764
3765   /* See if this is a partial specialization.  */
3766   is_partial = (DECL_IMPLICIT_TYPEDEF_P (decl)
3767                 && TREE_CODE (TREE_TYPE (decl)) != ENUMERAL_TYPE
3768                 && CLASSTYPE_TEMPLATE_SPECIALIZATION (TREE_TYPE (decl)));
3769
3770   if (TREE_CODE (decl) == FUNCTION_DECL && DECL_FRIEND_P (decl))
3771     is_friend = true;
3772
3773   if (is_friend)
3774     /* For a friend, we want the context of the friend function, not
3775        the type of which it is a friend.  */
3776     ctx = DECL_CONTEXT (decl);
3777   else if (CP_DECL_CONTEXT (decl)
3778            && TREE_CODE (CP_DECL_CONTEXT (decl)) != NAMESPACE_DECL)
3779     /* In the case of a virtual function, we want the class in which
3780        it is defined.  */
3781     ctx = CP_DECL_CONTEXT (decl);
3782   else
3783     /* Otherwise, if we're currently defining some class, the DECL
3784        is assumed to be a member of the class.  */
3785     ctx = current_scope ();
3786
3787   if (ctx && TREE_CODE (ctx) == NAMESPACE_DECL)
3788     ctx = NULL_TREE;
3789
3790   if (!DECL_CONTEXT (decl))
3791     DECL_CONTEXT (decl) = FROB_CONTEXT (current_namespace);
3792
3793   /* See if this is a primary template.  */
3794   if (is_friend && ctx)
3795     /* A friend template that specifies a class context, i.e.
3796          template <typename T> friend void A<T>::f();
3797        is not primary.  */
3798     primary = 0;
3799   else
3800     primary = template_parm_scope_p ();
3801
3802   if (primary)
3803     {
3804       if (DECL_CLASS_SCOPE_P (decl))
3805         member_template_p = true;
3806       if (TREE_CODE (decl) == TYPE_DECL
3807           && ANON_AGGRNAME_P (DECL_NAME (decl)))
3808         {
3809           error ("template class without a name");
3810           return error_mark_node;
3811         }
3812       else if (TREE_CODE (decl) == FUNCTION_DECL)
3813         {
3814           if (DECL_DESTRUCTOR_P (decl))
3815             {
3816               /* [temp.mem]
3817
3818                  A destructor shall not be a member template.  */
3819               error ("destructor %qD declared as member template", decl);
3820               return error_mark_node;
3821             }
3822           if (NEW_DELETE_OPNAME_P (DECL_NAME (decl))
3823               && (!TYPE_ARG_TYPES (TREE_TYPE (decl))
3824                   || TYPE_ARG_TYPES (TREE_TYPE (decl)) == void_list_node
3825                   || !TREE_CHAIN (TYPE_ARG_TYPES (TREE_TYPE (decl)))
3826                   || (TREE_CHAIN (TYPE_ARG_TYPES ((TREE_TYPE (decl))))
3827                       == void_list_node)))
3828             {
3829               /* [basic.stc.dynamic.allocation]
3830
3831                  An allocation function can be a function
3832                  template. ... Template allocation functions shall
3833                  have two or more parameters.  */
3834               error ("invalid template declaration of %qD", decl);
3835               return error_mark_node;
3836             }
3837         }
3838       else if (DECL_IMPLICIT_TYPEDEF_P (decl)
3839                && CLASS_TYPE_P (TREE_TYPE (decl)))
3840         /* OK */;
3841       else
3842         {
3843           error ("template declaration of %q#D", decl);
3844           return error_mark_node;
3845         }
3846     }
3847
3848   /* Check to see that the rules regarding the use of default
3849      arguments are not being violated.  */
3850   check_default_tmpl_args (decl, current_template_parms,
3851                            primary, is_partial, /*is_friend_decl=*/0);
3852
3853   /* Ensure that there are no parameter packs in the type of this
3854      declaration that have not been expanded.  */
3855   if (TREE_CODE (decl) == FUNCTION_DECL)
3856     {
3857       /* Check each of the arguments individually to see if there are
3858          any bare parameter packs.  */
3859       tree type = TREE_TYPE (decl);
3860       tree arg = DECL_ARGUMENTS (decl);
3861       tree argtype = TYPE_ARG_TYPES (type);
3862
3863       while (arg && argtype)
3864         {
3865           if (!FUNCTION_PARAMETER_PACK_P (arg)
3866               && check_for_bare_parameter_packs (TREE_TYPE (arg)))
3867             {
3868             /* This is a PARM_DECL that contains unexpanded parameter
3869                packs. We have already complained about this in the
3870                check_for_bare_parameter_packs call, so just replace
3871                these types with ERROR_MARK_NODE.  */
3872               TREE_TYPE (arg) = error_mark_node;
3873               TREE_VALUE (argtype) = error_mark_node;
3874             }
3875
3876           arg = TREE_CHAIN (arg);
3877           argtype = TREE_CHAIN (argtype);
3878         }
3879
3880       /* Check for bare parameter packs in the return type and the
3881          exception specifiers.  */
3882       if (check_for_bare_parameter_packs (TREE_TYPE (type)))
3883         /* Errors were already issued, set return type to int
3884            as the frontend doesn't expect error_mark_node as
3885            the return type.  */
3886         TREE_TYPE (type) = integer_type_node;
3887       if (check_for_bare_parameter_packs (TYPE_RAISES_EXCEPTIONS (type)))
3888         TYPE_RAISES_EXCEPTIONS (type) = NULL_TREE;
3889     }
3890   else if (check_for_bare_parameter_packs (TREE_TYPE (decl)))
3891     {
3892       TREE_TYPE (decl) = error_mark_node;
3893       return error_mark_node;
3894     }
3895
3896   if (is_partial)
3897     return process_partial_specialization (decl);
3898
3899   args = current_template_args ();
3900
3901   if (!ctx
3902       || TREE_CODE (ctx) == FUNCTION_DECL
3903       || (CLASS_TYPE_P (ctx) && TYPE_BEING_DEFINED (ctx))
3904       || (is_friend && !DECL_TEMPLATE_INFO (decl)))
3905     {
3906       if (DECL_LANG_SPECIFIC (decl)
3907           && DECL_TEMPLATE_INFO (decl)
3908           && DECL_TI_TEMPLATE (decl))
3909         tmpl = DECL_TI_TEMPLATE (decl);
3910       /* If DECL is a TYPE_DECL for a class-template, then there won't
3911          be DECL_LANG_SPECIFIC.  The information equivalent to
3912          DECL_TEMPLATE_INFO is found in TYPE_TEMPLATE_INFO instead.  */
3913       else if (DECL_IMPLICIT_TYPEDEF_P (decl)
3914                && TYPE_TEMPLATE_INFO (TREE_TYPE (decl))
3915                && TYPE_TI_TEMPLATE (TREE_TYPE (decl)))
3916         {
3917           /* Since a template declaration already existed for this
3918              class-type, we must be redeclaring it here.  Make sure
3919              that the redeclaration is valid.  */
3920           redeclare_class_template (TREE_TYPE (decl),
3921                                     current_template_parms);
3922           /* We don't need to create a new TEMPLATE_DECL; just use the
3923              one we already had.  */
3924           tmpl = TYPE_TI_TEMPLATE (TREE_TYPE (decl));
3925         }
3926       else
3927         {
3928           tmpl = build_template_decl (decl, current_template_parms,
3929                                       member_template_p);
3930           new_template_p = 1;
3931
3932           if (DECL_LANG_SPECIFIC (decl)
3933               && DECL_TEMPLATE_SPECIALIZATION (decl))
3934             {
3935               /* A specialization of a member template of a template
3936                  class.  */
3937               SET_DECL_TEMPLATE_SPECIALIZATION (tmpl);
3938               DECL_TEMPLATE_INFO (tmpl) = DECL_TEMPLATE_INFO (decl);
3939               DECL_TEMPLATE_INFO (decl) = NULL_TREE;
3940             }
3941         }
3942     }
3943   else
3944     {
3945       tree a, t, current, parms;
3946       int i;
3947       tree tinfo = get_template_info (decl);
3948
3949       if (!tinfo)
3950         {
3951           error ("template definition of non-template %q#D", decl);
3952           return error_mark_node;
3953         }
3954
3955       tmpl = TI_TEMPLATE (tinfo);
3956
3957       if (DECL_FUNCTION_TEMPLATE_P (tmpl)
3958           && DECL_TEMPLATE_INFO (decl) && DECL_TI_ARGS (decl)
3959           && DECL_TEMPLATE_SPECIALIZATION (decl)
3960           && DECL_MEMBER_TEMPLATE_P (tmpl))
3961         {
3962           tree new_tmpl;
3963
3964           /* The declaration is a specialization of a member
3965              template, declared outside the class.  Therefore, the
3966              innermost template arguments will be NULL, so we
3967              replace them with the arguments determined by the
3968              earlier call to check_explicit_specialization.  */
3969           args = DECL_TI_ARGS (decl);
3970
3971           new_tmpl
3972             = build_template_decl (decl, current_template_parms,
3973                                    member_template_p);
3974           DECL_TEMPLATE_RESULT (new_tmpl) = decl;
3975           TREE_TYPE (new_tmpl) = TREE_TYPE (decl);
3976           DECL_TI_TEMPLATE (decl) = new_tmpl;
3977           SET_DECL_TEMPLATE_SPECIALIZATION (new_tmpl);
3978           DECL_TEMPLATE_INFO (new_tmpl)
3979             = tree_cons (tmpl, args, NULL_TREE);
3980
3981           register_specialization (new_tmpl,
3982                                    most_general_template (tmpl),
3983                                    args,
3984                                    is_friend);
3985           return decl;
3986         }
3987
3988       /* Make sure the template headers we got make sense.  */
3989
3990       parms = DECL_TEMPLATE_PARMS (tmpl);
3991       i = TMPL_PARMS_DEPTH (parms);
3992       if (TMPL_ARGS_DEPTH (args) != i)
3993         {
3994           error ("expected %d levels of template parms for %q#D, got %d",
3995                  i, decl, TMPL_ARGS_DEPTH (args));
3996         }
3997       else
3998         for (current = decl; i > 0; --i, parms = TREE_CHAIN (parms))
3999           {
4000             a = TMPL_ARGS_LEVEL (args, i);
4001             t = INNERMOST_TEMPLATE_PARMS (parms);
4002
4003             if (TREE_VEC_LENGTH (t) != TREE_VEC_LENGTH (a))
4004               {
4005                 if (current == decl)
4006                   error ("got %d template parameters for %q#D",
4007                          TREE_VEC_LENGTH (a), decl);
4008                 else
4009                   error ("got %d template parameters for %q#T",
4010                          TREE_VEC_LENGTH (a), current);
4011                 error ("  but %d required", TREE_VEC_LENGTH (t));
4012                 return error_mark_node;
4013               }
4014
4015             if (current == decl)
4016               current = ctx;
4017             else
4018               current = (TYPE_P (current)
4019                          ? TYPE_CONTEXT (current)
4020                          : DECL_CONTEXT (current));
4021           }
4022
4023       /* Check that the parms are used in the appropriate qualifying scopes
4024          in the declarator.  */
4025       if (!comp_template_args
4026           (TI_ARGS (tinfo),
4027            TI_ARGS (get_template_info (DECL_TEMPLATE_RESULT (tmpl)))))
4028         {
4029           error ("\
4030 template arguments to %qD do not match original template %qD",
4031                  decl, DECL_TEMPLATE_RESULT (tmpl));
4032           if (!uses_template_parms (TI_ARGS (tinfo)))
4033             inform (input_location, "use template<> for an explicit specialization");
4034           /* Avoid crash in import_export_decl.  */
4035           DECL_INTERFACE_KNOWN (decl) = 1;
4036           return error_mark_node;
4037         }
4038     }
4039
4040   DECL_TEMPLATE_RESULT (tmpl) = decl;
4041   TREE_TYPE (tmpl) = TREE_TYPE (decl);
4042
4043   /* Push template declarations for global functions and types.  Note
4044      that we do not try to push a global template friend declared in a
4045      template class; such a thing may well depend on the template
4046      parameters of the class.  */
4047   if (new_template_p && !ctx
4048       && !(is_friend && template_class_depth (current_class_type) > 0))
4049     {
4050       tmpl = pushdecl_namespace_level (tmpl, is_friend);
4051       if (tmpl == error_mark_node)
4052         return error_mark_node;
4053
4054       /* Hide template friend classes that haven't been declared yet.  */
4055       if (is_friend && TREE_CODE (decl) == TYPE_DECL)
4056         {
4057           DECL_ANTICIPATED (tmpl) = 1;
4058           DECL_FRIEND_P (tmpl) = 1;
4059         }
4060     }
4061
4062   if (primary)
4063     {
4064       tree parms = DECL_TEMPLATE_PARMS (tmpl);
4065       int i;
4066
4067       DECL_PRIMARY_TEMPLATE (tmpl) = tmpl;
4068       if (DECL_CONV_FN_P (tmpl))
4069         {
4070           int depth = TMPL_PARMS_DEPTH (parms);
4071
4072           /* It is a conversion operator. See if the type converted to
4073              depends on innermost template operands.  */
4074
4075           if (uses_template_parms_level (TREE_TYPE (TREE_TYPE (tmpl)),
4076                                          depth))
4077             DECL_TEMPLATE_CONV_FN_P (tmpl) = 1;
4078         }
4079
4080       /* Give template template parms a DECL_CONTEXT of the template
4081          for which they are a parameter.  */
4082       parms = INNERMOST_TEMPLATE_PARMS (parms);
4083       for (i = TREE_VEC_LENGTH (parms) - 1; i >= 0; --i)
4084         {
4085           tree parm = TREE_VALUE (TREE_VEC_ELT (parms, i));
4086           if (TREE_CODE (parm) == TEMPLATE_DECL)
4087             DECL_CONTEXT (parm) = tmpl;
4088         }
4089     }
4090
4091   /* The DECL_TI_ARGS of DECL contains full set of arguments referring
4092      back to its most general template.  If TMPL is a specialization,
4093      ARGS may only have the innermost set of arguments.  Add the missing
4094      argument levels if necessary.  */
4095   if (DECL_TEMPLATE_INFO (tmpl))
4096     args = add_outermost_template_args (DECL_TI_ARGS (tmpl), args);
4097
4098   info = tree_cons (tmpl, args, NULL_TREE);
4099
4100   if (DECL_IMPLICIT_TYPEDEF_P (decl))
4101     SET_TYPE_TEMPLATE_INFO (TREE_TYPE (tmpl), info);
4102   else if (DECL_LANG_SPECIFIC (decl))
4103     DECL_TEMPLATE_INFO (decl) = info;
4104
4105   return DECL_TEMPLATE_RESULT (tmpl);
4106 }
4107
4108 tree
4109 push_template_decl (tree decl)