Merge branch 'vendor/GCC44'
[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 (arg == NULL_TREE)
2784         return args;
2785       if (ARGUMENT_PACK_P (arg))
2786         {
2787           int num_packed = TREE_VEC_LENGTH (ARGUMENT_PACK_ARGS (arg));
2788           if (num_result_args < 0)
2789             num_result_args = in_arg + num_packed;
2790           else
2791             num_result_args += num_packed;
2792         }
2793       else
2794         {
2795           if (num_result_args >= 0)
2796             num_result_args++;
2797         }
2798     }
2799
2800   /* If no expansion is necessary, we're done.  */
2801   if (num_result_args < 0)
2802     return args;
2803
2804   /* Expand arguments.  */
2805   result_args = make_tree_vec (num_result_args);
2806   for (in_arg = 0; in_arg < nargs; ++in_arg)
2807     {
2808       tree arg = TREE_VEC_ELT (args, in_arg);
2809       if (ARGUMENT_PACK_P (arg))
2810         {
2811           tree packed = ARGUMENT_PACK_ARGS (arg);
2812           int i, num_packed = TREE_VEC_LENGTH (packed);
2813           for (i = 0; i < num_packed; ++i, ++out_arg)
2814             TREE_VEC_ELT (result_args, out_arg) = TREE_VEC_ELT(packed, i);
2815         }
2816       else
2817         {
2818           TREE_VEC_ELT (result_args, out_arg) = arg;
2819           ++out_arg;
2820         }
2821     }
2822
2823   return result_args;
2824 }
2825
2826 /* Checks if DECL shadows a template parameter.
2827
2828    [temp.local]: A template-parameter shall not be redeclared within its
2829    scope (including nested scopes).
2830
2831    Emits an error and returns TRUE if the DECL shadows a parameter,
2832    returns FALSE otherwise.  */
2833
2834 bool
2835 check_template_shadow (tree decl)
2836 {
2837   tree olddecl;
2838
2839   /* If we're not in a template, we can't possibly shadow a template
2840      parameter.  */
2841   if (!current_template_parms)
2842     return true;
2843
2844   /* Figure out what we're shadowing.  */
2845   if (TREE_CODE (decl) == OVERLOAD)
2846     decl = OVL_CURRENT (decl);
2847   olddecl = innermost_non_namespace_value (DECL_NAME (decl));
2848
2849   /* If there's no previous binding for this name, we're not shadowing
2850      anything, let alone a template parameter.  */
2851   if (!olddecl)
2852     return true;
2853
2854   /* If we're not shadowing a template parameter, we're done.  Note
2855      that OLDDECL might be an OVERLOAD (or perhaps even an
2856      ERROR_MARK), so we can't just blithely assume it to be a _DECL
2857      node.  */
2858   if (!DECL_P (olddecl) || !DECL_TEMPLATE_PARM_P (olddecl))
2859     return true;
2860
2861   /* We check for decl != olddecl to avoid bogus errors for using a
2862      name inside a class.  We check TPFI to avoid duplicate errors for
2863      inline member templates.  */
2864   if (decl == olddecl
2865       || TEMPLATE_PARMS_FOR_INLINE (current_template_parms))
2866     return true;
2867
2868   error ("declaration of %q+#D", decl);
2869   error (" shadows template parm %q+#D", olddecl);
2870   return false;
2871 }
2872
2873 /* Return a new TEMPLATE_PARM_INDEX with the indicated INDEX, LEVEL,
2874    ORIG_LEVEL, DECL, and TYPE.  */
2875
2876 static tree
2877 build_template_parm_index (int index,
2878                            int level,
2879                            int orig_level,
2880                            tree decl,
2881                            tree type)
2882 {
2883   tree t = make_node (TEMPLATE_PARM_INDEX);
2884   TEMPLATE_PARM_IDX (t) = index;
2885   TEMPLATE_PARM_LEVEL (t) = level;
2886   TEMPLATE_PARM_ORIG_LEVEL (t) = orig_level;
2887   TEMPLATE_PARM_DECL (t) = decl;
2888   TREE_TYPE (t) = type;
2889   TREE_CONSTANT (t) = TREE_CONSTANT (decl);
2890   TREE_READONLY (t) = TREE_READONLY (decl);
2891
2892   return t;
2893 }
2894
2895 /* Find the canonical type parameter for the given template type
2896    parameter.  Returns the canonical type parameter, which may be TYPE
2897    if no such parameter existed.  */
2898 static tree
2899 canonical_type_parameter (tree type)
2900 {
2901   tree list;
2902   int idx = TEMPLATE_TYPE_IDX (type);
2903   if (!canonical_template_parms)
2904     canonical_template_parms = VEC_alloc (tree, gc, idx+1);
2905
2906   while (VEC_length (tree, canonical_template_parms) <= (unsigned)idx)
2907     VEC_safe_push (tree, gc, canonical_template_parms, NULL_TREE);
2908
2909   list = VEC_index (tree, canonical_template_parms, idx);
2910   while (list && !comptypes (type, TREE_VALUE (list), COMPARE_STRUCTURAL))
2911     list = TREE_CHAIN (list);
2912
2913   if (list)
2914     return TREE_VALUE (list);
2915   else
2916     {
2917       VEC_replace(tree, canonical_template_parms, idx,
2918                   tree_cons (NULL_TREE, type, 
2919                              VEC_index (tree, canonical_template_parms, idx)));
2920       return type;
2921     }
2922 }
2923
2924 /* Return a TEMPLATE_PARM_INDEX, similar to INDEX, but whose
2925    TEMPLATE_PARM_LEVEL has been decreased by LEVELS.  If such a
2926    TEMPLATE_PARM_INDEX already exists, it is returned; otherwise, a
2927    new one is created.  */
2928
2929 static tree
2930 reduce_template_parm_level (tree index, tree type, int levels, tree args,
2931                             tsubst_flags_t complain)
2932 {
2933   if (TEMPLATE_PARM_DESCENDANTS (index) == NULL_TREE
2934       || (TEMPLATE_PARM_LEVEL (TEMPLATE_PARM_DESCENDANTS (index))
2935           != TEMPLATE_PARM_LEVEL (index) - levels))
2936     {
2937       tree orig_decl = TEMPLATE_PARM_DECL (index);
2938       tree decl, t;
2939
2940       decl = build_decl (TREE_CODE (orig_decl), DECL_NAME (orig_decl), type);
2941       TREE_CONSTANT (decl) = TREE_CONSTANT (orig_decl);
2942       TREE_READONLY (decl) = TREE_READONLY (orig_decl);
2943       DECL_ARTIFICIAL (decl) = 1;
2944       SET_DECL_TEMPLATE_PARM_P (decl);
2945
2946       t = build_template_parm_index (TEMPLATE_PARM_IDX (index),
2947                                      TEMPLATE_PARM_LEVEL (index) - levels,
2948                                      TEMPLATE_PARM_ORIG_LEVEL (index),
2949                                      decl, type);
2950       TEMPLATE_PARM_DESCENDANTS (index) = t;
2951       TEMPLATE_PARM_PARAMETER_PACK (t) 
2952         = TEMPLATE_PARM_PARAMETER_PACK (index);
2953
2954         /* Template template parameters need this.  */
2955       if (TREE_CODE (decl) == TEMPLATE_DECL)
2956         DECL_TEMPLATE_PARMS (decl) = tsubst_template_parms
2957           (DECL_TEMPLATE_PARMS (TEMPLATE_PARM_DECL (index)),
2958            args, complain);
2959     }
2960
2961   return TEMPLATE_PARM_DESCENDANTS (index);
2962 }
2963
2964 /* Process information from new template parameter PARM and append it to the
2965    LIST being built.  This new parameter is a non-type parameter iff
2966    IS_NON_TYPE is true. This new parameter is a parameter
2967    pack iff IS_PARAMETER_PACK is true.  */
2968
2969 tree
2970 process_template_parm (tree list, tree parm, bool is_non_type, 
2971                        bool is_parameter_pack)
2972 {
2973   tree decl = 0;
2974   tree defval;
2975   tree err_parm_list;
2976   int idx = 0;
2977
2978   gcc_assert (TREE_CODE (parm) == TREE_LIST);
2979   defval = TREE_PURPOSE (parm);
2980
2981   if (list)
2982     {
2983       tree p = tree_last (list);
2984
2985       if (p && TREE_VALUE (p) != error_mark_node)
2986         {
2987           p = TREE_VALUE (p);
2988           if (TREE_CODE (p) == TYPE_DECL || TREE_CODE (p) == TEMPLATE_DECL)
2989             idx = TEMPLATE_TYPE_IDX (TREE_TYPE (p));
2990           else
2991             idx = TEMPLATE_PARM_IDX (DECL_INITIAL (p));
2992         }
2993
2994       ++idx;
2995     }
2996   else
2997     idx = 0;
2998
2999   if (is_non_type)
3000     {
3001       parm = TREE_VALUE (parm);
3002
3003       SET_DECL_TEMPLATE_PARM_P (parm);
3004
3005       if (TREE_TYPE (parm) == error_mark_node)
3006         {
3007           err_parm_list = build_tree_list (defval, parm);
3008           TREE_VALUE (err_parm_list) = error_mark_node;
3009            return chainon (list, err_parm_list);
3010         }
3011       else
3012       {
3013         /* [temp.param]
3014
3015            The top-level cv-qualifiers on the template-parameter are
3016            ignored when determining its type.  */
3017         TREE_TYPE (parm) = TYPE_MAIN_VARIANT (TREE_TYPE (parm));
3018         if (invalid_nontype_parm_type_p (TREE_TYPE (parm), 1))
3019           {
3020             err_parm_list = build_tree_list (defval, parm);
3021             TREE_VALUE (err_parm_list) = error_mark_node;
3022              return chainon (list, err_parm_list);
3023           }
3024
3025         if (uses_parameter_packs (TREE_TYPE (parm)) && !is_parameter_pack)
3026           {
3027             /* This template parameter is not a parameter pack, but it
3028                should be. Complain about "bare" parameter packs.  */
3029             check_for_bare_parameter_packs (TREE_TYPE (parm));
3030             
3031             /* Recover by calling this a parameter pack.  */
3032             is_parameter_pack = true;
3033           }
3034       }
3035
3036       /* A template parameter is not modifiable.  */
3037       TREE_CONSTANT (parm) = 1;
3038       TREE_READONLY (parm) = 1;
3039       decl = build_decl (CONST_DECL, DECL_NAME (parm), TREE_TYPE (parm));
3040       TREE_CONSTANT (decl) = 1;
3041       TREE_READONLY (decl) = 1;
3042       DECL_INITIAL (parm) = DECL_INITIAL (decl)
3043         = build_template_parm_index (idx, processing_template_decl,
3044                                      processing_template_decl,
3045                                      decl, TREE_TYPE (parm));
3046
3047       TEMPLATE_PARM_PARAMETER_PACK (DECL_INITIAL (parm)) 
3048         = is_parameter_pack;
3049     }
3050   else
3051     {
3052       tree t;
3053       parm = TREE_VALUE (TREE_VALUE (parm));
3054
3055       if (parm && TREE_CODE (parm) == TEMPLATE_DECL)
3056         {
3057           t = cxx_make_type (TEMPLATE_TEMPLATE_PARM);
3058           /* This is for distinguishing between real templates and template
3059              template parameters */
3060           TREE_TYPE (parm) = t;
3061           TREE_TYPE (DECL_TEMPLATE_RESULT (parm)) = t;
3062           decl = parm;
3063         }
3064       else
3065         {
3066           t = cxx_make_type (TEMPLATE_TYPE_PARM);
3067           /* parm is either IDENTIFIER_NODE or NULL_TREE.  */
3068           decl = build_decl (TYPE_DECL, parm, t);
3069         }
3070
3071       TYPE_NAME (t) = decl;
3072       TYPE_STUB_DECL (t) = decl;
3073       parm = decl;
3074       TEMPLATE_TYPE_PARM_INDEX (t)
3075         = build_template_parm_index (idx, processing_template_decl,
3076                                      processing_template_decl,
3077                                      decl, TREE_TYPE (parm));
3078       TEMPLATE_TYPE_PARAMETER_PACK (t) = is_parameter_pack;
3079       TYPE_CANONICAL (t) = canonical_type_parameter (t);
3080     }
3081   DECL_ARTIFICIAL (decl) = 1;
3082   SET_DECL_TEMPLATE_PARM_P (decl);
3083   pushdecl (decl);
3084   parm = build_tree_list (defval, parm);
3085   return chainon (list, parm);
3086 }
3087
3088 /* The end of a template parameter list has been reached.  Process the
3089    tree list into a parameter vector, converting each parameter into a more
3090    useful form.  Type parameters are saved as IDENTIFIER_NODEs, and others
3091    as PARM_DECLs.  */
3092
3093 tree
3094 end_template_parm_list (tree parms)
3095 {
3096   int nparms;
3097   tree parm, next;
3098   tree saved_parmlist = make_tree_vec (list_length (parms));
3099
3100   current_template_parms
3101     = tree_cons (size_int (processing_template_decl),
3102                  saved_parmlist, current_template_parms);
3103
3104   for (parm = parms, nparms = 0; parm; parm = next, nparms++)
3105     {
3106       next = TREE_CHAIN (parm);
3107       TREE_VEC_ELT (saved_parmlist, nparms) = parm;
3108       TREE_CHAIN (parm) = NULL_TREE;
3109     }
3110
3111   --processing_template_parmlist;
3112
3113   return saved_parmlist;
3114 }
3115
3116 /* end_template_decl is called after a template declaration is seen.  */
3117
3118 void
3119 end_template_decl (void)
3120 {
3121   reset_specialization ();
3122
3123   if (! processing_template_decl)
3124     return;
3125
3126   /* This matches the pushlevel in begin_template_parm_list.  */
3127   finish_scope ();
3128
3129   --processing_template_decl;
3130   current_template_parms = TREE_CHAIN (current_template_parms);
3131 }
3132
3133 /* Within the declaration of a template, return all levels of template
3134    parameters that apply.  The template parameters are represented as
3135    a TREE_VEC, in the form documented in cp-tree.h for template
3136    arguments.  */
3137
3138 static tree
3139 current_template_args (void)
3140 {
3141   tree header;
3142   tree args = NULL_TREE;
3143   int length = TMPL_PARMS_DEPTH (current_template_parms);
3144   int l = length;
3145
3146   /* If there is only one level of template parameters, we do not
3147      create a TREE_VEC of TREE_VECs.  Instead, we return a single
3148      TREE_VEC containing the arguments.  */
3149   if (length > 1)
3150     args = make_tree_vec (length);
3151
3152   for (header = current_template_parms; header; header = TREE_CHAIN (header))
3153     {
3154       tree a = copy_node (TREE_VALUE (header));
3155       int i;
3156
3157       TREE_TYPE (a) = NULL_TREE;
3158       for (i = TREE_VEC_LENGTH (a) - 1; i >= 0; --i)
3159         {
3160           tree t = TREE_VEC_ELT (a, i);
3161
3162           /* T will be a list if we are called from within a
3163              begin/end_template_parm_list pair, but a vector directly
3164              if within a begin/end_member_template_processing pair.  */
3165           if (TREE_CODE (t) == TREE_LIST)
3166             {
3167               t = TREE_VALUE (t);
3168
3169               if (!error_operand_p (t))
3170                 {
3171                   if (TREE_CODE (t) == TYPE_DECL
3172                       || TREE_CODE (t) == TEMPLATE_DECL)
3173                     {
3174                       t = TREE_TYPE (t);
3175                       
3176                       if (TEMPLATE_TYPE_PARAMETER_PACK (t))
3177                         {
3178                           /* Turn this argument into a TYPE_ARGUMENT_PACK
3179                              with a single element, which expands T.  */
3180                           tree vec = make_tree_vec (1);
3181                           TREE_VEC_ELT (vec, 0) = make_pack_expansion (t);
3182                           
3183                           t = make_node (TYPE_ARGUMENT_PACK);
3184                           SET_ARGUMENT_PACK_ARGS (t, vec);
3185                         }
3186                     }
3187                   else
3188                     {
3189                       t = DECL_INITIAL (t);
3190                       
3191                       if (TEMPLATE_PARM_PARAMETER_PACK (t))
3192                         {
3193                           /* Turn this argument into a NONTYPE_ARGUMENT_PACK
3194                              with a single element, which expands T.  */
3195                           tree vec = make_tree_vec (1);
3196                           tree type = TREE_TYPE (TEMPLATE_PARM_DECL (t));
3197                           TREE_VEC_ELT (vec, 0) = make_pack_expansion (t);
3198                           
3199                           t  = make_node (NONTYPE_ARGUMENT_PACK);
3200                           SET_ARGUMENT_PACK_ARGS (t, vec);
3201                           TREE_TYPE (t) = type;
3202                         }
3203                     }
3204                   TREE_VEC_ELT (a, i) = t;
3205                 }
3206             }
3207         }
3208
3209       if (length > 1)
3210         TREE_VEC_ELT (args, --l) = a;
3211       else
3212         args = a;
3213     }
3214
3215   return args;
3216 }
3217
3218 /* Return a TEMPLATE_DECL corresponding to DECL, using the indicated
3219    template PARMS.  If MEMBER_TEMPLATE_P is true, the new template is
3220    a member template.  Used by push_template_decl below.  */
3221
3222 static tree
3223 build_template_decl (tree decl, tree parms, bool member_template_p)
3224 {
3225   tree tmpl = build_lang_decl (TEMPLATE_DECL, DECL_NAME (decl), NULL_TREE);
3226   DECL_TEMPLATE_PARMS (tmpl) = parms;
3227   DECL_CONTEXT (tmpl) = DECL_CONTEXT (decl);
3228   DECL_MEMBER_TEMPLATE_P (tmpl) = member_template_p;
3229   if (DECL_LANG_SPECIFIC (decl))
3230     {
3231       DECL_STATIC_FUNCTION_P (tmpl) = DECL_STATIC_FUNCTION_P (decl);
3232       DECL_CONSTRUCTOR_P (tmpl) = DECL_CONSTRUCTOR_P (decl);
3233       DECL_DESTRUCTOR_P (tmpl) = DECL_DESTRUCTOR_P (decl);
3234       DECL_NONCONVERTING_P (tmpl) = DECL_NONCONVERTING_P (decl);
3235       DECL_ASSIGNMENT_OPERATOR_P (tmpl) = DECL_ASSIGNMENT_OPERATOR_P (decl);
3236       if (DECL_OVERLOADED_OPERATOR_P (decl))
3237         SET_OVERLOADED_OPERATOR_CODE (tmpl,
3238                                       DECL_OVERLOADED_OPERATOR_P (decl));
3239     }
3240
3241   return tmpl;
3242 }
3243
3244 struct template_parm_data
3245 {
3246   /* The level of the template parameters we are currently
3247      processing.  */
3248   int level;
3249
3250   /* The index of the specialization argument we are currently
3251      processing.  */
3252   int current_arg;
3253
3254   /* An array whose size is the number of template parameters.  The
3255      elements are nonzero if the parameter has been used in any one
3256      of the arguments processed so far.  */
3257   int* parms;
3258
3259   /* An array whose size is the number of template arguments.  The
3260      elements are nonzero if the argument makes use of template
3261      parameters of this level.  */
3262   int* arg_uses_template_parms;
3263 };
3264
3265 /* Subroutine of push_template_decl used to see if each template
3266    parameter in a partial specialization is used in the explicit
3267    argument list.  If T is of the LEVEL given in DATA (which is
3268    treated as a template_parm_data*), then DATA->PARMS is marked
3269    appropriately.  */
3270
3271 static int
3272 mark_template_parm (tree t, void* data)
3273 {
3274   int level;
3275   int idx;
3276   struct template_parm_data* tpd = (struct template_parm_data*) data;
3277
3278   if (TREE_CODE (t) == TEMPLATE_PARM_INDEX)
3279     {
3280       level = TEMPLATE_PARM_LEVEL (t);
3281       idx = TEMPLATE_PARM_IDX (t);
3282     }
3283   else
3284     {
3285       level = TEMPLATE_TYPE_LEVEL (t);
3286       idx = TEMPLATE_TYPE_IDX (t);
3287     }
3288
3289   if (level == tpd->level)
3290     {
3291       tpd->parms[idx] = 1;
3292       tpd->arg_uses_template_parms[tpd->current_arg] = 1;
3293     }
3294
3295   /* Return zero so that for_each_template_parm will continue the
3296      traversal of the tree; we want to mark *every* template parm.  */
3297   return 0;
3298 }
3299
3300 /* Process the partial specialization DECL.  */
3301
3302 static tree
3303 process_partial_specialization (tree decl)
3304 {
3305   tree type = TREE_TYPE (decl);
3306   tree maintmpl = CLASSTYPE_TI_TEMPLATE (type);
3307   tree specargs = CLASSTYPE_TI_ARGS (type);
3308   tree inner_args = INNERMOST_TEMPLATE_ARGS (specargs);
3309   tree main_inner_parms = DECL_INNERMOST_TEMPLATE_PARMS (maintmpl);
3310   tree inner_parms;
3311   int nargs = TREE_VEC_LENGTH (inner_args);
3312   int ntparms;
3313   int  i;
3314   int did_error_intro = 0;
3315   struct template_parm_data tpd;
3316   struct template_parm_data tpd2;
3317
3318   gcc_assert (current_template_parms);
3319
3320   inner_parms = INNERMOST_TEMPLATE_PARMS (current_template_parms);
3321   ntparms = TREE_VEC_LENGTH (inner_parms);
3322
3323   /* We check that each of the template parameters given in the
3324      partial specialization is used in the argument list to the
3325      specialization.  For example:
3326
3327        template <class T> struct S;
3328        template <class T> struct S<T*>;
3329
3330      The second declaration is OK because `T*' uses the template
3331      parameter T, whereas
3332
3333        template <class T> struct S<int>;
3334
3335      is no good.  Even trickier is:
3336
3337        template <class T>
3338        struct S1
3339        {
3340           template <class U>
3341           struct S2;
3342           template <class U>
3343           struct S2<T>;
3344        };
3345
3346      The S2<T> declaration is actually invalid; it is a
3347      full-specialization.  Of course,
3348
3349           template <class U>
3350           struct S2<T (*)(U)>;
3351
3352      or some such would have been OK.  */
3353   tpd.level = TMPL_PARMS_DEPTH (current_template_parms);
3354   tpd.parms = (int *) alloca (sizeof (int) * ntparms);
3355   memset (tpd.parms, 0, sizeof (int) * ntparms);
3356
3357   tpd.arg_uses_template_parms = (int *) alloca (sizeof (int) * nargs);
3358   memset (tpd.arg_uses_template_parms, 0, sizeof (int) * nargs);
3359   for (i = 0; i < nargs; ++i)
3360     {
3361       tpd.current_arg = i;
3362       for_each_template_parm (TREE_VEC_ELT (inner_args, i),
3363                               &mark_template_parm,
3364                               &tpd,
3365                               NULL,
3366                               /*include_nondeduced_p=*/false);
3367     }
3368   for (i = 0; i < ntparms; ++i)
3369     if (tpd.parms[i] == 0)
3370       {
3371         /* One of the template parms was not used in the
3372            specialization.  */
3373         if (!did_error_intro)
3374           {
3375             error ("template parameters not used in partial specialization:");
3376             did_error_intro = 1;
3377           }
3378
3379         error ("        %qD", TREE_VALUE (TREE_VEC_ELT (inner_parms, i)));
3380       }
3381
3382   /* [temp.class.spec]
3383
3384      The argument list of the specialization shall not be identical to
3385      the implicit argument list of the primary template.  */
3386   if (comp_template_args
3387       (inner_args,
3388        INNERMOST_TEMPLATE_ARGS (CLASSTYPE_TI_ARGS (TREE_TYPE
3389                                                    (maintmpl)))))
3390     error ("partial specialization %qT does not specialize any template arguments", type);
3391
3392   /* [temp.class.spec]
3393
3394      A partially specialized non-type argument expression shall not
3395      involve template parameters of the partial specialization except
3396      when the argument expression is a simple identifier.
3397
3398      The type of a template parameter corresponding to a specialized
3399      non-type argument shall not be dependent on a parameter of the
3400      specialization. 
3401
3402      Also, we verify that pack expansions only occur at the
3403      end of the argument list.  */
3404   gcc_assert (nargs == DECL_NTPARMS (maintmpl));
3405   tpd2.parms = 0;
3406   for (i = 0; i < nargs; ++i)
3407     {
3408       tree parm = TREE_VALUE (TREE_VEC_ELT (main_inner_parms, i));
3409       tree arg = TREE_VEC_ELT (inner_args, i);
3410       tree packed_args = NULL_TREE;
3411       int j, len = 1;
3412
3413       if (ARGUMENT_PACK_P (arg))
3414         {
3415           /* Extract the arguments from the argument pack. We'll be
3416              iterating over these in the following loop.  */
3417           packed_args = ARGUMENT_PACK_ARGS (arg);
3418           len = TREE_VEC_LENGTH (packed_args);
3419         }
3420
3421       for (j = 0; j < len; j++)
3422         {
3423           if (packed_args)
3424             /* Get the Jth argument in the parameter pack.  */
3425             arg = TREE_VEC_ELT (packed_args, j);
3426
3427           if (PACK_EXPANSION_P (arg))
3428             {
3429               /* Pack expansions must come at the end of the
3430                  argument list.  */
3431               if ((packed_args && j < len - 1)
3432                   || (!packed_args && i < nargs - 1))
3433                 {
3434                   if (TREE_CODE (arg) == EXPR_PACK_EXPANSION)
3435                     error ("parameter pack argument %qE must be at the end of the template argument list", arg);
3436                   else
3437                     error ("parameter pack argument %qT must be at the end of the template argument list", arg);
3438
3439                   if (packed_args)
3440                     TREE_VEC_ELT (packed_args, j) = error_mark_node;
3441                 }
3442             }
3443
3444           if (TREE_CODE (arg) == EXPR_PACK_EXPANSION)
3445             /* We only care about the pattern.  */
3446             arg = PACK_EXPANSION_PATTERN (arg);
3447
3448           if (/* These first two lines are the `non-type' bit.  */
3449               !TYPE_P (arg)
3450               && TREE_CODE (arg) != TEMPLATE_DECL
3451               /* This next line is the `argument expression is not just a
3452                  simple identifier' condition and also the `specialized
3453                  non-type argument' bit.  */
3454               && TREE_CODE (arg) != TEMPLATE_PARM_INDEX)
3455             {
3456               if ((!packed_args && tpd.arg_uses_template_parms[i])
3457                   || (packed_args && uses_template_parms (arg)))
3458                 error ("template argument %qE involves template parameter(s)",
3459                        arg);
3460               else 
3461                 {
3462                   /* Look at the corresponding template parameter,
3463                      marking which template parameters its type depends
3464                      upon.  */
3465                   tree type = TREE_TYPE (parm);
3466
3467                   if (!tpd2.parms)
3468                     {
3469                       /* We haven't yet initialized TPD2.  Do so now.  */
3470                       tpd2.arg_uses_template_parms 
3471                         = (int *) alloca (sizeof (int) * nargs);
3472                       /* The number of parameters here is the number in the
3473                          main template, which, as checked in the assertion
3474                          above, is NARGS.  */
3475                       tpd2.parms = (int *) alloca (sizeof (int) * nargs);
3476                       tpd2.level = 
3477                         TMPL_PARMS_DEPTH (DECL_TEMPLATE_PARMS (maintmpl));
3478                     }
3479
3480                   /* Mark the template parameters.  But this time, we're
3481                      looking for the template parameters of the main
3482                      template, not in the specialization.  */
3483                   tpd2.current_arg = i;
3484                   tpd2.arg_uses_template_parms[i] = 0;
3485                   memset (tpd2.parms, 0, sizeof (int) * nargs);
3486                   for_each_template_parm (type,
3487                                           &mark_template_parm,
3488                                           &tpd2,
3489                                           NULL,
3490                                           /*include_nondeduced_p=*/false);
3491
3492                   if (tpd2.arg_uses_template_parms [i])
3493                     {
3494                       /* The type depended on some template parameters.
3495                          If they are fully specialized in the
3496                          specialization, that's OK.  */
3497                       int j;
3498                       for (j = 0; j < nargs; ++j)
3499                         if (tpd2.parms[j] != 0
3500                             && tpd.arg_uses_template_parms [j])
3501                           {
3502                             error ("type %qT of template argument %qE depends "
3503                                    "on template parameter(s)", 
3504                                    type,
3505                                    arg);
3506                             break;
3507                           }
3508                     }
3509                 }
3510             }
3511         }
3512     }
3513
3514   if (retrieve_specialization (maintmpl, specargs,
3515                                /*class_specializations_p=*/true))
3516     /* We've already got this specialization.  */
3517     return decl;
3518
3519   DECL_TEMPLATE_SPECIALIZATIONS (maintmpl)
3520     = tree_cons (specargs, inner_parms,
3521                  DECL_TEMPLATE_SPECIALIZATIONS (maintmpl));
3522   TREE_TYPE (DECL_TEMPLATE_SPECIALIZATIONS (maintmpl)) = type;
3523   return decl;
3524 }
3525
3526 /* Check that a template declaration's use of default arguments and
3527    parameter packs is not invalid.  Here, PARMS are the template
3528    parameters.  IS_PRIMARY is nonzero if DECL is the thing declared by
3529    a primary template.  IS_PARTIAL is nonzero if DECL is a partial
3530    specialization.
3531    
3532
3533    IS_FRIEND_DECL is nonzero if DECL is a friend function template
3534    declaration (but not a definition); 1 indicates a declaration, 2
3535    indicates a redeclaration. When IS_FRIEND_DECL=2, no errors are
3536    emitted for extraneous default arguments.
3537
3538    Returns TRUE if there were no errors found, FALSE otherwise. */
3539
3540 bool
3541 check_default_tmpl_args (tree decl, tree parms, int is_primary, 
3542                          int is_partial, int is_friend_decl)
3543 {
3544   const char *msg;
3545   int last_level_to_check;
3546   tree parm_level;
3547   bool no_errors = true;
3548
3549   /* [temp.param]
3550
3551      A default template-argument shall not be specified in a
3552      function template declaration or a function template definition, nor
3553      in the template-parameter-list of the definition of a member of a
3554      class template.  */
3555
3556   if (TREE_CODE (CP_DECL_CONTEXT (decl)) == FUNCTION_DECL)
3557     /* You can't have a function template declaration in a local
3558        scope, nor you can you define a member of a class template in a
3559        local scope.  */
3560     return true;
3561
3562   if (current_class_type
3563       && !TYPE_BEING_DEFINED (current_class_type)
3564       && DECL_LANG_SPECIFIC (decl)
3565       /* If this is either a friend defined in the scope of the class
3566          or a member function.  */
3567       && (DECL_FUNCTION_MEMBER_P (decl)
3568           ? same_type_p (DECL_CONTEXT (decl), current_class_type)
3569           : DECL_FRIEND_CONTEXT (decl)
3570           ? same_type_p (DECL_FRIEND_CONTEXT (decl), current_class_type)
3571           : false)
3572       /* And, if it was a member function, it really was defined in
3573          the scope of the class.  */
3574       && (!DECL_FUNCTION_MEMBER_P (decl)
3575           || DECL_INITIALIZED_IN_CLASS_P (decl)))
3576     /* We already checked these parameters when the template was
3577        declared, so there's no need to do it again now.  This function
3578        was defined in class scope, but we're processing it's body now
3579        that the class is complete.  */
3580     return true;
3581
3582   /* Core issue 226 (C++0x only): the following only applies to class
3583      templates.  */
3584   if ((cxx_dialect == cxx98) || TREE_CODE (decl) != FUNCTION_DECL)
3585     {
3586       /* [temp.param]
3587
3588          If a template-parameter has a default template-argument, all
3589          subsequent template-parameters shall have a default
3590          template-argument supplied.  */
3591       for (parm_level = parms; parm_level; parm_level = TREE_CHAIN (parm_level))
3592         {
3593           tree inner_parms = TREE_VALUE (parm_level);
3594           int ntparms = TREE_VEC_LENGTH (inner_parms);
3595           int seen_def_arg_p = 0;
3596           int i;
3597
3598           for (i = 0; i < ntparms; ++i)
3599             {
3600               tree parm = TREE_VEC_ELT (inner_parms, i);
3601
3602               if (parm == error_mark_node)
3603                 continue;
3604
3605               if (TREE_PURPOSE (parm))
3606                 seen_def_arg_p = 1;
3607               else if (seen_def_arg_p
3608                        && !template_parameter_pack_p (TREE_VALUE (parm)))
3609                 {
3610                   error ("no default argument for %qD", TREE_VALUE (parm));
3611                   /* For better subsequent error-recovery, we indicate that
3612                      there should have been a default argument.  */
3613                   TREE_PURPOSE (parm) = error_mark_node;
3614                   no_errors = false;
3615                 }
3616               else if (is_primary
3617                        && !is_partial
3618                        && !is_friend_decl
3619                        /* Don't complain about an enclosing partial
3620                           specialization.  */
3621                        && parm_level == parms
3622                        && TREE_CODE (decl) == TYPE_DECL
3623                        && i < ntparms - 1
3624                        && template_parameter_pack_p (TREE_VALUE (parm)))
3625                 {
3626                   /* A primary class template can only have one
3627                      parameter pack, at the end of the template
3628                      parameter list.  */
3629
3630                   if (TREE_CODE (TREE_VALUE (parm)) == PARM_DECL)
3631                     error ("parameter pack %qE must be at the end of the"
3632                            " template parameter list", TREE_VALUE (parm));
3633                   else
3634                     error ("parameter pack %qT must be at the end of the"
3635                            " template parameter list", 
3636                            TREE_TYPE (TREE_VALUE (parm)));
3637
3638                   TREE_VALUE (TREE_VEC_ELT (inner_parms, i)) 
3639                     = error_mark_node;
3640                   no_errors = false;
3641                 }
3642             }
3643         }
3644     }
3645
3646   if (((cxx_dialect == cxx98) && TREE_CODE (decl) != TYPE_DECL)
3647       || is_partial 
3648       || !is_primary
3649       || is_friend_decl)
3650     /* For an ordinary class template, default template arguments are
3651        allowed at the innermost level, e.g.:
3652          template <class T = int>
3653          struct S {};
3654        but, in a partial specialization, they're not allowed even
3655        there, as we have in [temp.class.spec]:
3656
3657          The template parameter list of a specialization shall not
3658          contain default template argument values.
3659
3660        So, for a partial specialization, or for a function template
3661        (in C++98/C++03), we look at all of them.  */
3662     ;
3663   else
3664     /* But, for a primary class template that is not a partial
3665        specialization we look at all template parameters except the
3666        innermost ones.  */
3667     parms = TREE_CHAIN (parms);
3668
3669   /* Figure out what error message to issue.  */
3670   if (is_friend_decl == 2)
3671     msg = "default template arguments may not be used in function template friend re-declaration";
3672   else if (is_friend_decl)
3673     msg = "default template arguments may not be used in function template friend declarations";
3674   else if (TREE_CODE (decl) == FUNCTION_DECL && (cxx_dialect == cxx98))
3675     msg = ("default template arguments may not be used in function templates "
3676            "without -std=c++0x or -std=gnu++0x");
3677   else if (is_partial)
3678     msg = "default template arguments may not be used in partial specializations";
3679   else
3680     msg = "default argument for template parameter for class enclosing %qD";
3681
3682   if (current_class_type && TYPE_BEING_DEFINED (current_class_type))
3683     /* If we're inside a class definition, there's no need to
3684        examine the parameters to the class itself.  On the one
3685        hand, they will be checked when the class is defined, and,
3686        on the other, default arguments are valid in things like:
3687          template <class T = double>
3688          struct S { template <class U> void f(U); };
3689        Here the default argument for `S' has no bearing on the
3690        declaration of `f'.  */
3691     last_level_to_check = template_class_depth (current_class_type) + 1;
3692   else
3693     /* Check everything.  */
3694     last_level_to_check = 0;
3695
3696   for (parm_level = parms;
3697        parm_level && TMPL_PARMS_DEPTH (parm_level) >= last_level_to_check;
3698        parm_level = TREE_CHAIN (parm_level))
3699     {
3700       tree inner_parms = TREE_VALUE (parm_level);
3701       int i;
3702       int ntparms;
3703
3704       ntparms = TREE_VEC_LENGTH (inner_parms);
3705       for (i = 0; i < ntparms; ++i)
3706         {
3707           if (TREE_VEC_ELT (inner_parms, i) == error_mark_node)
3708             continue;
3709
3710           if (TREE_PURPOSE (TREE_VEC_ELT (inner_parms, i)))
3711             {
3712               if (msg)
3713                 {
3714                   no_errors = false;
3715                   if (is_friend_decl == 2)
3716                     return no_errors;
3717
3718                   error (msg, decl);
3719                   msg = 0;
3720                 }
3721
3722               /* Clear out the default argument so that we are not
3723                  confused later.  */
3724               TREE_PURPOSE (TREE_VEC_ELT (inner_parms, i)) = NULL_TREE;
3725             }
3726         }
3727
3728       /* At this point, if we're still interested in issuing messages,
3729          they must apply to classes surrounding the object declared.  */
3730       if (msg)
3731         msg = "default argument for template parameter for class enclosing %qD";
3732     }
3733
3734   return no_errors;
3735 }
3736
3737 /* Worker for push_template_decl_real, called via
3738    for_each_template_parm.  DATA is really an int, indicating the
3739    level of the parameters we are interested in.  If T is a template
3740    parameter of that level, return nonzero.  */
3741
3742 static int
3743 template_parm_this_level_p (tree t, void* data)
3744 {
3745   int this_level = *(int *)data;
3746   int level;
3747
3748   if (TREE_CODE (t) == TEMPLATE_PARM_INDEX)
3749     level = TEMPLATE_PARM_LEVEL (t);
3750   else
3751     level = TEMPLATE_TYPE_LEVEL (t);
3752   return level == this_level;
3753 }
3754
3755 /* Creates a TEMPLATE_DECL for the indicated DECL using the template
3756    parameters given by current_template_args, or reuses a
3757    previously existing one, if appropriate.  Returns the DECL, or an
3758    equivalent one, if it is replaced via a call to duplicate_decls.
3759
3760    If IS_FRIEND is true, DECL is a friend declaration.  */
3761
3762 tree
3763 push_template_decl_real (tree decl, bool is_friend)
3764 {
3765   tree tmpl;
3766   tree args;
3767   tree info;
3768   tree ctx;
3769   int primary;
3770   int is_partial;
3771   int new_template_p = 0;
3772   /* True if the template is a member template, in the sense of
3773      [temp.mem].  */
3774   bool member_template_p = false;
3775
3776   if (decl == error_mark_node || !current_template_parms)
3777     return error_mark_node;
3778
3779   /* See if this is a partial specialization.  */
3780   is_partial = (DECL_IMPLICIT_TYPEDEF_P (decl)
3781                 && TREE_CODE (TREE_TYPE (decl)) != ENUMERAL_TYPE
3782                 && CLASSTYPE_TEMPLATE_SPECIALIZATION (TREE_TYPE (decl)));
3783
3784   if (TREE_CODE (decl) == FUNCTION_DECL && DECL_FRIEND_P (decl))
3785     is_friend = true;
3786
3787   if (is_friend)
3788     /* For a friend, we want the context of the friend function, not
3789        the type of which it is a friend.  */
3790     ctx = DECL_CONTEXT (decl);
3791   else if (CP_DECL_CONTEXT (decl)
3792            && TREE_CODE (CP_DECL_CONTEXT (decl)) != NAMESPACE_DECL)
3793     /* In the case of a virtual function, we want the class in which
3794        it is defined.  */
3795     ctx = CP_DECL_CONTEXT (decl);
3796   else
3797     /* Otherwise, if we're currently defining some class, the DECL
3798        is assumed to be a member of the class.  */
3799     ctx = current_scope ();
3800
3801   if (ctx && TREE_CODE (ctx) == NAMESPACE_DECL)
3802     ctx = NULL_TREE;
3803
3804   if (!DECL_CONTEXT (decl))
3805     DECL_CONTEXT (decl) = FROB_CONTEXT (current_namespace);
3806
3807   /* See if this is a primary template.  */
3808   if (is_friend && ctx)
3809     /* A friend template that specifies a class context, i.e.
3810          template <typename T> friend void A<T>::f();
3811        is not primary.  */
3812     primary = 0;
3813   else
3814     primary = template_parm_scope_p ();
3815
3816   if (primary)
3817     {
3818       if (DECL_CLASS_SCOPE_P (decl))
3819         member_template_p = true;
3820       if (TREE_CODE (decl) == TYPE_DECL
3821           && ANON_AGGRNAME_P (DECL_NAME (decl)))
3822         {
3823           error ("template class without a name");
3824           return error_mark_node;
3825         }
3826       else if (TREE_CODE (decl) == FUNCTION_DECL)
3827         {
3828           if (DECL_DESTRUCTOR_P (decl))
3829             {
3830               /* [temp.mem]
3831
3832                  A destructor shall not be a member template.  */
3833               error ("destructor %qD declared as member template", decl);
3834               return error_mark_node;
3835             }
3836           if (NEW_DELETE_OPNAME_P (DECL_NAME (decl))
3837               && (!TYPE_ARG_TYPES (TREE_TYPE (decl))
3838                   || TYPE_ARG_TYPES (TREE_TYPE (decl)) == void_list_node
3839                   || !TREE_CHAIN (TYPE_ARG_TYPES (TREE_TYPE (decl)))
3840                   || (TREE_CHAIN (TYPE_ARG_TYPES ((TREE_TYPE (decl))))
3841                       == void_list_node)))
3842             {
3843               /* [basic.stc.dynamic.allocation]
3844
3845                  An allocation function can be a function
3846                  template. ... Template allocation functions shall
3847                  have two or more parameters.  */
3848               error ("invalid template declaration of %qD", decl);
3849               return error_mark_node;
3850             }
3851         }
3852       else if (DECL_IMPLICIT_TYPEDEF_P (decl)
3853                && CLASS_TYPE_P (TREE_TYPE (decl)))
3854         /* OK */;
3855       else
3856         {
3857           error ("template declaration of %q#D", decl);
3858           return error_mark_node;
3859         }
3860     }
3861
3862   /* Check to see that the rules regarding the use of default
3863      arguments are not being violated.  */
3864   check_default_tmpl_args (decl, current_template_parms,
3865                            primary, is_partial, /*is_friend_decl=*/0);
3866
3867   /* Ensure that there are no parameter packs in the type of this
3868      declaration that have not been expanded.  */
3869   if (TREE_CODE (decl) == FUNCTION_DECL)
3870     {
3871       /* Check each of the arguments individually to see if there are
3872          any bare parameter packs.  */
3873       tree type = TREE_TYPE (decl);
3874       tree arg = DECL_ARGUMENTS (decl);
3875       tree argtype = TYPE_ARG_TYPES (type);
3876
3877       while (arg && argtype)
3878         {
3879           if (!FUNCTION_PARAMETER_PACK_P (arg)
3880               && check_for_bare_parameter_packs (TREE_TYPE (arg)))
3881             {
3882             /* This is a PARM_DECL that contains unexpanded parameter
3883                packs. We have already complained about this in the
3884                check_for_bare_parameter_packs call, so just replace
3885                these types with ERROR_MARK_NODE.  */
3886               TREE_TYPE (arg) = error_mark_node;
3887               TREE_VALUE (argtype) = error_mark_node;
3888             }
3889
3890           arg = TREE_CHAIN (arg);
3891           argtype = TREE_CHAIN (argtype);
3892         }
3893
3894       /* Check for bare parameter packs in the return type and the
3895          exception specifiers.  */
3896       if (check_for_bare_parameter_packs (TREE_TYPE (type)))
3897         /* Errors were already issued, set return type to int
3898            as the frontend doesn't expect error_mark_node as
3899            the return type.  */
3900         TREE_TYPE (type) = integer_type_node;
3901       if (check_for_bare_parameter_packs (TYPE_RAISES_EXCEPTIONS (type)))
3902         TYPE_RAISES_EXCEPTIONS (type) = NULL_TREE;
3903     }
3904   else if (check_for_bare_parameter_packs (TREE_TYPE (decl)))
3905     {
3906       TREE_TYPE (decl) = error_mark_node;
3907       return error_mark_node;
3908     }
3909
3910   if (is_partial)
3911     return process_partial_specialization (decl);
3912
3913   args = current_template_args ();
3914
3915   if (!ctx
3916       || TREE_CODE (ctx) == FUNCTION_DECL
3917       || (CLASS_TYPE_P (ctx) && TYPE_BEING_DEFINED (ctx))
3918       || (is_friend && !DECL_TEMPLATE_INFO (decl)))
3919     {
3920       if (DECL_LANG_SPECIFIC (decl)
3921           && DECL_TEMPLATE_INFO (decl)
3922           && DECL_TI_TEMPLATE (decl))
3923         tmpl = DECL_TI_TEMPLATE (decl);
3924       /* If DECL is a TYPE_DECL for a class-template, then there won't
3925          be DECL_LANG_SPECIFIC.  The information equivalent to
3926          DECL_TEMPLATE_INFO is found in TYPE_TEMPLATE_INFO instead.  */
3927       else if (DECL_IMPLICIT_TYPEDEF_P (decl)
3928                && TYPE_TEMPLATE_INFO (TREE_TYPE (decl))
3929                && TYPE_TI_TEMPLATE (TREE_TYPE (decl)))
3930         {
3931           /* Since a template declaration already existed for this
3932              class-type, we must be redeclaring it here.  Make sure
3933              that the redeclaration is valid.  */
3934           redeclare_class_template (TREE_TYPE (decl),
3935                                     current_template_parms);
3936           /* We don't need to create a new TEMPLATE_DECL; just use the
3937              one we already had.  */
3938           tmpl = TYPE_TI_TEMPLATE (TREE_TYPE (decl));
3939         }
3940       else
3941         {
3942           tmpl = build_template_decl (decl, current_template_parms,
3943                                       member_template_p);
3944           new_template_p = 1;
3945
3946           if (DECL_LANG_SPECIFIC (decl)
3947               && DECL_TEMPLATE_SPECIALIZATION (decl))
3948             {
3949               /* A specialization of a member template of a template
3950                  class.  */
3951               SET_DECL_TEMPLATE_SPECIALIZATION (tmpl);
3952               DECL_TEMPLATE_INFO (tmpl) = DECL_TEMPLATE_INFO (decl);
3953               DECL_TEMPLATE_INFO (decl) = NULL_TREE;
3954             }
3955         }
3956     }
3957   else
3958     {
3959       tree a, t, current, parms;
3960       int i;
3961       tree tinfo = get_template_info (decl);
3962
3963       if (!tinfo)
3964         {
3965           error ("template definition of non-template %q#D", decl);
3966           return error_mark_node;
3967         }
3968
3969       tmpl = TI_TEMPLATE (tinfo);
3970
3971       if (DECL_FUNCTION_TEMPLATE_P (tmpl)
3972           && DECL_TEMPLATE_INFO (decl) && DECL_TI_ARGS (decl)
3973           && DECL_TEMPLATE_SPECIALIZATION (decl)
3974           && DECL_MEMBER_TEMPLATE_P (tmpl))
3975         {
3976           tree new_tmpl;
3977
3978           /* The declaration is a specialization of a member
3979              template, declared outside the class.  Therefore, the
3980              innermost template arguments will be NULL, so we
3981              replace them with the arguments determined by the
3982              earlier call to check_explicit_specialization.  */
3983           args = DECL_TI_ARGS (decl);
3984
3985           new_tmpl
3986             = build_template_decl (decl, current_template_parms,
3987                                    member_template_p);
3988           DECL_TEMPLATE_RESULT (new_tmpl) = decl;
3989           TREE_TYPE (new_tmpl) = TREE_TYPE (decl);
3990           DECL_TI_TEMPLATE (decl) = new_tmpl;
3991           SET_DECL_TEMPLATE_SPECIALIZATION (new_tmpl);
3992           DECL_TEMPLATE_INFO (new_tmpl)
3993             = tree_cons (tmpl, args, NULL_TREE);
3994
3995           register_specialization (new_tmpl,
3996                                    most_general_template (tmpl),
3997                                    args,
3998                                    is_friend);
3999           return decl;
4000         }
4001
4002       /* Make sure the template headers we got make sense.  */
4003
4004       parms = DECL_TEMPLATE_PARMS (tmpl);
4005       i = TMPL_PARMS_DEPTH (parms);
4006       if (TMPL_ARGS_DEPTH (args) != i)
4007         {
4008           error ("expected %d levels of template parms for %q#D, got %d",
4009                  i, decl, TMPL_ARGS_DEPTH (args));
4010         }
4011       else
4012         for (current = decl; i > 0; --i, parms = TREE_CHAIN (parms))
4013           {
4014             a = TMPL_ARGS_LEVEL (args, i);
4015             t = INNERMOST_TEMPLATE_PARMS (parms);
4016
4017             if (TREE_VEC_LENGTH (t) != TREE_VEC_LENGTH (a))
4018               {
4019                 if (current == decl)
4020                   error ("got %d template parameters for %q#D",
4021                          TREE_VEC_LENGTH (a), decl);
4022                 else
4023                   error ("got %d template parameters for %q#T",
4024                          TREE_VEC_LENGTH (a), current);
4025                 error ("  but %d required", TREE_VEC_LENGTH (t));
4026                 return error_mark_node;
4027               }
4028
4029             if (current == decl)
4030               current = ctx;
4031             else
4032               current = (TYPE_P (current)
4033                          ? TYPE_CONTEXT (current)
4034                          : DECL_CONTEXT (current));
4035           }
4036
4037       /* Check that the parms are used in the appropriate qualifying scopes
4038          in the declarator.  */
4039       if (!comp_template_args
4040           (TI_ARGS (tinfo),
4041            TI_ARGS (get_template_info (DECL_TEMPLATE_RESULT (tmpl)))))
4042         {
4043           error ("\
4044 template arguments to %qD do not match original template %qD",
4045                  decl, DECL_TEMPLATE_RESULT (tmpl));
4046           if (!uses_template_parms (TI_ARGS (tinfo)))
4047             inform (input_location, "use template<> for an explicit specialization");
4048           /* Avoid crash in import_export_decl.  */
4049           DECL_INTERFACE_KNOWN (decl) = 1;
4050           return error_mark_node;
4051         }
4052     }
4053
4054   DECL_TEMPLATE_RESULT (tmpl) = decl;
4055   TREE_TYPE (tmpl) = TREE_TYPE (decl);
4056
4057   /* Push template declarations for global functions and types.  Note
4058      that we do not try to push a global template friend declared in a
4059      template class; such a thing may well depend on the template
4060      parameters of the class.  */
4061   if (new_template_p && !ctx
4062       && !(is_friend && template_class_depth (current_class_type) > 0))
4063     {
4064       tmpl = pushdecl_namespace_level (tmpl, is_friend);
4065       if (tmpl == error_mark_node)
4066         return error_mark_node;
4067
4068       /* Hide template friend classes that haven't been declared yet.  */
4069       if (is_friend && TREE_CODE (decl) == TYPE_DECL)
4070         {
4071           DECL_ANTICIPATED (tmpl) = 1;
4072           DECL_FRIEND_P (tmpl) = 1;
4073         }
4074     }
4075
4076   if (primary)
4077     {
4078       tree parms = DECL_TEMPLATE_PARMS (tmpl);
4079       int i;
4080
4081       DECL_PRIMARY_TEMPLATE (tmpl) = tmpl;
4082       if (DECL_CONV_FN_P (tmpl))
4083         {
4084           int depth = TMPL_PARMS_DEPTH (parms);
4085
4086           /* It is a conversion operator. See if the type converted to
4087              depends on innermost template operands.  */
4088
4089           if (uses_template_parms_level (TREE_TYPE (TREE_TYPE (tmpl)),
4090                                          depth))
4091             DECL_TEMPLATE_CONV_FN_P (tmpl) = 1;
4092         }
4093
4094       /* Give template template parms a DECL_CONTEXT of the template
4095          for which they are a parameter.  */
4096       parms = INNERMOST_TEMPLATE_PARMS (parms);
4097       for (i = TREE_VEC_LENGTH (parms) - 1; i >= 0; --i)
4098         {
4099           tree parm = TREE_VALUE (TREE_VEC_ELT (parms, i));
4100           if (TREE_CODE (parm) == TEMPLATE_DECL)
4101             DECL_CONTEXT (parm) = tmpl;
4102         }
4103     }
4104
4105   /* The DECL_TI_ARGS of DECL contains full set of arguments referring
4106      back to its most general template.  If TMPL is a specialization,
4107      ARGS may only have the innermost set of arguments.  Add the missing
4108      argument levels if necessary.  */
4109   if (DECL_TEMPLATE_INFO (tmpl))
4110     args = add_outermost_template_args (DECL_TI_ARGS (tmpl), args);
4111
4112   info = tree_cons (tmpl, args, NULL_TREE);
4113
4114   if (DECL_IMPLICIT_TYPEDEF_P (decl))
4115     SET_TYPE_TEMPLATE_INFO (TREE_TYPE (tmpl), info);
4116   else if (DECL_LANG_SPECIFIC (decl))
4117     DECL_TEMPLATE_INFO (decl) = info;
4118
4119   return DECL_TEMPLATE_RESULT (tmpl);
4120 }
4121
4122 tree
4123 push_template_decl (tree decl)
4124 {
4125   return push_template_decl_real (decl, false);
4126 }
4127
4128 /* Called when a class template TYPE is redeclared with the indicated
4129    template PARMS, e.g.:
4130
4131      template <class T> struct S;
4132      template <class T> struct S {};  */
4133
4134 bool
4135 redeclare_class_template (tree type, tree parms)
4136 {
4137   tree tmpl;
4138   tree tmpl_parms;
4139   int i;