OSDN Git Service

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