OSDN Git Service

PR c++/28903
[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 = TREE_VALUE (TREE_VEC_ELT (parms, i));
340
341       if (parm == error_mark_node)
342         continue;
343
344       gcc_assert (DECL_P (parm));
345
346       switch (TREE_CODE (parm))
347         {
348         case TYPE_DECL:
349         case TEMPLATE_DECL:
350           pushdecl (parm);
351           break;
352
353         case PARM_DECL:
354           {
355             /* Make a CONST_DECL as is done in process_template_parm.
356                It is ugly that we recreate this here; the original
357                version built in process_template_parm is no longer
358                available.  */
359             tree decl = build_decl (CONST_DECL, DECL_NAME (parm),
360                                     TREE_TYPE (parm));
361             DECL_ARTIFICIAL (decl) = 1;
362             TREE_CONSTANT (decl) = 1;
363             TREE_INVARIANT (decl) = 1;
364             TREE_READONLY (decl) = 1;
365             DECL_INITIAL (decl) = DECL_INITIAL (parm);
366             SET_DECL_TEMPLATE_PARM_P (decl);
367             pushdecl (decl);
368           }
369           break;
370
371         default:
372           gcc_unreachable ();
373         }
374     }
375 }
376
377 /* Restore the template parameter context for a member template or
378    a friend template defined in a class definition.  */
379
380 void
381 maybe_begin_member_template_processing (tree decl)
382 {
383   tree parms;
384   int levels = 0;
385
386   if (inline_needs_template_parms (decl))
387     {
388       parms = DECL_TEMPLATE_PARMS (most_general_template (decl));
389       levels = TMPL_PARMS_DEPTH (parms) - processing_template_decl;
390
391       if (DECL_TEMPLATE_SPECIALIZATION (decl))
392         {
393           --levels;
394           parms = TREE_CHAIN (parms);
395         }
396
397       push_inline_template_parms_recursive (parms, levels);
398     }
399
400   /* Remember how many levels of template parameters we pushed so that
401      we can pop them later.  */
402   VEC_safe_push (int, heap, inline_parm_levels, levels);
403 }
404
405 /* Undo the effects of maybe_begin_member_template_processing.  */
406
407 void
408 maybe_end_member_template_processing (void)
409 {
410   int i;
411   int last;
412
413   if (VEC_length (int, inline_parm_levels) == 0)
414     return;
415
416   last = VEC_pop (int, inline_parm_levels);
417   for (i = 0; i < last; ++i)
418     {
419       --processing_template_decl;
420       current_template_parms = TREE_CHAIN (current_template_parms);
421       poplevel (0, 0, 0);
422     }
423 }
424
425 /* Return a new template argument vector which contains all of ARGS,
426    but has as its innermost set of arguments the EXTRA_ARGS.  */
427
428 static tree
429 add_to_template_args (tree args, tree extra_args)
430 {
431   tree new_args;
432   int extra_depth;
433   int i;
434   int j;
435
436   extra_depth = TMPL_ARGS_DEPTH (extra_args);
437   new_args = make_tree_vec (TMPL_ARGS_DEPTH (args) + extra_depth);
438
439   for (i = 1; i <= TMPL_ARGS_DEPTH (args); ++i)
440     SET_TMPL_ARGS_LEVEL (new_args, i, TMPL_ARGS_LEVEL (args, i));
441
442   for (j = 1; j <= extra_depth; ++j, ++i)
443     SET_TMPL_ARGS_LEVEL (new_args, i, TMPL_ARGS_LEVEL (extra_args, j));
444
445   return new_args;
446 }
447
448 /* Like add_to_template_args, but only the outermost ARGS are added to
449    the EXTRA_ARGS.  In particular, all but TMPL_ARGS_DEPTH
450    (EXTRA_ARGS) levels are added.  This function is used to combine
451    the template arguments from a partial instantiation with the
452    template arguments used to attain the full instantiation from the
453    partial instantiation.  */
454
455 static tree
456 add_outermost_template_args (tree args, tree extra_args)
457 {
458   tree new_args;
459
460   /* If there are more levels of EXTRA_ARGS than there are ARGS,
461      something very fishy is going on.  */
462   gcc_assert (TMPL_ARGS_DEPTH (args) >= TMPL_ARGS_DEPTH (extra_args));
463
464   /* If *all* the new arguments will be the EXTRA_ARGS, just return
465      them.  */
466   if (TMPL_ARGS_DEPTH (args) == TMPL_ARGS_DEPTH (extra_args))
467     return extra_args;
468
469   /* For the moment, we make ARGS look like it contains fewer levels.  */
470   TREE_VEC_LENGTH (args) -= TMPL_ARGS_DEPTH (extra_args);
471
472   new_args = add_to_template_args (args, extra_args);
473
474   /* Now, we restore ARGS to its full dimensions.  */
475   TREE_VEC_LENGTH (args) += TMPL_ARGS_DEPTH (extra_args);
476
477   return new_args;
478 }
479
480 /* Return the N levels of innermost template arguments from the ARGS.  */
481
482 tree
483 get_innermost_template_args (tree args, int n)
484 {
485   tree new_args;
486   int extra_levels;
487   int i;
488
489   gcc_assert (n >= 0);
490
491   /* If N is 1, just return the innermost set of template arguments.  */
492   if (n == 1)
493     return TMPL_ARGS_LEVEL (args, TMPL_ARGS_DEPTH (args));
494
495   /* If we're not removing anything, just return the arguments we were
496      given.  */
497   extra_levels = TMPL_ARGS_DEPTH (args) - n;
498   gcc_assert (extra_levels >= 0);
499   if (extra_levels == 0)
500     return args;
501
502   /* Make a new set of arguments, not containing the outer arguments.  */
503   new_args = make_tree_vec (n);
504   for (i = 1; i <= n; ++i)
505     SET_TMPL_ARGS_LEVEL (new_args, i,
506                          TMPL_ARGS_LEVEL (args, i + extra_levels));
507
508   return new_args;
509 }
510
511 /* We've got a template header coming up; push to a new level for storing
512    the parms.  */
513
514 void
515 begin_template_parm_list (void)
516 {
517   /* We use a non-tag-transparent scope here, which causes pushtag to
518      put tags in this scope, rather than in the enclosing class or
519      namespace scope.  This is the right thing, since we want
520      TEMPLATE_DECLS, and not TYPE_DECLS for template classes.  For a
521      global template class, push_template_decl handles putting the
522      TEMPLATE_DECL into top-level scope.  For a nested template class,
523      e.g.:
524
525        template <class T> struct S1 {
526          template <class T> struct S2 {};
527        };
528
529      pushtag contains special code to call pushdecl_with_scope on the
530      TEMPLATE_DECL for S2.  */
531   begin_scope (sk_template_parms, NULL);
532   ++processing_template_decl;
533   ++processing_template_parmlist;
534   note_template_header (0);
535 }
536
537 /* This routine is called when a specialization is declared.  If it is
538    invalid to declare a specialization here, an error is reported.  */
539
540 static void
541 check_specialization_scope (void)
542 {
543   tree scope = current_scope ();
544
545   /* [temp.expl.spec]
546
547      An explicit specialization shall be declared in the namespace of
548      which the template is a member, or, for member templates, in the
549      namespace of which the enclosing class or enclosing class
550      template is a member.  An explicit specialization of a member
551      function, member class or static data member of a class template
552      shall be declared in the namespace of which the class template
553      is a member.  */
554   if (scope && TREE_CODE (scope) != NAMESPACE_DECL)
555     error ("explicit specialization in non-namespace scope %qD", scope);
556
557   /* [temp.expl.spec]
558
559      In an explicit specialization declaration for a member of a class
560      template or a member template that appears in namespace scope,
561      the member template and some of its enclosing class templates may
562      remain unspecialized, except that the declaration shall not
563      explicitly specialize a class member template if its enclosing
564      class templates are not explicitly specialized as well.  */
565   if (current_template_parms)
566     error ("enclosing class templates are not explicitly specialized");
567 }
568
569 /* We've just seen template <>.  */
570
571 void
572 begin_specialization (void)
573 {
574   begin_scope (sk_template_spec, NULL);
575   note_template_header (1);
576   check_specialization_scope ();
577 }
578
579 /* Called at then end of processing a declaration preceded by
580    template<>.  */
581
582 void
583 end_specialization (void)
584 {
585   finish_scope ();
586   reset_specialization ();
587 }
588
589 /* Any template <>'s that we have seen thus far are not referring to a
590    function specialization.  */
591
592 void
593 reset_specialization (void)
594 {
595   processing_specialization = 0;
596   template_header_count = 0;
597 }
598
599 /* We've just seen a template header.  If SPECIALIZATION is nonzero,
600    it was of the form template <>.  */
601
602 static void
603 note_template_header (int specialization)
604 {
605   processing_specialization = specialization;
606   template_header_count++;
607 }
608
609 /* We're beginning an explicit instantiation.  */
610
611 void
612 begin_explicit_instantiation (void)
613 {
614   gcc_assert (!processing_explicit_instantiation);
615   processing_explicit_instantiation = true;
616 }
617
618
619 void
620 end_explicit_instantiation (void)
621 {
622   gcc_assert (processing_explicit_instantiation);
623   processing_explicit_instantiation = false;
624 }
625
626 /* An explicit specialization or partial specialization TMPL is being
627    declared.  Check that the namespace in which the specialization is
628    occurring is permissible.  Returns false iff it is invalid to
629    specialize TMPL in the current namespace.  */
630
631 static bool
632 check_specialization_namespace (tree tmpl)
633 {
634   tree tpl_ns = decl_namespace_context (tmpl);
635
636   /* [tmpl.expl.spec]
637
638      An explicit specialization shall be declared in the namespace of
639      which the template is a member, or, for member templates, in the
640      namespace of which the enclosing class or enclosing class
641      template is a member.  An explicit specialization of a member
642      function, member class or static data member of a class template
643      shall be declared in the namespace of which the class template is
644      a member.  */
645   if (is_associated_namespace (current_namespace, tpl_ns))
646     /* Same or super-using namespace.  */
647     return true;
648   else
649     {
650       pedwarn ("specialization of %qD in different namespace", tmpl);
651       pedwarn ("  from definition of %q+#D", tmpl);
652       return false;
653     }
654 }
655
656 /* SPEC is an explicit instantiation.  Check that it is valid to
657    perform this explicit instantiation in the current namespace.  */
658
659 static void
660 check_explicit_instantiation_namespace (tree spec)
661 {
662   tree ns;
663
664   /* DR 275: An explicit instantiation shall appear in an enclosing
665      namespace of its template.  */
666   ns = decl_namespace_context (spec);
667   if (!is_ancestor (current_namespace, ns))
668     pedwarn ("explicit instantiation of %qD in namespace %qD "
669              "(which does not enclose namespace %qD)",
670              spec, current_namespace, ns);
671 }
672
673 /* The TYPE is being declared.  If it is a template type, that means it
674    is a partial specialization.  Do appropriate error-checking.  */
675
676 tree
677 maybe_process_partial_specialization (tree type)
678 {
679   tree context;
680
681   if (type == error_mark_node)
682     return error_mark_node;
683
684   if (TREE_CODE (type) == BOUND_TEMPLATE_TEMPLATE_PARM)
685     {
686       error ("name of class shadows template template parameter %qD",
687              TYPE_NAME (type));
688       return error_mark_node;
689     }
690
691   context = TYPE_CONTEXT (type);
692
693   if (CLASS_TYPE_P (type) && CLASSTYPE_USE_TEMPLATE (type))
694     {
695       /* This is for ordinary explicit specialization and partial
696          specialization of a template class such as:
697
698            template <> class C<int>;
699
700          or:
701
702            template <class T> class C<T*>;
703
704          Make sure that `C<int>' and `C<T*>' are implicit instantiations.  */
705
706       if (CLASSTYPE_IMPLICIT_INSTANTIATION (type)
707           && !COMPLETE_TYPE_P (type))
708         {
709           check_specialization_namespace (CLASSTYPE_TI_TEMPLATE (type));
710           SET_CLASSTYPE_TEMPLATE_SPECIALIZATION (type);
711           if (processing_template_decl)
712             push_template_decl (TYPE_MAIN_DECL (type));
713         }
714       else if (CLASSTYPE_TEMPLATE_INSTANTIATION (type))
715         error ("specialization of %qT after instantiation", type);
716     }
717   else if (CLASS_TYPE_P (type)
718            && !CLASSTYPE_USE_TEMPLATE (type)
719            && CLASSTYPE_TEMPLATE_INFO (type)
720            && context && CLASS_TYPE_P (context)
721            && CLASSTYPE_TEMPLATE_INFO (context))
722     {
723       /* This is for an explicit specialization of member class
724          template according to [temp.expl.spec/18]:
725
726            template <> template <class U> class C<int>::D;
727
728          The context `C<int>' must be an implicit instantiation.
729          Otherwise this is just a member class template declared
730          earlier like:
731
732            template <> class C<int> { template <class U> class D; };
733            template <> template <class U> class C<int>::D;
734
735          In the first case, `C<int>::D' is a specialization of `C<T>::D'
736          while in the second case, `C<int>::D' is a primary template
737          and `C<T>::D' may not exist.  */
738
739       if (CLASSTYPE_IMPLICIT_INSTANTIATION (context)
740           && !COMPLETE_TYPE_P (type))
741         {
742           tree t;
743
744           if (current_namespace
745               != decl_namespace_context (CLASSTYPE_TI_TEMPLATE (type)))
746             {
747               pedwarn ("specializing %q#T in different namespace", type);
748               pedwarn ("  from definition of %q+#D",
749                        CLASSTYPE_TI_TEMPLATE (type));
750             }
751
752           /* Check for invalid specialization after instantiation:
753
754                template <> template <> class C<int>::D<int>;
755                template <> template <class U> class C<int>::D;  */
756
757           for (t = DECL_TEMPLATE_INSTANTIATIONS
758                  (most_general_template (CLASSTYPE_TI_TEMPLATE (type)));
759                t; t = TREE_CHAIN (t))
760             if (TREE_VALUE (t) != type
761                 && TYPE_CONTEXT (TREE_VALUE (t)) == context)
762               error ("specialization %qT after instantiation %qT",
763                      type, TREE_VALUE (t));
764
765           /* Mark TYPE as a specialization.  And as a result, we only
766              have one level of template argument for the innermost
767              class template.  */
768           SET_CLASSTYPE_TEMPLATE_SPECIALIZATION (type);
769           CLASSTYPE_TI_ARGS (type)
770             = INNERMOST_TEMPLATE_ARGS (CLASSTYPE_TI_ARGS (type));
771         }
772     }
773   else if (processing_specialization)
774     {
775       error ("explicit specialization of non-template %qT", type);
776       return error_mark_node;
777     }
778
779   return type;
780 }
781
782 /* Returns nonzero if we can optimize the retrieval of specializations
783    for TMPL, a TEMPLATE_DECL.  In particular, for such a template, we
784    do not use DECL_TEMPLATE_SPECIALIZATIONS at all.  */
785
786 static inline bool
787 optimize_specialization_lookup_p (tree tmpl)
788 {
789   return (DECL_FUNCTION_TEMPLATE_P (tmpl)
790           && DECL_CLASS_SCOPE_P (tmpl)
791           /* DECL_CLASS_SCOPE_P holds of T::f even if T is a template
792              parameter.  */
793           && CLASS_TYPE_P (DECL_CONTEXT (tmpl))
794           /* The optimized lookup depends on the fact that the
795              template arguments for the member function template apply
796              purely to the containing class, which is not true if the
797              containing class is an explicit or partial
798              specialization.  */
799           && !CLASSTYPE_TEMPLATE_SPECIALIZATION (DECL_CONTEXT (tmpl))
800           && !DECL_MEMBER_TEMPLATE_P (tmpl)
801           && !DECL_CONV_FN_P (tmpl)
802           /* It is possible to have a template that is not a member
803              template and is not a member of a template class:
804
805              template <typename T>
806              struct S { friend A::f(); };
807
808              Here, the friend function is a template, but the context does
809              not have template information.  The optimized lookup relies
810              on having ARGS be the template arguments for both the class
811              and the function template.  */
812           && !DECL_FRIEND_P (DECL_TEMPLATE_RESULT (tmpl)));
813 }
814
815 /* Retrieve the specialization (in the sense of [temp.spec] - a
816    specialization is either an instantiation or an explicit
817    specialization) of TMPL for the given template ARGS.  If there is
818    no such specialization, return NULL_TREE.  The ARGS are a vector of
819    arguments, or a vector of vectors of arguments, in the case of
820    templates with more than one level of parameters.
821
822    If TMPL is a type template and CLASS_SPECIALIZATIONS_P is true,
823    then we search for a partial specialization matching ARGS.  This
824    parameter is ignored if TMPL is not a class template.  */
825
826 static tree
827 retrieve_specialization (tree tmpl, tree args,
828                          bool class_specializations_p)
829 {
830   if (args == error_mark_node)
831     return NULL_TREE;
832
833   gcc_assert (TREE_CODE (tmpl) == TEMPLATE_DECL);
834
835   /* There should be as many levels of arguments as there are
836      levels of parameters.  */
837   gcc_assert (TMPL_ARGS_DEPTH (args)
838               == TMPL_PARMS_DEPTH (DECL_TEMPLATE_PARMS (tmpl)));
839
840   if (optimize_specialization_lookup_p (tmpl))
841     {
842       tree class_template;
843       tree class_specialization;
844       VEC(tree,gc) *methods;
845       tree fns;
846       int idx;
847
848       /* The template arguments actually apply to the containing
849          class.  Find the class specialization with those
850          arguments.  */
851       class_template = CLASSTYPE_TI_TEMPLATE (DECL_CONTEXT (tmpl));
852       class_specialization
853         = retrieve_specialization (class_template, args,
854                                    /*class_specializations_p=*/false);
855       if (!class_specialization)
856         return NULL_TREE;
857       /* Now, find the appropriate entry in the CLASSTYPE_METHOD_VEC
858          for the specialization.  */
859       idx = class_method_index_for_fn (class_specialization, tmpl);
860       if (idx == -1)
861         return NULL_TREE;
862       /* Iterate through the methods with the indicated name, looking
863          for the one that has an instance of TMPL.  */
864       methods = CLASSTYPE_METHOD_VEC (class_specialization);
865       for (fns = VEC_index (tree, methods, idx); fns; fns = OVL_NEXT (fns))
866         {
867           tree fn = OVL_CURRENT (fns);
868           if (DECL_TEMPLATE_INFO (fn) && DECL_TI_TEMPLATE (fn) == tmpl)
869             return fn;
870         }
871       return NULL_TREE;
872     }
873   else
874     {
875       tree *sp;
876       tree *head;
877
878       /* Class templates store their instantiations on the
879          DECL_TEMPLATE_INSTANTIATIONS list; other templates use the
880          DECL_TEMPLATE_SPECIALIZATIONS list.  */
881       if (!class_specializations_p
882           && TREE_CODE (DECL_TEMPLATE_RESULT (tmpl)) == TYPE_DECL)
883         sp = &DECL_TEMPLATE_INSTANTIATIONS (tmpl);
884       else
885         sp = &DECL_TEMPLATE_SPECIALIZATIONS (tmpl);
886       head = sp;
887       /* Iterate through the list until we find a matching template.  */
888       while (*sp != NULL_TREE)
889         {
890           tree spec = *sp;
891
892           if (comp_template_args (TREE_PURPOSE (spec), args))
893             {
894               /* Use the move-to-front heuristic to speed up future
895                  searches.  */
896               if (spec != *head)
897                 {
898                   *sp = TREE_CHAIN (*sp);
899                   TREE_CHAIN (spec) = *head;
900                   *head = spec;
901                 }
902               return TREE_VALUE (spec);
903             }
904           sp = &TREE_CHAIN (spec);
905         }
906     }
907
908   return NULL_TREE;
909 }
910
911 /* Like retrieve_specialization, but for local declarations.  */
912
913 static tree
914 retrieve_local_specialization (tree tmpl)
915 {
916   tree spec = (tree) htab_find_with_hash (local_specializations, tmpl,
917                                           htab_hash_pointer (tmpl));
918   return spec ? TREE_PURPOSE (spec) : NULL_TREE;
919 }
920
921 /* Returns nonzero iff DECL is a specialization of TMPL.  */
922
923 int
924 is_specialization_of (tree decl, tree tmpl)
925 {
926   tree t;
927
928   if (TREE_CODE (decl) == FUNCTION_DECL)
929     {
930       for (t = decl;
931            t != NULL_TREE;
932            t = DECL_TEMPLATE_INFO (t) ? DECL_TI_TEMPLATE (t) : NULL_TREE)
933         if (t == tmpl)
934           return 1;
935     }
936   else
937     {
938       gcc_assert (TREE_CODE (decl) == TYPE_DECL);
939
940       for (t = TREE_TYPE (decl);
941            t != NULL_TREE;
942            t = CLASSTYPE_USE_TEMPLATE (t)
943              ? TREE_TYPE (CLASSTYPE_TI_TEMPLATE (t)) : NULL_TREE)
944         if (same_type_ignoring_top_level_qualifiers_p (t, TREE_TYPE (tmpl)))
945           return 1;
946     }
947
948   return 0;
949 }
950
951 /* Returns nonzero iff DECL is a specialization of friend declaration
952    FRIEND according to [temp.friend].  */
953
954 bool
955 is_specialization_of_friend (tree decl, tree friend)
956 {
957   bool need_template = true;
958   int template_depth;
959
960   gcc_assert (TREE_CODE (decl) == FUNCTION_DECL
961               || TREE_CODE (decl) == TYPE_DECL);
962
963   /* For [temp.friend/6] when FRIEND is an ordinary member function
964      of a template class, we want to check if DECL is a specialization
965      if this.  */
966   if (TREE_CODE (friend) == FUNCTION_DECL
967       && DECL_TEMPLATE_INFO (friend)
968       && !DECL_USE_TEMPLATE (friend))
969     {
970       /* We want a TEMPLATE_DECL for `is_specialization_of'.  */
971       friend = DECL_TI_TEMPLATE (friend);
972       need_template = false;
973     }
974   else if (TREE_CODE (friend) == TEMPLATE_DECL
975            && !PRIMARY_TEMPLATE_P (friend))
976     need_template = false;
977
978   /* There is nothing to do if this is not a template friend.  */
979   if (TREE_CODE (friend) != TEMPLATE_DECL)
980     return false;
981
982   if (is_specialization_of (decl, friend))
983     return true;
984
985   /* [temp.friend/6]
986      A member of a class template may be declared to be a friend of a
987      non-template class.  In this case, the corresponding member of
988      every specialization of the class template is a friend of the
989      class granting friendship.
990
991      For example, given a template friend declaration
992
993        template <class T> friend void A<T>::f();
994
995      the member function below is considered a friend
996
997        template <> struct A<int> {
998          void f();
999        };
1000
1001      For this type of template friend, TEMPLATE_DEPTH below will be
1002      nonzero.  To determine if DECL is a friend of FRIEND, we first
1003      check if the enclosing class is a specialization of another.  */
1004
1005   template_depth = template_class_depth (DECL_CONTEXT (friend));
1006   if (template_depth
1007       && DECL_CLASS_SCOPE_P (decl)
1008       && is_specialization_of (TYPE_NAME (DECL_CONTEXT (decl)),
1009                                CLASSTYPE_TI_TEMPLATE (DECL_CONTEXT (friend))))
1010     {
1011       /* Next, we check the members themselves.  In order to handle
1012          a few tricky cases, such as when FRIEND's are
1013
1014            template <class T> friend void A<T>::g(T t);
1015            template <class T> template <T t> friend void A<T>::h();
1016
1017          and DECL's are
1018
1019            void A<int>::g(int);
1020            template <int> void A<int>::h();
1021
1022          we need to figure out ARGS, the template arguments from
1023          the context of DECL.  This is required for template substitution
1024          of `T' in the function parameter of `g' and template parameter
1025          of `h' in the above examples.  Here ARGS corresponds to `int'.  */
1026
1027       tree context = DECL_CONTEXT (decl);
1028       tree args = NULL_TREE;
1029       int current_depth = 0;
1030
1031       while (current_depth < template_depth)
1032         {
1033           if (CLASSTYPE_TEMPLATE_INFO (context))
1034             {
1035               if (current_depth == 0)
1036                 args = TYPE_TI_ARGS (context);
1037               else
1038                 args = add_to_template_args (TYPE_TI_ARGS (context), args);
1039               current_depth++;
1040             }
1041           context = TYPE_CONTEXT (context);
1042         }
1043
1044       if (TREE_CODE (decl) == FUNCTION_DECL)
1045         {
1046           bool is_template;
1047           tree friend_type;
1048           tree decl_type;
1049           tree friend_args_type;
1050           tree decl_args_type;
1051
1052           /* Make sure that both DECL and FRIEND are templates or
1053              non-templates.  */
1054           is_template = DECL_TEMPLATE_INFO (decl)
1055                         && PRIMARY_TEMPLATE_P (DECL_TI_TEMPLATE (decl));
1056           if (need_template ^ is_template)
1057             return false;
1058           else if (is_template)
1059             {
1060               /* If both are templates, check template parameter list.  */
1061               tree friend_parms
1062                 = tsubst_template_parms (DECL_TEMPLATE_PARMS (friend),
1063                                          args, tf_none);
1064               if (!comp_template_parms
1065                      (DECL_TEMPLATE_PARMS (DECL_TI_TEMPLATE (decl)),
1066                       friend_parms))
1067                 return false;
1068
1069               decl_type = TREE_TYPE (DECL_TI_TEMPLATE (decl));
1070             }
1071           else
1072             decl_type = TREE_TYPE (decl);
1073
1074           friend_type = tsubst_function_type (TREE_TYPE (friend), args,
1075                                               tf_none, NULL_TREE);
1076           if (friend_type == error_mark_node)
1077             return false;
1078
1079           /* Check if return types match.  */
1080           if (!same_type_p (TREE_TYPE (decl_type), TREE_TYPE (friend_type)))
1081             return false;
1082
1083           /* Check if function parameter types match, ignoring the
1084              `this' parameter.  */
1085           friend_args_type = TYPE_ARG_TYPES (friend_type);
1086           decl_args_type = TYPE_ARG_TYPES (decl_type);
1087           if (DECL_NONSTATIC_MEMBER_FUNCTION_P (friend))
1088             friend_args_type = TREE_CHAIN (friend_args_type);
1089           if (DECL_NONSTATIC_MEMBER_FUNCTION_P (decl))
1090             decl_args_type = TREE_CHAIN (decl_args_type);
1091
1092           return compparms (decl_args_type, friend_args_type);
1093         }
1094       else
1095         {
1096           /* DECL is a TYPE_DECL */
1097           bool is_template;
1098           tree decl_type = TREE_TYPE (decl);
1099
1100           /* Make sure that both DECL and FRIEND are templates or
1101              non-templates.  */
1102           is_template
1103             = CLASSTYPE_TEMPLATE_INFO (decl_type)
1104               && PRIMARY_TEMPLATE_P (CLASSTYPE_TI_TEMPLATE (decl_type));
1105
1106           if (need_template ^ is_template)
1107             return false;
1108           else if (is_template)
1109             {
1110               tree friend_parms;
1111               /* If both are templates, check the name of the two
1112                  TEMPLATE_DECL's first because is_friend didn't.  */
1113               if (DECL_NAME (CLASSTYPE_TI_TEMPLATE (decl_type))
1114                   != DECL_NAME (friend))
1115                 return false;
1116
1117               /* Now check template parameter list.  */
1118               friend_parms
1119                 = tsubst_template_parms (DECL_TEMPLATE_PARMS (friend),
1120                                          args, tf_none);
1121               return comp_template_parms
1122                 (DECL_TEMPLATE_PARMS (CLASSTYPE_TI_TEMPLATE (decl_type)),
1123                  friend_parms);
1124             }
1125           else
1126             return (DECL_NAME (decl)
1127                     == DECL_NAME (friend));
1128         }
1129     }
1130   return false;
1131 }
1132
1133 /* Register the specialization SPEC as a specialization of TMPL with
1134    the indicated ARGS.  IS_FRIEND indicates whether the specialization
1135    is actually just a friend declaration.  Returns SPEC, or an
1136    equivalent prior declaration, if available.  */
1137
1138 static tree
1139 register_specialization (tree spec, tree tmpl, tree args, bool is_friend)
1140 {
1141   tree fn;
1142
1143   gcc_assert (TREE_CODE (tmpl) == TEMPLATE_DECL);
1144
1145   if (TREE_CODE (spec) == FUNCTION_DECL
1146       && uses_template_parms (DECL_TI_ARGS (spec)))
1147     /* This is the FUNCTION_DECL for a partial instantiation.  Don't
1148        register it; we want the corresponding TEMPLATE_DECL instead.
1149        We use `uses_template_parms (DECL_TI_ARGS (spec))' rather than
1150        the more obvious `uses_template_parms (spec)' to avoid problems
1151        with default function arguments.  In particular, given
1152        something like this:
1153
1154           template <class T> void f(T t1, T t = T())
1155
1156        the default argument expression is not substituted for in an
1157        instantiation unless and until it is actually needed.  */
1158     return spec;
1159
1160   fn = retrieve_specialization (tmpl, args,
1161                                 /*class_specializations_p=*/false);
1162   /* We can sometimes try to re-register a specialization that we've
1163      already got.  In particular, regenerate_decl_from_template calls
1164      duplicate_decls which will update the specialization list.  But,
1165      we'll still get called again here anyhow.  It's more convenient
1166      to simply allow this than to try to prevent it.  */
1167   if (fn == spec)
1168     return spec;
1169   else if (fn && DECL_TEMPLATE_SPECIALIZATION (spec))
1170     {
1171       if (DECL_TEMPLATE_INSTANTIATION (fn))
1172         {
1173           if (TREE_USED (fn)
1174               || DECL_EXPLICIT_INSTANTIATION (fn))
1175             {
1176               error ("specialization of %qD after instantiation",
1177                      fn);
1178               return error_mark_node;
1179             }
1180           else
1181             {
1182               tree clone;
1183               /* This situation should occur only if the first
1184                  specialization is an implicit instantiation, the
1185                  second is an explicit specialization, and the
1186                  implicit instantiation has not yet been used.  That
1187                  situation can occur if we have implicitly
1188                  instantiated a member function and then specialized
1189                  it later.
1190
1191                  We can also wind up here if a friend declaration that
1192                  looked like an instantiation turns out to be a
1193                  specialization:
1194
1195                    template <class T> void foo(T);
1196                    class S { friend void foo<>(int) };
1197                    template <> void foo(int);
1198
1199                  We transform the existing DECL in place so that any
1200                  pointers to it become pointers to the updated
1201                  declaration.
1202
1203                  If there was a definition for the template, but not
1204                  for the specialization, we want this to look as if
1205                  there were no definition, and vice versa.  */
1206               DECL_INITIAL (fn) = NULL_TREE;
1207               duplicate_decls (spec, fn, is_friend);
1208               /* The call to duplicate_decls will have applied
1209                  [temp.expl.spec]:
1210
1211                    An explicit specialization of a function template
1212                    is inline only if it is explicitly declared to be,
1213                    and independently of whether its function template
1214                    is.
1215
1216                 to the primary function; now copy the inline bits to
1217                 the various clones.  */
1218               FOR_EACH_CLONE (clone, fn)
1219                 {
1220                   DECL_DECLARED_INLINE_P (clone)
1221                     = DECL_DECLARED_INLINE_P (fn);
1222                   DECL_INLINE (clone)
1223                     = DECL_INLINE (fn);
1224                 }
1225               check_specialization_namespace (fn);
1226
1227               return fn;
1228             }
1229         }
1230       else if (DECL_TEMPLATE_SPECIALIZATION (fn))
1231         {
1232           if (!duplicate_decls (spec, fn, is_friend) && DECL_INITIAL (spec))
1233             /* Dup decl failed, but this is a new definition. Set the
1234                line number so any errors match this new
1235                definition.  */
1236             DECL_SOURCE_LOCATION (fn) = DECL_SOURCE_LOCATION (spec);
1237
1238           return fn;
1239         }
1240     }
1241
1242   /* A specialization must be declared in the same namespace as the
1243      template it is specializing.  */
1244   if (DECL_TEMPLATE_SPECIALIZATION (spec)
1245       && !check_specialization_namespace (tmpl))
1246     DECL_CONTEXT (spec) = FROB_CONTEXT (decl_namespace_context (tmpl));
1247
1248   if (!optimize_specialization_lookup_p (tmpl))
1249     DECL_TEMPLATE_SPECIALIZATIONS (tmpl)
1250       = tree_cons (args, spec, DECL_TEMPLATE_SPECIALIZATIONS (tmpl));
1251
1252   return spec;
1253 }
1254
1255 /* Unregister the specialization SPEC as a specialization of TMPL.
1256    Replace it with NEW_SPEC, if NEW_SPEC is non-NULL.  Returns true
1257    if the SPEC was listed as a specialization of TMPL.  */
1258
1259 bool
1260 reregister_specialization (tree spec, tree tmpl, tree new_spec)
1261 {
1262   tree* s;
1263
1264   for (s = &DECL_TEMPLATE_SPECIALIZATIONS (tmpl);
1265        *s != NULL_TREE;
1266        s = &TREE_CHAIN (*s))
1267     if (TREE_VALUE (*s) == spec)
1268       {
1269         if (!new_spec)
1270           *s = TREE_CHAIN (*s);
1271         else
1272           TREE_VALUE (*s) = new_spec;
1273         return 1;
1274       }
1275
1276   return 0;
1277 }
1278
1279 /* Compare an entry in the local specializations hash table P1 (which
1280    is really a pointer to a TREE_LIST) with P2 (which is really a
1281    DECL).  */
1282
1283 static int
1284 eq_local_specializations (const void *p1, const void *p2)
1285 {
1286   return TREE_VALUE ((tree) p1) == (tree) p2;
1287 }
1288
1289 /* Hash P1, an entry in the local specializations table.  */
1290
1291 static hashval_t
1292 hash_local_specialization (const void* p1)
1293 {
1294   return htab_hash_pointer (TREE_VALUE ((tree) p1));
1295 }
1296
1297 /* Like register_specialization, but for local declarations.  We are
1298    registering SPEC, an instantiation of TMPL.  */
1299
1300 static void
1301 register_local_specialization (tree spec, tree tmpl)
1302 {
1303   void **slot;
1304
1305   slot = htab_find_slot_with_hash (local_specializations, tmpl,
1306                                    htab_hash_pointer (tmpl), INSERT);
1307   *slot = build_tree_list (spec, tmpl);
1308 }
1309
1310 /* Print the list of candidate FNS in an error message.  */
1311
1312 void
1313 print_candidates (tree fns)
1314 {
1315   tree fn;
1316
1317   const char *str = "candidates are:";
1318
1319   for (fn = fns; fn != NULL_TREE; fn = TREE_CHAIN (fn))
1320     {
1321       tree f;
1322
1323       for (f = TREE_VALUE (fn); f; f = OVL_NEXT (f))
1324         error ("%s %+#D", str, OVL_CURRENT (f));
1325       str = "               ";
1326     }
1327 }
1328
1329 /* Returns the template (one of the functions given by TEMPLATE_ID)
1330    which can be specialized to match the indicated DECL with the
1331    explicit template args given in TEMPLATE_ID.  The DECL may be
1332    NULL_TREE if none is available.  In that case, the functions in
1333    TEMPLATE_ID are non-members.
1334
1335    If NEED_MEMBER_TEMPLATE is nonzero the function is known to be a
1336    specialization of a member template.
1337
1338    The TEMPLATE_COUNT is the number of references to qualifying
1339    template classes that appeared in the name of the function. See
1340    check_explicit_specialization for a more accurate description.
1341
1342    TSK indicates what kind of template declaration (if any) is being
1343    declared.  TSK_TEMPLATE indicates that the declaration given by
1344    DECL, though a FUNCTION_DECL, has template parameters, and is
1345    therefore a template function.
1346
1347    The template args (those explicitly specified and those deduced)
1348    are output in a newly created vector *TARGS_OUT.
1349
1350    If it is impossible to determine the result, an error message is
1351    issued.  The error_mark_node is returned to indicate failure.  */
1352
1353 static tree
1354 determine_specialization (tree template_id,
1355                           tree decl,
1356                           tree* targs_out,
1357                           int need_member_template,
1358                           int template_count,
1359                           tmpl_spec_kind tsk)
1360 {
1361   tree fns;
1362   tree targs;
1363   tree explicit_targs;
1364   tree candidates = NULL_TREE;
1365   /* A TREE_LIST of templates of which DECL may be a specialization.
1366      The TREE_VALUE of each node is a TEMPLATE_DECL.  The
1367      corresponding TREE_PURPOSE is the set of template arguments that,
1368      when used to instantiate the template, would produce a function
1369      with the signature of DECL.  */
1370   tree templates = NULL_TREE;
1371   int header_count;
1372   struct cp_binding_level *b;
1373
1374   *targs_out = NULL_TREE;
1375
1376   if (template_id == error_mark_node || decl == error_mark_node)
1377     return error_mark_node;
1378
1379   fns = TREE_OPERAND (template_id, 0);
1380   explicit_targs = TREE_OPERAND (template_id, 1);
1381
1382   if (fns == error_mark_node)
1383     return error_mark_node;
1384
1385   /* Check for baselinks.  */
1386   if (BASELINK_P (fns))
1387     fns = BASELINK_FUNCTIONS (fns);
1388
1389   if (!is_overloaded_fn (fns))
1390     {
1391       error ("%qD is not a function template", fns);
1392       return error_mark_node;
1393     }
1394
1395   /* Count the number of template headers specified for this
1396      specialization.  */
1397   header_count = 0;
1398   for (b = current_binding_level;
1399        b->kind == sk_template_parms;
1400        b = b->level_chain)
1401     ++header_count;
1402
1403   for (; fns; fns = OVL_NEXT (fns))
1404     {
1405       tree fn = OVL_CURRENT (fns);
1406
1407       if (TREE_CODE (fn) == TEMPLATE_DECL)
1408         {
1409           tree decl_arg_types;
1410           tree fn_arg_types;
1411
1412           /* DECL might be a specialization of FN.  */
1413
1414           /* Adjust the type of DECL in case FN is a static member.  */
1415           decl_arg_types = TYPE_ARG_TYPES (TREE_TYPE (decl));
1416           if (DECL_STATIC_FUNCTION_P (fn)
1417               && DECL_NONSTATIC_MEMBER_FUNCTION_P (decl))
1418             decl_arg_types = TREE_CHAIN (decl_arg_types);
1419
1420           /* Check that the number of function parameters matches.
1421              For example,
1422                template <class T> void f(int i = 0);
1423                template <> void f<int>();
1424              The specialization f<int> is invalid but is not caught
1425              by get_bindings below.  */
1426
1427           fn_arg_types = TYPE_ARG_TYPES (TREE_TYPE (fn));
1428           if (list_length (fn_arg_types) != list_length (decl_arg_types))
1429             continue;
1430
1431           /* For a non-static member function, we need to make sure that
1432              the const qualification is the same. This can be done by
1433              checking the 'this' in the argument list.  */
1434           if (DECL_NONSTATIC_MEMBER_FUNCTION_P (fn)
1435               && !same_type_p (TREE_VALUE (fn_arg_types),
1436                                TREE_VALUE (decl_arg_types)))
1437             continue;
1438
1439           /* In case of explicit specialization, we need to check if
1440              the number of template headers appearing in the specialization
1441              is correct. This is usually done in check_explicit_specialization,
1442              but the check done there cannot be exhaustive when specializing
1443              member functions. Consider the following code:
1444
1445              template <> void A<int>::f(int);
1446              template <> template <> void A<int>::f(int);
1447
1448              Assuming that A<int> is not itself an explicit specialization
1449              already, the first line specializes "f" which is a non-template
1450              member function, whilst the second line specializes "f" which
1451              is a template member function. So both lines are syntactically
1452              correct, and check_explicit_specialization does not reject
1453              them.
1454
1455              Here, we can do better, as we are matching the specialization
1456              against the declarations. We count the number of template
1457              headers, and we check if they match TEMPLATE_COUNT + 1
1458              (TEMPLATE_COUNT is the number of qualifying template classes,
1459              plus there must be another header for the member template
1460              itself).
1461
1462              Notice that if header_count is zero, this is not a
1463              specialization but rather a template instantiation, so there
1464              is no check we can perform here.  */
1465           if (header_count && header_count != template_count + 1)
1466             continue;
1467
1468           /* Check that the number of template arguments at the
1469              innermost level for DECL is the same as for FN.  */
1470           if (current_binding_level->kind == sk_template_parms
1471               && !current_binding_level->explicit_spec_p
1472               && (TREE_VEC_LENGTH (DECL_INNERMOST_TEMPLATE_PARMS (fn))
1473                   != TREE_VEC_LENGTH (INNERMOST_TEMPLATE_PARMS
1474                                       (current_template_parms))))
1475             continue;
1476
1477           /* Function templates cannot be specializations; there are
1478              no partial specializations of functions.  Therefore, if
1479              the type of DECL does not match FN, there is no
1480              match.  */
1481           if (tsk == tsk_template)
1482             {
1483               if (compparms (TYPE_ARG_TYPES (TREE_TYPE (fn)),
1484                              decl_arg_types))
1485                 candidates = tree_cons (NULL_TREE, fn, candidates);
1486               continue;
1487             }
1488
1489           /* See whether this function might be a specialization of this
1490              template.  */
1491           targs = get_bindings (fn, decl, explicit_targs, /*check_ret=*/true);
1492
1493           if (!targs)
1494             /* We cannot deduce template arguments that when used to
1495                specialize TMPL will produce DECL.  */
1496             continue;
1497
1498           /* Save this template, and the arguments deduced.  */
1499           templates = tree_cons (targs, fn, templates);
1500         }
1501       else if (need_member_template)
1502         /* FN is an ordinary member function, and we need a
1503            specialization of a member template.  */
1504         ;
1505       else if (TREE_CODE (fn) != FUNCTION_DECL)
1506         /* We can get IDENTIFIER_NODEs here in certain erroneous
1507            cases.  */
1508         ;
1509       else if (!DECL_FUNCTION_MEMBER_P (fn))
1510         /* This is just an ordinary non-member function.  Nothing can
1511            be a specialization of that.  */
1512         ;
1513       else if (DECL_ARTIFICIAL (fn))
1514         /* Cannot specialize functions that are created implicitly.  */
1515         ;
1516       else
1517         {
1518           tree decl_arg_types;
1519
1520           /* This is an ordinary member function.  However, since
1521              we're here, we can assume it's enclosing class is a
1522              template class.  For example,
1523
1524                template <typename T> struct S { void f(); };
1525                template <> void S<int>::f() {}
1526
1527              Here, S<int>::f is a non-template, but S<int> is a
1528              template class.  If FN has the same type as DECL, we
1529              might be in business.  */
1530
1531           if (!DECL_TEMPLATE_INFO (fn))
1532             /* Its enclosing class is an explicit specialization
1533                of a template class.  This is not a candidate.  */
1534             continue;
1535
1536           if (!same_type_p (TREE_TYPE (TREE_TYPE (decl)),
1537                             TREE_TYPE (TREE_TYPE (fn))))
1538             /* The return types differ.  */
1539             continue;
1540
1541           /* Adjust the type of DECL in case FN is a static member.  */
1542           decl_arg_types = TYPE_ARG_TYPES (TREE_TYPE (decl));
1543           if (DECL_STATIC_FUNCTION_P (fn)
1544               && DECL_NONSTATIC_MEMBER_FUNCTION_P (decl))
1545             decl_arg_types = TREE_CHAIN (decl_arg_types);
1546
1547           if (compparms (TYPE_ARG_TYPES (TREE_TYPE (fn)),
1548                          decl_arg_types))
1549             /* They match!  */
1550             candidates = tree_cons (NULL_TREE, fn, candidates);
1551         }
1552     }
1553
1554   if (templates && TREE_CHAIN (templates))
1555     {
1556       /* We have:
1557
1558            [temp.expl.spec]
1559
1560            It is possible for a specialization with a given function
1561            signature to be instantiated from more than one function
1562            template.  In such cases, explicit specification of the
1563            template arguments must be used to uniquely identify the
1564            function template specialization being specialized.
1565
1566          Note that here, there's no suggestion that we're supposed to
1567          determine which of the candidate templates is most
1568          specialized.  However, we, also have:
1569
1570            [temp.func.order]
1571
1572            Partial ordering of overloaded function template
1573            declarations is used in the following contexts to select
1574            the function template to which a function template
1575            specialization refers:
1576
1577            -- when an explicit specialization refers to a function
1578               template.
1579
1580          So, we do use the partial ordering rules, at least for now.
1581          This extension can only serve to make invalid programs valid,
1582          so it's safe.  And, there is strong anecdotal evidence that
1583          the committee intended the partial ordering rules to apply;
1584          the EDG front-end has that behavior, and John Spicer claims
1585          that the committee simply forgot to delete the wording in
1586          [temp.expl.spec].  */
1587       tree tmpl = most_specialized_instantiation (templates);
1588       if (tmpl != error_mark_node)
1589         {
1590           templates = tmpl;
1591           TREE_CHAIN (templates) = NULL_TREE;
1592         }
1593     }
1594
1595   if (templates == NULL_TREE && candidates == NULL_TREE)
1596     {
1597       error ("template-id %qD for %q+D does not match any template "
1598              "declaration", template_id, decl);
1599       return error_mark_node;
1600     }
1601   else if ((templates && TREE_CHAIN (templates))
1602            || (candidates && TREE_CHAIN (candidates))
1603            || (templates && candidates))
1604     {
1605       error ("ambiguous template specialization %qD for %q+D",
1606              template_id, decl);
1607       chainon (candidates, templates);
1608       print_candidates (candidates);
1609       return error_mark_node;
1610     }
1611
1612   /* We have one, and exactly one, match.  */
1613   if (candidates)
1614     {
1615       tree fn = TREE_VALUE (candidates);
1616       /* DECL is a re-declaration of a template function.  */
1617       if (TREE_CODE (fn) == TEMPLATE_DECL)
1618         return fn;
1619       /* It was a specialization of an ordinary member function in a
1620          template class.  */
1621       *targs_out = copy_node (DECL_TI_ARGS (fn));
1622       return DECL_TI_TEMPLATE (fn);
1623     }
1624
1625   /* It was a specialization of a template.  */
1626   targs = DECL_TI_ARGS (DECL_TEMPLATE_RESULT (TREE_VALUE (templates)));
1627   if (TMPL_ARGS_HAVE_MULTIPLE_LEVELS (targs))
1628     {
1629       *targs_out = copy_node (targs);
1630       SET_TMPL_ARGS_LEVEL (*targs_out,
1631                            TMPL_ARGS_DEPTH (*targs_out),
1632                            TREE_PURPOSE (templates));
1633     }
1634   else
1635     *targs_out = TREE_PURPOSE (templates);
1636   return TREE_VALUE (templates);
1637 }
1638
1639 /* Returns a chain of parameter types, exactly like the SPEC_TYPES,
1640    but with the default argument values filled in from those in the
1641    TMPL_TYPES.  */
1642
1643 static tree
1644 copy_default_args_to_explicit_spec_1 (tree spec_types,
1645                                       tree tmpl_types)
1646 {
1647   tree new_spec_types;
1648
1649   if (!spec_types)
1650     return NULL_TREE;
1651
1652   if (spec_types == void_list_node)
1653     return void_list_node;
1654
1655   /* Substitute into the rest of the list.  */
1656   new_spec_types =
1657     copy_default_args_to_explicit_spec_1 (TREE_CHAIN (spec_types),
1658                                           TREE_CHAIN (tmpl_types));
1659
1660   /* Add the default argument for this parameter.  */
1661   return hash_tree_cons (TREE_PURPOSE (tmpl_types),
1662                          TREE_VALUE (spec_types),
1663                          new_spec_types);
1664 }
1665
1666 /* DECL is an explicit specialization.  Replicate default arguments
1667    from the template it specializes.  (That way, code like:
1668
1669      template <class T> void f(T = 3);
1670      template <> void f(double);
1671      void g () { f (); }
1672
1673    works, as required.)  An alternative approach would be to look up
1674    the correct default arguments at the call-site, but this approach
1675    is consistent with how implicit instantiations are handled.  */
1676
1677 static void
1678 copy_default_args_to_explicit_spec (tree decl)
1679 {
1680   tree tmpl;
1681   tree spec_types;
1682   tree tmpl_types;
1683   tree new_spec_types;
1684   tree old_type;
1685   tree new_type;
1686   tree t;
1687   tree object_type = NULL_TREE;
1688   tree in_charge = NULL_TREE;
1689   tree vtt = NULL_TREE;
1690
1691   /* See if there's anything we need to do.  */
1692   tmpl = DECL_TI_TEMPLATE (decl);
1693   tmpl_types = TYPE_ARG_TYPES (TREE_TYPE (DECL_TEMPLATE_RESULT (tmpl)));
1694   for (t = tmpl_types; t; t = TREE_CHAIN (t))
1695     if (TREE_PURPOSE (t))
1696       break;
1697   if (!t)
1698     return;
1699
1700   old_type = TREE_TYPE (decl);
1701   spec_types = TYPE_ARG_TYPES (old_type);
1702
1703   if (DECL_NONSTATIC_MEMBER_FUNCTION_P (decl))
1704     {
1705       /* Remove the this pointer, but remember the object's type for
1706          CV quals.  */
1707       object_type = TREE_TYPE (TREE_VALUE (spec_types));
1708       spec_types = TREE_CHAIN (spec_types);
1709       tmpl_types = TREE_CHAIN (tmpl_types);
1710
1711       if (DECL_HAS_IN_CHARGE_PARM_P (decl))
1712         {
1713           /* DECL may contain more parameters than TMPL due to the extra
1714              in-charge parameter in constructors and destructors.  */
1715           in_charge = spec_types;
1716           spec_types = TREE_CHAIN (spec_types);
1717         }
1718       if (DECL_HAS_VTT_PARM_P (decl))
1719         {
1720           vtt = spec_types;
1721           spec_types = TREE_CHAIN (spec_types);
1722         }
1723     }
1724
1725   /* Compute the merged default arguments.  */
1726   new_spec_types =
1727     copy_default_args_to_explicit_spec_1 (spec_types, tmpl_types);
1728
1729   /* Compute the new FUNCTION_TYPE.  */
1730   if (object_type)
1731     {
1732       if (vtt)
1733         new_spec_types = hash_tree_cons (TREE_PURPOSE (vtt),
1734                                          TREE_VALUE (vtt),
1735                                          new_spec_types);
1736
1737       if (in_charge)
1738         /* Put the in-charge parameter back.  */
1739         new_spec_types = hash_tree_cons (TREE_PURPOSE (in_charge),
1740                                          TREE_VALUE (in_charge),
1741                                          new_spec_types);
1742
1743       new_type = build_method_type_directly (object_type,
1744                                              TREE_TYPE (old_type),
1745                                              new_spec_types);
1746     }
1747   else
1748     new_type = build_function_type (TREE_TYPE (old_type),
1749                                     new_spec_types);
1750   new_type = cp_build_type_attribute_variant (new_type,
1751                                               TYPE_ATTRIBUTES (old_type));
1752   new_type = build_exception_variant (new_type,
1753                                       TYPE_RAISES_EXCEPTIONS (old_type));
1754   TREE_TYPE (decl) = new_type;
1755 }
1756
1757 /* Check to see if the function just declared, as indicated in
1758    DECLARATOR, and in DECL, is a specialization of a function
1759    template.  We may also discover that the declaration is an explicit
1760    instantiation at this point.
1761
1762    Returns DECL, or an equivalent declaration that should be used
1763    instead if all goes well.  Issues an error message if something is
1764    amiss.  Returns error_mark_node if the error is not easily
1765    recoverable.
1766
1767    FLAGS is a bitmask consisting of the following flags:
1768
1769    2: The function has a definition.
1770    4: The function is a friend.
1771
1772    The TEMPLATE_COUNT is the number of references to qualifying
1773    template classes that appeared in the name of the function.  For
1774    example, in
1775
1776      template <class T> struct S { void f(); };
1777      void S<int>::f();
1778
1779    the TEMPLATE_COUNT would be 1.  However, explicitly specialized
1780    classes are not counted in the TEMPLATE_COUNT, so that in
1781
1782      template <class T> struct S {};
1783      template <> struct S<int> { void f(); }
1784      template <> void S<int>::f();
1785
1786    the TEMPLATE_COUNT would be 0.  (Note that this declaration is
1787    invalid; there should be no template <>.)
1788
1789    If the function is a specialization, it is marked as such via
1790    DECL_TEMPLATE_SPECIALIZATION.  Furthermore, its DECL_TEMPLATE_INFO
1791    is set up correctly, and it is added to the list of specializations
1792    for that template.  */
1793
1794 tree
1795 check_explicit_specialization (tree declarator,
1796                                tree decl,
1797                                int template_count,
1798                                int flags)
1799 {
1800   int have_def = flags & 2;
1801   int is_friend = flags & 4;
1802   int specialization = 0;
1803   int explicit_instantiation = 0;
1804   int member_specialization = 0;
1805   tree ctype = DECL_CLASS_CONTEXT (decl);
1806   tree dname = DECL_NAME (decl);
1807   tmpl_spec_kind tsk;
1808
1809   if (is_friend)
1810     {
1811       if (!processing_specialization)
1812         tsk = tsk_none;
1813       else
1814         tsk = tsk_excessive_parms;
1815     }
1816   else
1817     tsk = current_tmpl_spec_kind (template_count);
1818
1819   switch (tsk)
1820     {
1821     case tsk_none:
1822       if (processing_specialization)
1823         {
1824           specialization = 1;
1825           SET_DECL_TEMPLATE_SPECIALIZATION (decl);
1826         }
1827       else if (TREE_CODE (declarator) == TEMPLATE_ID_EXPR)
1828         {
1829           if (is_friend)
1830             /* This could be something like:
1831
1832                template <class T> void f(T);
1833                class S { friend void f<>(int); }  */
1834             specialization = 1;
1835           else
1836             {
1837               /* This case handles bogus declarations like template <>
1838                  template <class T> void f<int>(); */
1839
1840               error ("template-id %qD in declaration of primary template",
1841                      declarator);
1842               return decl;
1843             }
1844         }
1845       break;
1846
1847     case tsk_invalid_member_spec:
1848       /* The error has already been reported in
1849          check_specialization_scope.  */
1850       return error_mark_node;
1851
1852     case tsk_invalid_expl_inst:
1853       error ("template parameter list used in explicit instantiation");
1854
1855       /* Fall through.  */
1856
1857     case tsk_expl_inst:
1858       if (have_def)
1859         error ("definition provided for explicit instantiation");
1860
1861       explicit_instantiation = 1;
1862       break;
1863
1864     case tsk_excessive_parms:
1865     case tsk_insufficient_parms:
1866       if (tsk == tsk_excessive_parms)
1867         error ("too many template parameter lists in declaration of %qD",
1868                decl);
1869       else if (template_header_count)
1870         error("too few template parameter lists in declaration of %qD", decl);
1871       else
1872         error("explicit specialization of %qD must be introduced by "
1873               "%<template <>%>", decl);
1874
1875       /* Fall through.  */
1876     case tsk_expl_spec:
1877       SET_DECL_TEMPLATE_SPECIALIZATION (decl);
1878       if (ctype)
1879         member_specialization = 1;
1880       else
1881         specialization = 1;
1882       break;
1883
1884     case tsk_template:
1885       if (TREE_CODE (declarator) == TEMPLATE_ID_EXPR)
1886         {
1887           /* This case handles bogus declarations like template <>
1888              template <class T> void f<int>(); */
1889
1890           if (uses_template_parms (declarator))
1891             error ("function template partial specialization %qD "
1892                    "is not allowed", declarator);
1893           else
1894             error ("template-id %qD in declaration of primary template",
1895                    declarator);
1896           return decl;
1897         }
1898
1899       if (ctype && CLASSTYPE_TEMPLATE_INSTANTIATION (ctype))
1900         /* This is a specialization of a member template, without
1901            specialization the containing class.  Something like:
1902
1903              template <class T> struct S {
1904                template <class U> void f (U);
1905              };
1906              template <> template <class U> void S<int>::f(U) {}
1907
1908            That's a specialization -- but of the entire template.  */
1909         specialization = 1;
1910       break;
1911
1912     default:
1913       gcc_unreachable ();
1914     }
1915
1916   if (specialization || member_specialization)
1917     {
1918       tree t = TYPE_ARG_TYPES (TREE_TYPE (decl));
1919       for (; t; t = TREE_CHAIN (t))
1920         if (TREE_PURPOSE (t))
1921           {
1922             pedwarn
1923               ("default argument specified in explicit specialization");
1924             break;
1925           }
1926     }
1927
1928   if (specialization || member_specialization || explicit_instantiation)
1929     {
1930       tree tmpl = NULL_TREE;
1931       tree targs = NULL_TREE;
1932
1933       /* Make sure that the declarator is a TEMPLATE_ID_EXPR.  */
1934       if (TREE_CODE (declarator) != TEMPLATE_ID_EXPR)
1935         {
1936           tree fns;
1937
1938           gcc_assert (TREE_CODE (declarator) == IDENTIFIER_NODE);
1939           if (ctype)
1940             fns = dname;
1941           else
1942             {
1943               /* If there is no class context, the explicit instantiation
1944                  must be at namespace scope.  */
1945               gcc_assert (DECL_NAMESPACE_SCOPE_P (decl));
1946
1947               /* Find the namespace binding, using the declaration
1948                  context.  */
1949               fns = lookup_qualified_name (CP_DECL_CONTEXT (decl), dname,
1950                                            false, true);
1951               if (!fns || !is_overloaded_fn (fns))
1952                 {
1953                   error ("%qD is not a template function", dname);
1954                   fns = error_mark_node;
1955                 }
1956               else
1957                 {
1958                   tree fn = OVL_CURRENT (fns);
1959                   if (!is_associated_namespace (CP_DECL_CONTEXT (decl),
1960                                                 CP_DECL_CONTEXT (fn)))
1961                     error ("%qD is not declared in %qD",
1962                            decl, current_namespace);
1963                 }
1964             }
1965
1966           declarator = lookup_template_function (fns, NULL_TREE);
1967         }
1968
1969       if (declarator == error_mark_node)
1970         return error_mark_node;
1971
1972       if (ctype != NULL_TREE && TYPE_BEING_DEFINED (ctype))
1973         {
1974           if (!explicit_instantiation)
1975             /* A specialization in class scope.  This is invalid,
1976                but the error will already have been flagged by
1977                check_specialization_scope.  */
1978             return error_mark_node;
1979           else
1980             {
1981               /* It's not valid to write an explicit instantiation in
1982                  class scope, e.g.:
1983
1984                    class C { template void f(); }
1985
1986                    This case is caught by the parser.  However, on
1987                    something like:
1988
1989                    template class C { void f(); };
1990
1991                    (which is invalid) we can get here.  The error will be
1992                    issued later.  */
1993               ;
1994             }
1995
1996           return decl;
1997         }
1998       else if (ctype != NULL_TREE
1999                && (TREE_CODE (TREE_OPERAND (declarator, 0)) ==
2000                    IDENTIFIER_NODE))
2001         {
2002           /* Find the list of functions in ctype that have the same
2003              name as the declared function.  */
2004           tree name = TREE_OPERAND (declarator, 0);
2005           tree fns = NULL_TREE;
2006           int idx;
2007
2008           if (constructor_name_p (name, ctype))
2009             {
2010               int is_constructor = DECL_CONSTRUCTOR_P (decl);
2011
2012               if (is_constructor ? !TYPE_HAS_CONSTRUCTOR (ctype)
2013                   : !CLASSTYPE_DESTRUCTORS (ctype))
2014                 {
2015                   /* From [temp.expl.spec]:
2016
2017                      If such an explicit specialization for the member
2018                      of a class template names an implicitly-declared
2019                      special member function (clause _special_), the
2020                      program is ill-formed.
2021
2022                      Similar language is found in [temp.explicit].  */
2023                   error ("specialization of implicitly-declared special member function");
2024                   return error_mark_node;
2025                 }
2026
2027               name = is_constructor ? ctor_identifier : dtor_identifier;
2028             }
2029
2030           if (!DECL_CONV_FN_P (decl))
2031             {
2032               idx = lookup_fnfields_1 (ctype, name);
2033               if (idx >= 0)
2034                 fns = VEC_index (tree, CLASSTYPE_METHOD_VEC (ctype), idx);
2035             }
2036           else
2037             {
2038               VEC(tree,gc) *methods;
2039               tree ovl;
2040
2041               /* For a type-conversion operator, we cannot do a
2042                  name-based lookup.  We might be looking for `operator
2043                  int' which will be a specialization of `operator T'.
2044                  So, we find *all* the conversion operators, and then
2045                  select from them.  */
2046               fns = NULL_TREE;
2047
2048               methods = CLASSTYPE_METHOD_VEC (ctype);
2049               if (methods)
2050                 for (idx = CLASSTYPE_FIRST_CONVERSION_SLOT;
2051                      VEC_iterate (tree, methods, idx, ovl);
2052                      ++idx)
2053                   {
2054                     if (!DECL_CONV_FN_P (OVL_CURRENT (ovl)))
2055                       /* There are no more conversion functions.  */
2056                       break;
2057
2058                     /* Glue all these conversion functions together
2059                        with those we already have.  */
2060                     for (; ovl; ovl = OVL_NEXT (ovl))
2061                       fns = ovl_cons (OVL_CURRENT (ovl), fns);
2062                   }
2063             }
2064
2065           if (fns == NULL_TREE)
2066             {
2067               error ("no member function %qD declared in %qT", name, ctype);
2068               return error_mark_node;
2069             }
2070           else
2071             TREE_OPERAND (declarator, 0) = fns;
2072         }
2073
2074       /* Figure out what exactly is being specialized at this point.
2075          Note that for an explicit instantiation, even one for a
2076          member function, we cannot tell apriori whether the
2077          instantiation is for a member template, or just a member
2078          function of a template class.  Even if a member template is
2079          being instantiated, the member template arguments may be
2080          elided if they can be deduced from the rest of the
2081          declaration.  */
2082       tmpl = determine_specialization (declarator, decl,
2083                                        &targs,
2084                                        member_specialization,
2085                                        template_count,
2086                                        tsk);
2087
2088       if (!tmpl || tmpl == error_mark_node)
2089         /* We couldn't figure out what this declaration was
2090            specializing.  */
2091         return error_mark_node;
2092       else
2093         {
2094           tree gen_tmpl = most_general_template (tmpl);
2095
2096           if (explicit_instantiation)
2097             {
2098               /* We don't set DECL_EXPLICIT_INSTANTIATION here; that
2099                  is done by do_decl_instantiation later.  */
2100
2101               int arg_depth = TMPL_ARGS_DEPTH (targs);
2102               int parm_depth = TMPL_PARMS_DEPTH (DECL_TEMPLATE_PARMS (tmpl));
2103
2104               if (arg_depth > parm_depth)
2105                 {
2106                   /* If TMPL is not the most general template (for
2107                      example, if TMPL is a friend template that is
2108                      injected into namespace scope), then there will
2109                      be too many levels of TARGS.  Remove some of them
2110                      here.  */
2111                   int i;
2112                   tree new_targs;
2113
2114                   new_targs = make_tree_vec (parm_depth);
2115                   for (i = arg_depth - parm_depth; i < arg_depth; ++i)
2116                     TREE_VEC_ELT (new_targs, i - (arg_depth - parm_depth))
2117                       = TREE_VEC_ELT (targs, i);
2118                   targs = new_targs;
2119                 }
2120
2121               return instantiate_template (tmpl, targs, tf_error);
2122             }
2123
2124           /* If we thought that the DECL was a member function, but it
2125              turns out to be specializing a static member function,
2126              make DECL a static member function as well.  */
2127           if (DECL_STATIC_FUNCTION_P (tmpl)
2128               && DECL_NONSTATIC_MEMBER_FUNCTION_P (decl))
2129             revert_static_member_fn (decl);
2130
2131           /* If this is a specialization of a member template of a
2132              template class, we want to return the TEMPLATE_DECL, not
2133              the specialization of it.  */
2134           if (tsk == tsk_template)
2135             {
2136               SET_DECL_TEMPLATE_SPECIALIZATION (tmpl);
2137               DECL_INITIAL (DECL_TEMPLATE_RESULT (tmpl)) = NULL_TREE;
2138               if (have_def)
2139                 {
2140                   DECL_SOURCE_LOCATION (tmpl) = DECL_SOURCE_LOCATION (decl);
2141                   DECL_SOURCE_LOCATION (DECL_TEMPLATE_RESULT (tmpl))
2142                     = DECL_SOURCE_LOCATION (decl);
2143                   /* We want to use the argument list specified in the
2144                      definition, not in the original declaration.  */
2145                   DECL_ARGUMENTS (DECL_TEMPLATE_RESULT (tmpl))
2146                     = DECL_ARGUMENTS (decl);
2147                 }
2148               return tmpl;
2149             }
2150
2151           /* Set up the DECL_TEMPLATE_INFO for DECL.  */
2152           DECL_TEMPLATE_INFO (decl) = tree_cons (tmpl, targs, NULL_TREE);
2153
2154           /* Inherit default function arguments from the template
2155              DECL is specializing.  */
2156           copy_default_args_to_explicit_spec (decl);
2157
2158           /* This specialization has the same protection as the
2159              template it specializes.  */
2160           TREE_PRIVATE (decl) = TREE_PRIVATE (gen_tmpl);
2161           TREE_PROTECTED (decl) = TREE_PROTECTED (gen_tmpl);
2162
2163           /* If DECL is a friend declaration, declared using an
2164              unqualified name, the namespace associated with DECL may
2165              have been set incorrectly.  For example, in:
2166
2167                template <typename T> void f(T);
2168                namespace N {
2169                  struct S { friend void f<int>(int); }
2170                }
2171
2172              we will have set the DECL_CONTEXT for the friend
2173              declaration to N, rather than to the global namespace.  */
2174           if (DECL_NAMESPACE_SCOPE_P (decl))
2175             DECL_CONTEXT (decl) = DECL_CONTEXT (tmpl);
2176
2177           if (is_friend && !have_def)
2178             /* This is not really a declaration of a specialization.
2179                It's just the name of an instantiation.  But, it's not
2180                a request for an instantiation, either.  */
2181             SET_DECL_IMPLICIT_INSTANTIATION (decl);
2182           else if (DECL_CONSTRUCTOR_P (decl) || DECL_DESTRUCTOR_P (decl))
2183             /* This is indeed a specialization.  In case of constructors
2184                and destructors, we need in-charge and not-in-charge
2185                versions in V3 ABI.  */
2186             clone_function_decl (decl, /*update_method_vec_p=*/0);
2187
2188           /* Register this specialization so that we can find it
2189              again.  */
2190           decl = register_specialization (decl, gen_tmpl, targs, is_friend);
2191         }
2192     }
2193
2194   return decl;
2195 }
2196
2197 /* Returns 1 iff PARMS1 and PARMS2 are identical sets of template
2198    parameters.  These are represented in the same format used for
2199    DECL_TEMPLATE_PARMS.  */
2200
2201 int
2202 comp_template_parms (tree parms1, tree parms2)
2203 {
2204   tree p1;
2205   tree p2;
2206
2207   if (parms1 == parms2)
2208     return 1;
2209
2210   for (p1 = parms1, p2 = parms2;
2211        p1 != NULL_TREE && p2 != NULL_TREE;
2212        p1 = TREE_CHAIN (p1), p2 = TREE_CHAIN (p2))
2213     {
2214       tree t1 = TREE_VALUE (p1);
2215       tree t2 = TREE_VALUE (p2);
2216       int i;
2217
2218       gcc_assert (TREE_CODE (t1) == TREE_VEC);
2219       gcc_assert (TREE_CODE (t2) == TREE_VEC);
2220
2221       if (TREE_VEC_LENGTH (t1) != TREE_VEC_LENGTH (t2))
2222         return 0;
2223
2224       for (i = 0; i < TREE_VEC_LENGTH (t2); ++i)
2225         {
2226           tree parm1 = TREE_VALUE (TREE_VEC_ELT (t1, i));
2227           tree parm2 = TREE_VALUE (TREE_VEC_ELT (t2, i));
2228
2229           /* If either of the template parameters are invalid, assume
2230              they match for the sake of error recovery. */
2231           if (parm1 == error_mark_node || parm2 == error_mark_node)
2232             return 1;
2233
2234           if (TREE_CODE (parm1) != TREE_CODE (parm2))
2235             return 0;
2236
2237           if (TREE_CODE (parm1) == TEMPLATE_TYPE_PARM)
2238             continue;
2239           else if (!same_type_p (TREE_TYPE (parm1), TREE_TYPE (parm2)))
2240             return 0;
2241         }
2242     }
2243
2244   if ((p1 != NULL_TREE) != (p2 != NULL_TREE))
2245     /* One set of parameters has more parameters lists than the
2246        other.  */
2247     return 0;
2248
2249   return 1;
2250 }
2251
2252 /* Complain if DECL shadows a template parameter.
2253
2254    [temp.local]: A template-parameter shall not be redeclared within its
2255    scope (including nested scopes).  */
2256
2257 void
2258 check_template_shadow (tree decl)
2259 {
2260   tree olddecl;
2261
2262   /* If we're not in a template, we can't possibly shadow a template
2263      parameter.  */
2264   if (!current_template_parms)
2265     return;
2266
2267   /* Figure out what we're shadowing.  */
2268   if (TREE_CODE (decl) == OVERLOAD)
2269     decl = OVL_CURRENT (decl);
2270   olddecl = innermost_non_namespace_value (DECL_NAME (decl));
2271
2272   /* If there's no previous binding for this name, we're not shadowing
2273      anything, let alone a template parameter.  */
2274   if (!olddecl)
2275     return;
2276
2277   /* If we're not shadowing a template parameter, we're done.  Note
2278      that OLDDECL might be an OVERLOAD (or perhaps even an
2279      ERROR_MARK), so we can't just blithely assume it to be a _DECL
2280      node.  */
2281   if (!DECL_P (olddecl) || !DECL_TEMPLATE_PARM_P (olddecl))
2282     return;
2283
2284   /* We check for decl != olddecl to avoid bogus errors for using a
2285      name inside a class.  We check TPFI to avoid duplicate errors for
2286      inline member templates.  */
2287   if (decl == olddecl
2288       || TEMPLATE_PARMS_FOR_INLINE (current_template_parms))
2289     return;
2290
2291   error ("declaration of %q+#D", decl);
2292   error (" shadows template parm %q+#D", olddecl);
2293 }
2294
2295 /* Return a new TEMPLATE_PARM_INDEX with the indicated INDEX, LEVEL,
2296    ORIG_LEVEL, DECL, and TYPE.  */
2297
2298 static tree
2299 build_template_parm_index (int index,
2300                            int level,
2301                            int orig_level,
2302                            tree decl,
2303                            tree type)
2304 {
2305   tree t = make_node (TEMPLATE_PARM_INDEX);
2306   TEMPLATE_PARM_IDX (t) = index;
2307   TEMPLATE_PARM_LEVEL (t) = level;
2308   TEMPLATE_PARM_ORIG_LEVEL (t) = orig_level;
2309   TEMPLATE_PARM_DECL (t) = decl;
2310   TREE_TYPE (t) = type;
2311   TREE_CONSTANT (t) = TREE_CONSTANT (decl);
2312   TREE_INVARIANT (t) = TREE_INVARIANT (decl);
2313   TREE_READONLY (t) = TREE_READONLY (decl);
2314
2315   return t;
2316 }
2317
2318 /* Return a TEMPLATE_PARM_INDEX, similar to INDEX, but whose
2319    TEMPLATE_PARM_LEVEL has been decreased by LEVELS.  If such a
2320    TEMPLATE_PARM_INDEX already exists, it is returned; otherwise, a
2321    new one is created.  */
2322
2323 static tree
2324 reduce_template_parm_level (tree index, tree type, int levels)
2325 {
2326   if (TEMPLATE_PARM_DESCENDANTS (index) == NULL_TREE
2327       || (TEMPLATE_PARM_LEVEL (TEMPLATE_PARM_DESCENDANTS (index))
2328           != TEMPLATE_PARM_LEVEL (index) - levels))
2329     {
2330       tree orig_decl = TEMPLATE_PARM_DECL (index);
2331       tree decl, t;
2332
2333       decl = build_decl (TREE_CODE (orig_decl), DECL_NAME (orig_decl), type);
2334       TREE_CONSTANT (decl) = TREE_CONSTANT (orig_decl);
2335       TREE_INVARIANT (decl) = TREE_INVARIANT (orig_decl);
2336       TREE_READONLY (decl) = TREE_READONLY (orig_decl);
2337       DECL_ARTIFICIAL (decl) = 1;
2338       SET_DECL_TEMPLATE_PARM_P (decl);
2339
2340       t = build_template_parm_index (TEMPLATE_PARM_IDX (index),
2341                                      TEMPLATE_PARM_LEVEL (index) - levels,
2342                                      TEMPLATE_PARM_ORIG_LEVEL (index),
2343                                      decl, type);
2344       TEMPLATE_PARM_DESCENDANTS (index) = t;
2345
2346         /* Template template parameters need this.  */
2347       if (TREE_CODE (decl) != CONST_DECL)
2348         DECL_TEMPLATE_PARMS (decl)
2349           = DECL_TEMPLATE_PARMS (TEMPLATE_PARM_DECL (index));
2350     }
2351
2352   return TEMPLATE_PARM_DESCENDANTS (index);
2353 }
2354
2355 /* Process information from new template parameter PARM and append it to the
2356    LIST being built.  This new parameter is a non-type parameter iff
2357    IS_NON_TYPE is true.  */
2358
2359 tree
2360 process_template_parm (tree list, tree parm, bool is_non_type)
2361 {
2362   tree decl = 0;
2363   tree defval;
2364   tree err_parm_list;
2365   int idx = 0;
2366
2367   gcc_assert (TREE_CODE (parm) == TREE_LIST);
2368   defval = TREE_PURPOSE (parm);
2369
2370   if (list)
2371     {
2372       tree p = tree_last (list);
2373
2374       if (p && TREE_VALUE (p) != error_mark_node)
2375         {
2376           p = TREE_VALUE (p);
2377           if (TREE_CODE (p) == TYPE_DECL || TREE_CODE (p) == TEMPLATE_DECL)
2378             idx = TEMPLATE_TYPE_IDX (TREE_TYPE (p));
2379           else
2380             idx = TEMPLATE_PARM_IDX (DECL_INITIAL (p));
2381         }
2382
2383       ++idx;
2384     }
2385   else
2386     idx = 0;
2387
2388   if (is_non_type)
2389     {
2390       parm = TREE_VALUE (parm);
2391
2392       SET_DECL_TEMPLATE_PARM_P (parm);
2393
2394       if (TREE_TYPE (parm) == error_mark_node)
2395         {
2396           err_parm_list = build_tree_list (defval, parm);
2397           TREE_VALUE (err_parm_list) = error_mark_node;
2398            return chainon (list, err_parm_list);
2399         }
2400       else
2401       {
2402         /* [temp.param]
2403
2404            The top-level cv-qualifiers on the template-parameter are
2405            ignored when determining its type.  */
2406         TREE_TYPE (parm) = TYPE_MAIN_VARIANT (TREE_TYPE (parm));
2407         if (invalid_nontype_parm_type_p (TREE_TYPE (parm), 1))
2408           {
2409             err_parm_list = build_tree_list (defval, parm);
2410             TREE_VALUE (err_parm_list) = error_mark_node;
2411              return chainon (list, err_parm_list);
2412           }
2413       }
2414
2415       /* A template parameter is not modifiable.  */
2416       TREE_CONSTANT (parm) = 1;
2417       TREE_INVARIANT (parm) = 1;
2418       TREE_READONLY (parm) = 1;
2419       decl = build_decl (CONST_DECL, DECL_NAME (parm), TREE_TYPE (parm));
2420       TREE_CONSTANT (decl) = 1;
2421       TREE_INVARIANT (decl) = 1;
2422       TREE_READONLY (decl) = 1;
2423       DECL_INITIAL (parm) = DECL_INITIAL (decl)
2424         = build_template_parm_index (idx, processing_template_decl,
2425                                      processing_template_decl,
2426                                      decl, TREE_TYPE (parm));
2427     }
2428   else
2429     {
2430       tree t;
2431       parm = TREE_VALUE (TREE_VALUE (parm));
2432
2433       if (parm && TREE_CODE (parm) == TEMPLATE_DECL)
2434         {
2435           t = make_aggr_type (TEMPLATE_TEMPLATE_PARM);
2436           /* This is for distinguishing between real templates and template
2437              template parameters */
2438           TREE_TYPE (parm) = t;
2439           TREE_TYPE (DECL_TEMPLATE_RESULT (parm)) = t;
2440           decl = parm;
2441         }
2442       else
2443         {
2444           t = make_aggr_type (TEMPLATE_TYPE_PARM);
2445           /* parm is either IDENTIFIER_NODE or NULL_TREE.  */
2446           decl = build_decl (TYPE_DECL, parm, t);
2447         }
2448
2449       TYPE_NAME (t) = decl;
2450       TYPE_STUB_DECL (t) = decl;
2451       parm = decl;
2452       TEMPLATE_TYPE_PARM_INDEX (t)
2453         = build_template_parm_index (idx, processing_template_decl,
2454                                      processing_template_decl,
2455                                      decl, TREE_TYPE (parm));
2456     }
2457   DECL_ARTIFICIAL (decl) = 1;
2458   SET_DECL_TEMPLATE_PARM_P (decl);
2459   pushdecl (decl);
2460   parm = build_tree_list (defval, parm);
2461   return chainon (list, parm);
2462 }
2463
2464 /* The end of a template parameter list has been reached.  Process the
2465    tree list into a parameter vector, converting each parameter into a more
2466    useful form.  Type parameters are saved as IDENTIFIER_NODEs, and others
2467    as PARM_DECLs.  */
2468
2469 tree
2470 end_template_parm_list (tree parms)
2471 {
2472   int nparms;
2473   tree parm, next;
2474   tree saved_parmlist = make_tree_vec (list_length (parms));
2475
2476   current_template_parms
2477     = tree_cons (size_int (processing_template_decl),
2478                  saved_parmlist, current_template_parms);
2479
2480   for (parm = parms, nparms = 0; parm; parm = next, nparms++)
2481     {
2482       next = TREE_CHAIN (parm);
2483       TREE_VEC_ELT (saved_parmlist, nparms) = parm;
2484       TREE_CHAIN (parm) = NULL_TREE;
2485     }
2486
2487   --processing_template_parmlist;
2488
2489   return saved_parmlist;
2490 }
2491
2492 /* end_template_decl is called after a template declaration is seen.  */
2493
2494 void
2495 end_template_decl (void)
2496 {
2497   reset_specialization ();
2498
2499   if (! processing_template_decl)
2500     return;
2501
2502   /* This matches the pushlevel in begin_template_parm_list.  */
2503   finish_scope ();
2504
2505   --processing_template_decl;
2506   current_template_parms = TREE_CHAIN (current_template_parms);
2507 }
2508
2509 /* Given a template argument vector containing the template PARMS.
2510    The innermost PARMS are given first.  */
2511
2512 static tree
2513 current_template_args (void)
2514 {
2515   tree header;
2516   tree args = NULL_TREE;
2517   int length = TMPL_PARMS_DEPTH (current_template_parms);
2518   int l = length;
2519
2520   /* If there is only one level of template parameters, we do not
2521      create a TREE_VEC of TREE_VECs.  Instead, we return a single
2522      TREE_VEC containing the arguments.  */
2523   if (length > 1)
2524     args = make_tree_vec (length);
2525
2526   for (header = current_template_parms; header; header = TREE_CHAIN (header))
2527     {
2528       tree a = copy_node (TREE_VALUE (header));
2529       int i;
2530
2531       TREE_TYPE (a) = NULL_TREE;
2532       for (i = TREE_VEC_LENGTH (a) - 1; i >= 0; --i)
2533         {
2534           tree t = TREE_VEC_ELT (a, i);
2535
2536           /* T will be a list if we are called from within a
2537              begin/end_template_parm_list pair, but a vector directly
2538              if within a begin/end_member_template_processing pair.  */
2539           if (TREE_CODE (t) == TREE_LIST)
2540             {
2541               t = TREE_VALUE (t);
2542
2543               if (t != error_mark_node)
2544                 {
2545                   if (TREE_CODE (t) == TYPE_DECL
2546                       || TREE_CODE (t) == TEMPLATE_DECL)
2547                     t = TREE_TYPE (t);
2548                   else
2549                     t = DECL_INITIAL (t);
2550                 }
2551
2552               TREE_VEC_ELT (a, i) = t;
2553             }
2554         }
2555
2556       if (length > 1)
2557         TREE_VEC_ELT (args, --l) = a;
2558       else
2559         args = a;
2560     }
2561
2562   return args;
2563 }
2564
2565 /* Return a TEMPLATE_DECL corresponding to DECL, using the indicated
2566    template PARMS.  If MEMBER_TEMPLATE_P is true, the new template is
2567    a member template.  Used by push_template_decl below.  */
2568
2569 static tree
2570 build_template_decl (tree decl, tree parms, bool member_template_p)
2571 {
2572   tree tmpl = build_lang_decl (TEMPLATE_DECL, DECL_NAME (decl), NULL_TREE);
2573   DECL_TEMPLATE_PARMS (tmpl) = parms;
2574   DECL_CONTEXT (tmpl) = DECL_CONTEXT (decl);
2575   DECL_MEMBER_TEMPLATE_P (tmpl) = member_template_p;
2576   if (DECL_LANG_SPECIFIC (decl))
2577     {
2578       DECL_STATIC_FUNCTION_P (tmpl) = DECL_STATIC_FUNCTION_P (decl);
2579       DECL_CONSTRUCTOR_P (tmpl) = DECL_CONSTRUCTOR_P (decl);
2580       DECL_DESTRUCTOR_P (tmpl) = DECL_DESTRUCTOR_P (decl);
2581       DECL_NONCONVERTING_P (tmpl) = DECL_NONCONVERTING_P (decl);
2582       DECL_ASSIGNMENT_OPERATOR_P (tmpl) = DECL_ASSIGNMENT_OPERATOR_P (decl);
2583       if (DECL_OVERLOADED_OPERATOR_P (decl))
2584         SET_OVERLOADED_OPERATOR_CODE (tmpl,
2585                                       DECL_OVERLOADED_OPERATOR_P (decl));
2586     }
2587
2588   return tmpl;
2589 }
2590
2591 struct template_parm_data
2592 {
2593   /* The level of the template parameters we are currently
2594      processing.  */
2595   int level;
2596
2597   /* The index of the specialization argument we are currently
2598      processing.  */
2599   int current_arg;
2600
2601   /* An array whose size is the number of template parameters.  The
2602      elements are nonzero if the parameter has been used in any one
2603      of the arguments processed so far.  */
2604   int* parms;
2605
2606   /* An array whose size is the number of template arguments.  The
2607      elements are nonzero if the argument makes use of template
2608      parameters of this level.  */
2609   int* arg_uses_template_parms;
2610 };
2611
2612 /* Subroutine of push_template_decl used to see if each template
2613    parameter in a partial specialization is used in the explicit
2614    argument list.  If T is of the LEVEL given in DATA (which is
2615    treated as a template_parm_data*), then DATA->PARMS is marked
2616    appropriately.  */
2617
2618 static int
2619 mark_template_parm (tree t, void* data)
2620 {
2621   int level;
2622   int idx;
2623   struct template_parm_data* tpd = (struct template_parm_data*) data;
2624
2625   if (TREE_CODE (t) == TEMPLATE_PARM_INDEX)
2626     {
2627       level = TEMPLATE_PARM_LEVEL (t);
2628       idx = TEMPLATE_PARM_IDX (t);
2629     }
2630   else
2631     {
2632       level = TEMPLATE_TYPE_LEVEL (t);
2633       idx = TEMPLATE_TYPE_IDX (t);
2634     }
2635
2636   if (level == tpd->level)
2637     {
2638       tpd->parms[idx] = 1;
2639       tpd->arg_uses_template_parms[tpd->current_arg] = 1;
2640     }
2641
2642   /* Return zero so that for_each_template_parm will continue the
2643      traversal of the tree; we want to mark *every* template parm.  */
2644   return 0;
2645 }
2646
2647 /* Process the partial specialization DECL.  */
2648
2649 static tree
2650 process_partial_specialization (tree decl)
2651 {
2652   tree type = TREE_TYPE (decl);
2653   tree maintmpl = CLASSTYPE_TI_TEMPLATE (type);
2654   tree specargs = CLASSTYPE_TI_ARGS (type);
2655   tree inner_args = INNERMOST_TEMPLATE_ARGS (specargs);
2656   tree inner_parms = INNERMOST_TEMPLATE_PARMS (current_template_parms);
2657   tree main_inner_parms = DECL_INNERMOST_TEMPLATE_PARMS (maintmpl);
2658   int nargs = TREE_VEC_LENGTH (inner_args);
2659   int ntparms = TREE_VEC_LENGTH (inner_parms);
2660   int  i;
2661   int did_error_intro = 0;
2662   struct template_parm_data tpd;
2663   struct template_parm_data tpd2;
2664
2665   /* We check that each of the template parameters given in the
2666      partial specialization is used in the argument list to the
2667      specialization.  For example:
2668
2669        template <class T> struct S;
2670        template <class T> struct S<T*>;
2671
2672      The second declaration is OK because `T*' uses the template
2673      parameter T, whereas
2674
2675        template <class T> struct S<int>;
2676
2677      is no good.  Even trickier is:
2678
2679        template <class T>
2680        struct S1
2681        {
2682           template <class U>
2683           struct S2;
2684           template <class U>
2685           struct S2<T>;
2686        };
2687
2688      The S2<T> declaration is actually invalid; it is a
2689      full-specialization.  Of course,
2690
2691           template <class U>
2692           struct S2<T (*)(U)>;
2693
2694      or some such would have been OK.  */
2695   tpd.level = TMPL_PARMS_DEPTH (current_template_parms);
2696   tpd.parms = (int *) alloca (sizeof (int) * ntparms);
2697   memset (tpd.parms, 0, sizeof (int) * ntparms);
2698
2699   tpd.arg_uses_template_parms = (int *) alloca (sizeof (int) * nargs);
2700   memset (tpd.arg_uses_template_parms, 0, sizeof (int) * nargs);
2701   for (i = 0; i < nargs; ++i)
2702     {
2703       tpd.current_arg = i;
2704       for_each_template_parm (TREE_VEC_ELT (inner_args, i),
2705                               &mark_template_parm,
2706                               &tpd,
2707                               NULL);
2708     }
2709   for (i = 0; i < ntparms; ++i)
2710     if (tpd.parms[i] == 0)
2711       {
2712         /* One of the template parms was not used in the
2713            specialization.  */
2714         if (!did_error_intro)
2715           {
2716             error ("template parameters not used in partial specialization:");
2717             did_error_intro = 1;
2718           }
2719
2720         error ("        %qD", TREE_VALUE (TREE_VEC_ELT (inner_parms, i)));
2721       }
2722
2723   /* [temp.class.spec]
2724
2725      The argument list of the specialization shall not be identical to
2726      the implicit argument list of the primary template.  */
2727   if (comp_template_args
2728       (inner_args,
2729        INNERMOST_TEMPLATE_ARGS (CLASSTYPE_TI_ARGS (TREE_TYPE
2730                                                    (maintmpl)))))
2731     error ("partial specialization %qT does not specialize any template arguments", type);
2732
2733   /* [temp.class.spec]
2734
2735      A partially specialized non-type argument expression shall not
2736      involve template parameters of the partial specialization except
2737      when the argument expression is a simple identifier.
2738
2739      The type of a template parameter corresponding to a specialized
2740      non-type argument shall not be dependent on a parameter of the
2741      specialization.  */
2742   gcc_assert (nargs == DECL_NTPARMS (maintmpl));
2743   tpd2.parms = 0;
2744   for (i = 0; i < nargs; ++i)
2745     {
2746       tree arg = TREE_VEC_ELT (inner_args, i);
2747       if (/* These first two lines are the `non-type' bit.  */
2748           !TYPE_P (arg)
2749           && TREE_CODE (arg) != TEMPLATE_DECL
2750           /* This next line is the `argument expression is not just a
2751              simple identifier' condition and also the `specialized
2752              non-type argument' bit.  */
2753           && TREE_CODE (arg) != TEMPLATE_PARM_INDEX)
2754         {
2755           if (tpd.arg_uses_template_parms[i])
2756             error ("template argument %qE involves template parameter(s)", arg);
2757           else
2758             {
2759               /* Look at the corresponding template parameter,
2760                  marking which template parameters its type depends
2761                  upon.  */
2762               tree type =
2763                 TREE_TYPE (TREE_VALUE (TREE_VEC_ELT (main_inner_parms,
2764                                                      i)));
2765
2766               if (!tpd2.parms)
2767                 {
2768                   /* We haven't yet initialized TPD2.  Do so now.  */
2769                   tpd2.arg_uses_template_parms
2770                     = (int *) alloca (sizeof (int) * nargs);
2771                   /* The number of parameters here is the number in the
2772                      main template, which, as checked in the assertion
2773                      above, is NARGS.  */
2774                   tpd2.parms = (int *) alloca (sizeof (int) * nargs);
2775                   tpd2.level =
2776                     TMPL_PARMS_DEPTH (DECL_TEMPLATE_PARMS (maintmpl));
2777                 }
2778
2779               /* Mark the template parameters.  But this time, we're
2780                  looking for the template parameters of the main
2781                  template, not in the specialization.  */
2782               tpd2.current_arg = i;
2783               tpd2.arg_uses_template_parms[i] = 0;
2784               memset (tpd2.parms, 0, sizeof (int) * nargs);
2785               for_each_template_parm (type,
2786                                       &mark_template_parm,
2787                                       &tpd2,
2788                                       NULL);
2789
2790               if (tpd2.arg_uses_template_parms [i])
2791                 {
2792                   /* The type depended on some template parameters.
2793                      If they are fully specialized in the
2794                      specialization, that's OK.  */
2795                   int j;
2796                   for (j = 0; j < nargs; ++j)
2797                     if (tpd2.parms[j] != 0
2798                         && tpd.arg_uses_template_parms [j])
2799                       {
2800                         error ("type %qT of template argument %qE depends "
2801                                "on template parameter(s)",
2802                                type,
2803                                arg);
2804                         break;
2805                       }
2806                 }
2807             }
2808         }
2809     }
2810
2811   if (retrieve_specialization (maintmpl, specargs,
2812                                /*class_specializations_p=*/true))
2813     /* We've already got this specialization.  */
2814     return decl;
2815
2816   DECL_TEMPLATE_SPECIALIZATIONS (maintmpl)
2817     = tree_cons (specargs, inner_parms,
2818                  DECL_TEMPLATE_SPECIALIZATIONS (maintmpl));
2819   TREE_TYPE (DECL_TEMPLATE_SPECIALIZATIONS (maintmpl)) = type;
2820   return decl;
2821 }
2822
2823 /* Check that a template declaration's use of default arguments is not
2824    invalid.  Here, PARMS are the template parameters.  IS_PRIMARY is
2825    nonzero if DECL is the thing declared by a primary template.
2826    IS_PARTIAL is nonzero if DECL is a partial specialization.  */
2827
2828 static void
2829 check_default_tmpl_args (tree decl, tree parms, int is_primary, int is_partial)
2830 {
2831   const char *msg;
2832   int last_level_to_check;
2833   tree parm_level;
2834
2835   /* [temp.param]
2836
2837      A default template-argument shall not be specified in a
2838      function template declaration or a function template definition, nor
2839      in the template-parameter-list of the definition of a member of a
2840      class template.  */
2841
2842   if (TREE_CODE (CP_DECL_CONTEXT (decl)) == FUNCTION_DECL)
2843     /* You can't have a function template declaration in a local
2844        scope, nor you can you define a member of a class template in a
2845        local scope.  */
2846     return;
2847
2848   if (current_class_type
2849       && !TYPE_BEING_DEFINED (current_class_type)
2850       && DECL_LANG_SPECIFIC (decl)
2851       /* If this is either a friend defined in the scope of the class
2852          or a member function.  */
2853       && (DECL_FUNCTION_MEMBER_P (decl)
2854           ? same_type_p (DECL_CONTEXT (decl), current_class_type)
2855           : DECL_FRIEND_CONTEXT (decl)
2856           ? same_type_p (DECL_FRIEND_CONTEXT (decl), current_class_type)
2857           : false)
2858       /* And, if it was a member function, it really was defined in
2859          the scope of the class.  */
2860       && (!DECL_FUNCTION_MEMBER_P (decl)
2861           || DECL_INITIALIZED_IN_CLASS_P (decl)))
2862     /* We already checked these parameters when the template was
2863        declared, so there's no need to do it again now.  This function
2864        was defined in class scope, but we're processing it's body now
2865        that the class is complete.  */
2866     return;
2867
2868   /* [temp.param]
2869
2870      If a template-parameter has a default template-argument, all
2871      subsequent template-parameters shall have a default
2872      template-argument supplied.  */
2873   for (parm_level = parms; parm_level; parm_level = TREE_CHAIN (parm_level))
2874     {
2875       tree inner_parms = TREE_VALUE (parm_level);
2876       int ntparms = TREE_VEC_LENGTH (inner_parms);
2877       int seen_def_arg_p = 0;
2878       int i;
2879
2880       for (i = 0; i < ntparms; ++i)
2881         {
2882           tree parm = TREE_VEC_ELT (inner_parms, i);
2883
2884           if (parm == error_mark_node)
2885             continue;
2886
2887           if (TREE_PURPOSE (parm))
2888             seen_def_arg_p = 1;
2889           else if (seen_def_arg_p)
2890             {
2891               error ("no default argument for %qD", TREE_VALUE (parm));
2892               /* For better subsequent error-recovery, we indicate that
2893                  there should have been a default argument.  */
2894               TREE_PURPOSE (parm) = error_mark_node;
2895             }
2896         }
2897     }
2898
2899   if (TREE_CODE (decl) != TYPE_DECL || is_partial || !is_primary)
2900     /* For an ordinary class template, default template arguments are
2901        allowed at the innermost level, e.g.:
2902          template <class T = int>
2903          struct S {};
2904        but, in a partial specialization, they're not allowed even
2905        there, as we have in [temp.class.spec]:
2906
2907          The template parameter list of a specialization shall not
2908          contain default template argument values.
2909
2910        So, for a partial specialization, or for a function template,
2911        we look at all of them.  */
2912     ;
2913   else
2914     /* But, for a primary class template that is not a partial
2915        specialization we look at all template parameters except the
2916        innermost ones.  */
2917     parms = TREE_CHAIN (parms);
2918
2919   /* Figure out what error message to issue.  */
2920   if (TREE_CODE (decl) == FUNCTION_DECL)
2921     msg = "default template arguments may not be used in function templates";
2922   else if (is_partial)
2923     msg = "default template arguments may not be used in partial specializations";
2924   else
2925     msg = "default argument for template parameter for class enclosing %qD";
2926
2927   if (current_class_type && TYPE_BEING_DEFINED (current_class_type))
2928     /* If we're inside a class definition, there's no need to
2929        examine the parameters to the class itself.  On the one
2930        hand, they will be checked when the class is defined, and,
2931        on the other, default arguments are valid in things like:
2932          template <class T = double>
2933          struct S { template <class U> void f(U); };
2934        Here the default argument for `S' has no bearing on the
2935        declaration of `f'.  */
2936     last_level_to_check = template_class_depth (current_class_type) + 1;
2937   else
2938     /* Check everything.  */
2939     last_level_to_check = 0;
2940
2941   for (parm_level = parms;
2942        parm_level && TMPL_PARMS_DEPTH (parm_level) >= last_level_to_check;
2943        parm_level = TREE_CHAIN (parm_level))
2944     {
2945       tree inner_parms = TREE_VALUE (parm_level);
2946       int i;
2947       int ntparms;
2948
2949       ntparms = TREE_VEC_LENGTH (inner_parms);
2950       for (i = 0; i < ntparms; ++i)
2951         {
2952           if (TREE_VEC_ELT (inner_parms, i) == error_mark_node)
2953             continue;
2954
2955           if (TREE_PURPOSE (TREE_VEC_ELT (inner_parms, i)))
2956             {
2957               if (msg)
2958                 {
2959                   error (msg, decl);
2960                   msg = 0;
2961                 }
2962
2963               /* Clear out the default argument so that we are not
2964                  confused later.  */
2965               TREE_PURPOSE (TREE_VEC_ELT (inner_parms, i)) = NULL_TREE;
2966             }
2967         }
2968
2969       /* At this point, if we're still interested in issuing messages,
2970          they must apply to classes surrounding the object declared.  */
2971       if (msg)
2972         msg = "default argument for template parameter for class enclosing %qD";
2973     }
2974 }
2975
2976 /* Worker for push_template_decl_real, called via
2977    for_each_template_parm.  DATA is really an int, indicating the
2978    level of the parameters we are interested in.  If T is a template
2979    parameter of that level, return nonzero.  */
2980
2981 static int
2982 template_parm_this_level_p (tree t, void* data)
2983 {
2984   int this_level = *(int *)data;
2985   int level;
2986
2987   if (TREE_CODE (t) == TEMPLATE_PARM_INDEX)
2988     level = TEMPLATE_PARM_LEVEL (t);
2989   else
2990     level = TEMPLATE_TYPE_LEVEL (t);
2991   return level == this_level;
2992 }
2993
2994 /* Creates a TEMPLATE_DECL for the indicated DECL using the template
2995    parameters given by current_template_args, or reuses a
2996    previously existing one, if appropriate.  Returns the DECL, or an
2997    equivalent one, if it is replaced via a call to duplicate_decls.
2998
2999    If IS_FRIEND is true, DECL is a friend declaration.  */
3000
3001 tree
3002 push_template_decl_real (tree decl, bool is_friend)
3003 {
3004   tree tmpl;
3005   tree args;
3006   tree info;
3007   tree ctx;
3008   int primary;
3009   int is_partial;
3010   int new_template_p = 0;
3011   /* True if the template is a member template, in the sense of
3012      [temp.mem].  */
3013   bool member_template_p = false;
3014
3015   if (decl == error_mark_node)
3016     return decl;
3017
3018   /* See if this is a partial specialization.  */
3019   is_partial = (DECL_IMPLICIT_TYPEDEF_P (decl)
3020                 && TREE_CODE (TREE_TYPE (decl)) != ENUMERAL_TYPE
3021                 && CLASSTYPE_TEMPLATE_SPECIALIZATION (TREE_TYPE (decl)));
3022
3023   if (TREE_CODE (decl) == FUNCTION_DECL && DECL_FRIEND_P (decl))
3024     is_friend = true;
3025
3026   if (is_friend)
3027     /* For a friend, we want the context of the friend function, not
3028        the type of which it is a friend.  */
3029     ctx = DECL_CONTEXT (decl);
3030   else if (CP_DECL_CONTEXT (decl)
3031            && TREE_CODE (CP_DECL_CONTEXT (decl)) != NAMESPACE_DECL)
3032     /* In the case of a virtual function, we want the class in which
3033        it is defined.  */
3034     ctx = CP_DECL_CONTEXT (decl);
3035   else
3036     /* Otherwise, if we're currently defining some class, the DECL
3037        is assumed to be a member of the class.  */
3038     ctx = current_scope ();
3039
3040   if (ctx && TREE_CODE (ctx) == NAMESPACE_DECL)
3041     ctx = NULL_TREE;
3042
3043   if (!DECL_CONTEXT (decl))
3044     DECL_CONTEXT (decl) = FROB_CONTEXT (current_namespace);
3045
3046   /* See if this is a primary template.  */
3047   if (is_friend && ctx)
3048     /* A friend template that specifies a class context, i.e.
3049          template <typename T> friend void A<T>::f();
3050        is not primary.  */
3051     primary = 0;
3052   else
3053     primary = template_parm_scope_p ();
3054
3055   if (primary)
3056     {
3057       if (DECL_CLASS_SCOPE_P (decl))
3058         member_template_p = true;
3059       if (TREE_CODE (decl) == TYPE_DECL
3060           && ANON_AGGRNAME_P (DECL_NAME (decl)))
3061         error ("template class without a name");
3062       else if (TREE_CODE (decl) == FUNCTION_DECL)
3063         {
3064           if (DECL_DESTRUCTOR_P (decl))
3065             {
3066               /* [temp.mem]
3067
3068                  A destructor shall not be a member template.  */
3069               error ("destructor %qD declared as member template", decl);
3070               return error_mark_node;
3071             }
3072           if (NEW_DELETE_OPNAME_P (DECL_NAME (decl))
3073               && (!TYPE_ARG_TYPES (TREE_TYPE (decl))
3074                   || TYPE_ARG_TYPES (TREE_TYPE (decl)) == void_list_node
3075                   || !TREE_CHAIN (TYPE_ARG_TYPES (TREE_TYPE (decl)))
3076                   || (TREE_CHAIN (TYPE_ARG_TYPES ((TREE_TYPE (decl))))
3077                       == void_list_node)))
3078             {
3079               /* [basic.stc.dynamic.allocation]
3080
3081                  An allocation function can be a function
3082                  template. ... Template allocation functions shall
3083                  have two or more parameters.  */
3084               error ("invalid template declaration of %qD", decl);
3085               return error_mark_node;
3086             }
3087         }
3088       else if (DECL_IMPLICIT_TYPEDEF_P (decl)
3089                && CLASS_TYPE_P (TREE_TYPE (decl)))
3090         /* OK */;
3091       else
3092         {
3093           error ("template declaration of %q#D", decl);
3094           return error_mark_node;
3095         }
3096     }
3097
3098   /* Check to see that the rules regarding the use of default
3099      arguments are not being violated.  */
3100   check_default_tmpl_args (decl, current_template_parms,
3101                            primary, is_partial);
3102
3103   if (is_partial)
3104     return process_partial_specialization (decl);
3105
3106   args = current_template_args ();
3107
3108   if (!ctx
3109       || TREE_CODE (ctx) == FUNCTION_DECL
3110       || (CLASS_TYPE_P (ctx) && TYPE_BEING_DEFINED (ctx))
3111       || (is_friend && !DECL_TEMPLATE_INFO (decl)))
3112     {
3113       if (DECL_LANG_SPECIFIC (decl)
3114           && DECL_TEMPLATE_INFO (decl)
3115           && DECL_TI_TEMPLATE (decl))
3116         tmpl = DECL_TI_TEMPLATE (decl);
3117       /* If DECL is a TYPE_DECL for a class-template, then there won't
3118          be DECL_LANG_SPECIFIC.  The information equivalent to
3119          DECL_TEMPLATE_INFO is found in TYPE_TEMPLATE_INFO instead.  */
3120       else if (DECL_IMPLICIT_TYPEDEF_P (decl)
3121                && TYPE_TEMPLATE_INFO (TREE_TYPE (decl))
3122                && TYPE_TI_TEMPLATE (TREE_TYPE (decl)))
3123         {
3124           /* Since a template declaration already existed for this
3125              class-type, we must be redeclaring it here.  Make sure
3126              that the redeclaration is valid.  */
3127           redeclare_class_template (TREE_TYPE (decl),
3128                                     current_template_parms);
3129           /* We don't need to create a new TEMPLATE_DECL; just use the
3130              one we already had.  */
3131           tmpl = TYPE_TI_TEMPLATE (TREE_TYPE (decl));
3132         }
3133       else
3134         {
3135           tmpl = build_template_decl (decl, current_template_parms,
3136                                       member_template_p);
3137           new_template_p = 1;
3138
3139           if (DECL_LANG_SPECIFIC (decl)
3140               && DECL_TEMPLATE_SPECIALIZATION (decl))
3141             {
3142               /* A specialization of a member template of a template
3143                  class.  */
3144               SET_DECL_TEMPLATE_SPECIALIZATION (tmpl);
3145               DECL_TEMPLATE_INFO (tmpl) = DECL_TEMPLATE_INFO (decl);
3146               DECL_TEMPLATE_INFO (decl) = NULL_TREE;
3147             }
3148         }
3149     }
3150   else
3151     {
3152       tree a, t, current, parms;
3153       int i;
3154
3155       if (TREE_CODE (decl) == TYPE_DECL)
3156         {
3157           if ((IS_AGGR_TYPE_CODE (TREE_CODE (TREE_TYPE (decl)))
3158                || TREE_CODE (TREE_TYPE (decl)) == ENUMERAL_TYPE)
3159               && TYPE_TEMPLATE_INFO (TREE_TYPE (decl))
3160               && TYPE_TI_TEMPLATE (TREE_TYPE (decl)))
3161             tmpl = TYPE_TI_TEMPLATE (TREE_TYPE (decl));
3162           else
3163             {
3164               error ("%qD does not declare a template type", decl);
3165               return decl;
3166             }
3167         }
3168       else if (!DECL_LANG_SPECIFIC (decl) || !DECL_TEMPLATE_INFO (decl))
3169         {
3170           error ("template definition of non-template %q#D", decl);
3171           return decl;
3172         }
3173       else
3174         tmpl = DECL_TI_TEMPLATE (decl);
3175
3176       if (DECL_FUNCTION_TEMPLATE_P (tmpl)
3177           && DECL_TEMPLATE_INFO (decl) && DECL_TI_ARGS (decl)
3178           && DECL_TEMPLATE_SPECIALIZATION (decl)
3179           && DECL_MEMBER_TEMPLATE_P (tmpl))
3180         {
3181           tree new_tmpl;
3182
3183           /* The declaration is a specialization of a member
3184              template, declared outside the class.  Therefore, the
3185              innermost template arguments will be NULL, so we
3186              replace them with the arguments determined by the
3187              earlier call to check_explicit_specialization.  */
3188           args = DECL_TI_ARGS (decl);
3189
3190           new_tmpl
3191             = build_template_decl (decl, current_template_parms,
3192                                    member_template_p);
3193           DECL_TEMPLATE_RESULT (new_tmpl) = decl;
3194           TREE_TYPE (new_tmpl) = TREE_TYPE (decl);
3195           DECL_TI_TEMPLATE (decl) = new_tmpl;
3196           SET_DECL_TEMPLATE_SPECIALIZATION (new_tmpl);
3197           DECL_TEMPLATE_INFO (new_tmpl)
3198             = tree_cons (tmpl, args, NULL_TREE);
3199
3200           register_specialization (new_tmpl,
3201                                    most_general_template (tmpl),
3202                                    args,
3203                                    is_friend);
3204           return decl;
3205         }
3206
3207       /* Make sure the template headers we got make sense.  */
3208
3209       parms = DECL_TEMPLATE_PARMS (tmpl);
3210       i = TMPL_PARMS_DEPTH (parms);
3211       if (TMPL_ARGS_DEPTH (args) != i)
3212         {
3213           error ("expected %d levels of template parms for %q#D, got %d",
3214                  i, decl, TMPL_ARGS_DEPTH (args));
3215         }
3216       else
3217         for (current = decl; i > 0; --i, parms = TREE_CHAIN (parms))
3218           {
3219             a = TMPL_ARGS_LEVEL (args, i);
3220             t = INNERMOST_TEMPLATE_PARMS (parms);
3221
3222             if (TREE_VEC_LENGTH (t) != TREE_VEC_LENGTH (a))
3223               {
3224                 if (current == decl)
3225                   error ("got %d template parameters for %q#D",
3226                          TREE_VEC_LENGTH (a), decl);
3227                 else
3228                   error ("got %d template parameters for %q#T",
3229                          TREE_VEC_LENGTH (a), current);
3230                 error ("  but %d required", TREE_VEC_LENGTH (t));
3231                 return error_mark_node;
3232               }
3233
3234             /* Perhaps we should also check that the parms are used in the
3235                appropriate qualifying scopes in the declarator?  */
3236
3237             if (current == decl)
3238               current = ctx;
3239             else
3240               current = TYPE_CONTEXT (current);
3241           }
3242     }
3243
3244   DECL_TEMPLATE_RESULT (tmpl) = decl;
3245   TREE_TYPE (tmpl) = TREE_TYPE (decl);
3246
3247   /* Push template declarations for global functions and types.  Note
3248      that we do not try to push a global template friend declared in a
3249      template class; such a thing may well depend on the template
3250      parameters of the class.  */
3251   if (new_template_p && !ctx
3252       && !(is_friend && template_class_depth (current_class_type) > 0))
3253     {
3254       tmpl = pushdecl_namespace_level (tmpl, is_friend);
3255       if (tmpl == error_mark_node)
3256         return error_mark_node;
3257
3258       /* Hide template friend classes that haven't been declared yet.  */
3259       if (is_friend && TREE_CODE (decl) == TYPE_DECL)
3260         {
3261           DECL_ANTICIPATED (tmpl) = 1;
3262           DECL_FRIEND_P (tmpl) = 1;
3263         }
3264     }
3265
3266   if (primary)
3267     {
3268       DECL_PRIMARY_TEMPLATE (tmpl) = tmpl;
3269       if (DECL_CONV_FN_P (tmpl))
3270         {
3271           int depth = TMPL_PARMS_DEPTH (DECL_TEMPLATE_PARMS (tmpl));
3272
3273           /* It is a conversion operator. See if the type converted to
3274              depends on innermost template operands.  */
3275
3276           if (uses_template_parms_level (TREE_TYPE (TREE_TYPE (tmpl)),
3277                                          depth))
3278             DECL_TEMPLATE_CONV_FN_P (tmpl) = 1;
3279         }
3280     }
3281
3282   /* The DECL_TI_ARGS of DECL contains full set of arguments referring
3283      back to its most general template.  If TMPL is a specialization,
3284      ARGS may only have the innermost set of arguments.  Add the missing
3285      argument levels if necessary.  */
3286   if (DECL_TEMPLATE_INFO (tmpl))
3287     args = add_outermost_template_args (DECL_TI_ARGS (tmpl), args);
3288
3289   info = tree_cons (tmpl, args, NULL_TREE);
3290
3291   if (DECL_IMPLICIT_TYPEDEF_P (decl))
3292     {
3293       SET_TYPE_TEMPLATE_INFO (TREE_TYPE (tmpl), info);
3294       if ((!ctx || TREE_CODE (ctx) != FUNCTION_DECL)
3295           && TREE_CODE (TREE_TYPE (decl)) != ENUMERAL_TYPE
3296           /* Don't change the name if we've already set it up.  */
3297           && !IDENTIFIER_TEMPLATE (DECL_NAME (decl)))
3298         DECL_NAME (decl) = classtype_mangled_name (TREE_TYPE (decl));
3299     }
3300   else if (DECL_LANG_SPECIFIC (decl))
3301     DECL_TEMPLATE_INFO (decl) = info;
3302
3303   return DECL_TEMPLATE_RESULT (tmpl);
3304 }
3305
3306 tree
3307 push_template_decl (tree decl)
3308 {
3309   return push_template_decl_real (decl, false);
3310 }
3311
3312 /* Called when a class template TYPE is redeclared with the indicated
3313    template PARMS, e.g.:
3314
3315      template <class T> struct S;
3316      template <class T> struct S {};  */
3317
3318 void
3319 redeclare_class_template (tree type, tree parms)
3320 {
3321   tree tmpl;
3322   tree tmpl_parms;
3323   int i;
3324
3325   if (!TYPE_TEMPLATE_INFO (type))
3326     {
3327       error ("%qT is not a template type", type);
3328       return;
3329     }
3330
3331   tmpl = TYPE_TI_TEMPLATE (type);
3332   if (!PRIMARY_TEMPLATE_P (tmpl))
3333     /* The type is nested in some template class.  Nothing to worry
3334        about here; there are no new template parameters for the nested
3335        type.  */
3336     return;
3337
3338   if (!parms)
3339     {
3340       error ("template specifiers not specified in declaration of %qD",
3341              tmpl);
3342       return;
3343     }
3344
3345   parms = INNERMOST_TEMPLATE_PARMS (parms);
3346   tmpl_parms = DECL_INNERMOST_TEMPLATE_PARMS (tmpl);
3347
3348   if (TREE_VEC_LENGTH (parms) != TREE_VEC_LENGTH (tmpl_parms))
3349     {
3350       error ("previous declaration %q+D", tmpl);
3351       error ("used %d template parameter(s) instead of %d",
3352              TREE_VEC_LENGTH (tmpl_parms),
3353              TREE_VEC_LENGTH (parms));
3354       return;
3355     }
3356
3357   for (i = 0; i < TREE_VEC_LENGTH (tmpl_parms); ++i)
3358     {
3359       tree tmpl_parm;
3360       tree parm;
3361       tree tmpl_default;
3362       tree parm_default;
3363
3364       if (TREE_VEC_ELT (tmpl_parms, i) == error_mark_node
3365           || TREE_VEC_ELT (parms, i) == error_mark_node)
3366         continue;
3367
3368       tmpl_parm = TREE_VALUE (TREE_VEC_ELT (tmpl_parms, i));
3369       parm = TREE_VALUE (TREE_VEC_ELT (parms, i));
3370       tmpl_default = TREE_PURPOSE (TREE_VEC_ELT (tmpl_parms, i));
3371       parm_default = TREE_PURPOSE (TREE_VEC_ELT (parms, i));
3372
3373       /* TMPL_PARM and PARM can be either TYPE_DECL, PARM_DECL, or
3374          TEMPLATE_DECL.  */
3375       if (tmpl_parm != error_mark_node
3376            && (TREE_CODE (tmpl_parm) != TREE_CODE (parm)
3377            || (TREE_CODE (tmpl_parm) != TYPE_DECL
3378                && !same_type_p (TREE_TYPE (tmpl_parm), TREE_TYPE (parm)))))
3379         {
3380           error ("template parameter %q+#D", tmpl_parm);
3381           error ("redeclared here as %q#D", parm);
3382           return;
3383         }
3384
3385       if (tmpl_default != NULL_TREE && parm_default != NULL_TREE)
3386         {
3387           /* We have in [temp.param]:
3388
3389              A template-parameter may not be given default arguments
3390              by two different declarations in the same scope.  */
3391           error ("redefinition of default argument for %q#D", parm);
3392           error ("%J  original definition appeared here", tmpl_parm);
3393           return;
3394         }
3395
3396       if (parm_default != NULL_TREE)
3397         /* Update the previous template parameters (which are the ones
3398            that will really count) with the new default value.  */
3399         TREE_PURPOSE (TREE_VEC_ELT (tmpl_parms, i)) = parm_default;
3400       else if (tmpl_default != NULL_TREE)
3401         /* Update the new parameters, too; they'll be used as the
3402            parameters for any members.  */
3403         TREE_PURPOSE (TREE_VEC_ELT (parms, i)) = tmpl_default;
3404     }
3405 }
3406
3407 /* Simplify EXPR if it is a non-dependent expression.  Returns the
3408    (possibly simplified) expression.  */
3409
3410 tree
3411 fold_non_dependent_expr (tree expr)
3412 {
3413   /* If we're in a template, but EXPR isn't value dependent, simplify
3414      it.  We're supposed to treat:
3415
3416        template <typename T> void f(T[1 + 1]);
3417        template <typename T> void f(T[2]);
3418
3419      as two declarations of the same function, for example.  */
3420   if (processing_template_decl
3421       && !type_dependent_expression_p (expr)
3422       && !value_dependent_expression_p (expr))
3423     {
3424       HOST_WIDE_INT saved_processing_template_decl;
3425
3426       saved_processing_template_decl = processing_template_decl;
3427       processing_template_decl = 0;
3428       expr = tsubst_copy_and_build (expr,
3429                                     /*args=*/NULL_TREE,
3430                                     tf_error,
3431                                     /*in_decl=*/NULL_TREE,
3432                                     /*function_p=*/false,
3433                                     /*integral_constant_expression_p=*/true);
3434       processing_template_decl = saved_processing_template_decl;
3435     }
3436   return expr;
3437 }
3438
3439 /* EXPR is an expression which is used in a constant-expression context.
3440    For instance, it could be a VAR_DECL with a constant initializer.
3441    Extract the innest constant expression.
3442
3443    This is basically a more powerful version of
3444    integral_constant_value, which can be used also in templates where
3445    initializers can maintain a syntactic rather than semantic form
3446    (even if they are non-dependent, for access-checking purposes).  */
3447
3448 static tree
3449 fold_decl_constant_value (tree expr)
3450 {
3451   tree const_expr = expr;
3452   do
3453     {
3454       expr = fold_non_dependent_expr (const_expr);
3455       const_expr = integral_constant_value (expr);
3456     }
3457   while (expr != const_expr);
3458
3459   return expr;
3460 }
3461
3462 /* Subroutine of convert_nontype_argument. Converts EXPR to TYPE, which
3463    must be a function or a pointer-to-function type, as specified
3464    in [temp.arg.nontype]: disambiguate EXPR if it is an overload set,
3465    and check that the resulting function has external linkage.  */
3466
3467 static tree
3468 convert_nontype_argument_function (tree type, tree expr)
3469 {
3470   tree fns = expr;
3471   tree fn, fn_no_ptr;
3472
3473   fn = instantiate_type (type, fns, tf_none);
3474   if (fn == error_mark_node)
3475     return error_mark_node;
3476
3477   fn_no_ptr = fn;
3478   if (TREE_CODE (fn_no_ptr) == ADDR_EXPR)
3479     fn_no_ptr = TREE_OPERAND (fn_no_ptr, 0);
3480   if (TREE_CODE (fn_no_ptr) == BASELINK)
3481     fn_no_ptr = BASELINK_FUNCTIONS (fn_no_ptr);
3482  
3483   /* [temp.arg.nontype]/1
3484
3485      A template-argument for a non-type, non-template template-parameter
3486      shall be one of:
3487      [...]
3488      -- the address of an object or function with external linkage.  */
3489   if (!DECL_EXTERNAL_LINKAGE_P (fn_no_ptr))
3490     {
3491       error ("%qE is not a valid template argument for type %qT "
3492              "because function %qD has not external linkage",
3493              expr, type, fn_no_ptr);
3494       return NULL_TREE;
3495     }
3496
3497   return fn;
3498 }
3499
3500 /* Attempt to convert the non-type template parameter EXPR to the
3501    indicated TYPE.  If the conversion is successful, return the
3502    converted value.  If the conversion is unsuccessful, return
3503    NULL_TREE if we issued an error message, or error_mark_node if we
3504    did not.  We issue error messages for out-and-out bad template
3505    parameters, but not simply because the conversion failed, since we
3506    might be just trying to do argument deduction.  Both TYPE and EXPR
3507    must be non-dependent.
3508
3509    The conversion follows the special rules described in
3510    [temp.arg.nontype], and it is much more strict than an implicit
3511    conversion.