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