OSDN Git Service

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