OSDN Git Service

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