OSDN Git Service

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