OSDN Git Service

2005-07-08 Daniel Berlin <dberlin@dberlin.org>
[pf3gnuchains/gcc-fork.git] / gcc / cp / pt.c
1 /* Handle parameterized types (templates) for GNU C++.
2    Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998, 1999, 2000,
3    2001, 2002, 2003, 2004, 2005  Free Software Foundation, Inc.
4    Written by Ken Raeburn (raeburn@cygnus.com) while at Watchmaker Computing.
5    Rewritten by Jason Merrill (jason@cygnus.com).
6
7 This file is part of GCC.
8
9 GCC is free software; you can redistribute it and/or modify
10 it under the terms of the GNU General Public License as published by
11 the Free Software Foundation; either version 2, or (at your option)
12 any later version.
13
14 GCC is distributed in the hope that it will be useful,
15 but WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
17 GNU General Public License for more details.
18
19 You should have received a copy of the GNU General Public License
20 along with GCC; see the file COPYING.  If not, write to
21 the Free Software Foundation, 51 Franklin Street, Fifth Floor,
22 Boston, MA 02110-1301, USA.  */
23
24 /* Known bugs or deficiencies include:
25
26      all methods must be provided in header files; can't use a source
27      file that contains only the method templates and "just win".  */
28
29 #include "config.h"
30 #include "system.h"
31 #include "coretypes.h"
32 #include "tm.h"
33 #include "obstack.h"
34 #include "tree.h"
35 #include "pointer-set.h"
36 #include "flags.h"
37 #include "c-common.h"
38 #include "cp-tree.h"
39 #include "cp-objcp-common.h"
40 #include "tree-inline.h"
41 #include "decl.h"
42 #include "output.h"
43 #include "except.h"
44 #include "toplev.h"
45 #include "rtl.h"
46 #include "timevar.h"
47 #include "tree-iterator.h"
48
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       pedwarn ("  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               pedwarn ("  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   fn = retrieve_specialization (tmpl, args,
1143                                 /*class_specializations_p=*/false);
1144   /* We can sometimes try to re-register a specialization that we've
1145      already got.  In particular, regenerate_decl_from_template calls
1146      duplicate_decls which will update the specialization list.  But,
1147      we'll still get called again here anyhow.  It's more convenient
1148      to simply allow this than to try to prevent it.  */
1149   if (fn == spec)
1150     return spec;
1151   else if (fn && DECL_TEMPLATE_SPECIALIZATION (spec))
1152     {
1153       if (DECL_TEMPLATE_INSTANTIATION (fn))
1154         {
1155           if (TREE_USED (fn)
1156               || DECL_EXPLICIT_INSTANTIATION (fn))
1157             {
1158               error ("specialization of %qD after instantiation",
1159                      fn);
1160               return spec;
1161             }
1162           else
1163             {
1164               /* This situation should occur only if the first
1165                  specialization is an implicit instantiation, the
1166                  second is an explicit specialization, and the
1167                  implicit instantiation has not yet been used.  That
1168                  situation can occur if we have implicitly
1169                  instantiated a member function and then specialized
1170                  it later.
1171
1172                  We can also wind up here if a friend declaration that
1173                  looked like an instantiation turns out to be a
1174                  specialization:
1175
1176                    template <class T> void foo(T);
1177                    class S { friend void foo<>(int) };
1178                    template <> void foo(int);
1179
1180                  We transform the existing DECL in place so that any
1181                  pointers to it become pointers to the updated
1182                  declaration.
1183
1184                  If there was a definition for the template, but not
1185                  for the specialization, we want this to look as if
1186                  there were no definition, and vice versa.  */
1187               DECL_INITIAL (fn) = NULL_TREE;
1188               duplicate_decls (spec, fn);
1189
1190               return fn;
1191             }
1192         }
1193       else if (DECL_TEMPLATE_SPECIALIZATION (fn))
1194         {
1195           if (!duplicate_decls (spec, fn) && DECL_INITIAL (spec))
1196             /* Dup decl failed, but this is a new definition. Set the
1197                line number so any errors match this new
1198                definition.  */
1199             DECL_SOURCE_LOCATION (fn) = DECL_SOURCE_LOCATION (spec);
1200
1201           return fn;
1202         }
1203     }
1204
1205   /* A specialization must be declared in the same namespace as the
1206      template it is specializing.  */
1207   if (DECL_TEMPLATE_SPECIALIZATION (spec)
1208       && !check_specialization_namespace (tmpl))
1209     DECL_CONTEXT (spec) = decl_namespace_context (tmpl);
1210
1211   if (!optimize_specialization_lookup_p (tmpl))
1212     DECL_TEMPLATE_SPECIALIZATIONS (tmpl)
1213       = tree_cons (args, spec, DECL_TEMPLATE_SPECIALIZATIONS (tmpl));
1214
1215   return spec;
1216 }
1217
1218 /* Unregister the specialization SPEC as a specialization of TMPL.
1219    Replace it with NEW_SPEC, if NEW_SPEC is non-NULL.  Returns true
1220    if the SPEC was listed as a specialization of TMPL.  */
1221
1222 bool
1223 reregister_specialization (tree spec, tree tmpl, tree new_spec)
1224 {
1225   tree* s;
1226
1227   for (s = &DECL_TEMPLATE_SPECIALIZATIONS (tmpl);
1228        *s != NULL_TREE;
1229        s = &TREE_CHAIN (*s))
1230     if (TREE_VALUE (*s) == spec)
1231       {
1232         if (!new_spec)
1233           *s = TREE_CHAIN (*s);
1234         else
1235           TREE_VALUE (*s) = new_spec;
1236         return 1;
1237       }
1238
1239   return 0;
1240 }
1241
1242 /* Compare an entry in the local specializations hash table P1 (which
1243    is really a pointer to a TREE_LIST) with P2 (which is really a
1244    DECL).  */
1245
1246 static int
1247 eq_local_specializations (const void *p1, const void *p2)
1248 {
1249   return TREE_VALUE ((tree) p1) == (tree) p2;
1250 }
1251
1252 /* Hash P1, an entry in the local specializations table.  */
1253
1254 static hashval_t
1255 hash_local_specialization (const void* p1)
1256 {
1257   return htab_hash_pointer (TREE_VALUE ((tree) p1));
1258 }
1259
1260 /* Like register_specialization, but for local declarations.  We are
1261    registering SPEC, an instantiation of TMPL.  */
1262
1263 static void
1264 register_local_specialization (tree spec, tree tmpl)
1265 {
1266   void **slot;
1267
1268   slot = htab_find_slot_with_hash (local_specializations, tmpl,
1269                                    htab_hash_pointer (tmpl), INSERT);
1270   *slot = build_tree_list (spec, tmpl);
1271 }
1272
1273 /* Print the list of candidate FNS in an error message.  */
1274
1275 void
1276 print_candidates (tree fns)
1277 {
1278   tree fn;
1279
1280   const char *str = "candidates are:";
1281
1282   for (fn = fns; fn != NULL_TREE; fn = TREE_CHAIN (fn))
1283     {
1284       tree f;
1285
1286       for (f = TREE_VALUE (fn); f; f = OVL_NEXT (f))
1287         error ("%s %+#D", str, OVL_CURRENT (f));
1288       str = "               ";
1289     }
1290 }
1291
1292 /* Returns the template (one of the functions given by TEMPLATE_ID)
1293    which can be specialized to match the indicated DECL with the
1294    explicit template args given in TEMPLATE_ID.  The DECL may be
1295    NULL_TREE if none is available.  In that case, the functions in
1296    TEMPLATE_ID are non-members.
1297
1298    If NEED_MEMBER_TEMPLATE is nonzero the function is known to be a
1299    specialization of a member template.
1300
1301    The TEMPLATE_COUNT is the number of references to qualifying
1302    template classes that appeared in the name of the function. See
1303    check_explicit_specialization for a more accurate description.
1304
1305    The template args (those explicitly specified and those deduced)
1306    are output in a newly created vector *TARGS_OUT.
1307
1308    If it is impossible to determine the result, an error message is
1309    issued.  The error_mark_node is returned to indicate failure.  */
1310
1311 static tree
1312 determine_specialization (tree template_id,
1313                           tree decl,
1314                           tree* targs_out,
1315                           int need_member_template,
1316                           int template_count)
1317 {
1318   tree fns;
1319   tree targs;
1320   tree explicit_targs;
1321   tree candidates = NULL_TREE;
1322   tree templates = NULL_TREE;
1323   int header_count;
1324   struct cp_binding_level *b;
1325
1326   *targs_out = NULL_TREE;
1327
1328   if (template_id == error_mark_node)
1329     return error_mark_node;
1330
1331   fns = TREE_OPERAND (template_id, 0);
1332   explicit_targs = TREE_OPERAND (template_id, 1);
1333
1334   if (fns == error_mark_node)
1335     return error_mark_node;
1336
1337   /* Check for baselinks.  */
1338   if (BASELINK_P (fns))
1339     fns = BASELINK_FUNCTIONS (fns);
1340
1341   if (!is_overloaded_fn (fns))
1342     {
1343       error ("%qD is not a function template", fns);
1344       return error_mark_node;
1345     }
1346
1347   /* Count the number of template headers specified for this
1348      specialization.  */
1349   header_count = 0;
1350   for (b = current_binding_level;
1351        b->kind == sk_template_parms;
1352        b = b->level_chain)
1353     ++header_count;
1354
1355   for (; fns; fns = OVL_NEXT (fns))
1356     {
1357       tree fn = OVL_CURRENT (fns);
1358
1359       if (TREE_CODE (fn) == TEMPLATE_DECL)
1360         {
1361           tree decl_arg_types;
1362           tree fn_arg_types;
1363
1364           /* DECL might be a specialization of FN.  */
1365
1366           /* Adjust the type of DECL in case FN is a static member.  */
1367           decl_arg_types = TYPE_ARG_TYPES (TREE_TYPE (decl));
1368           if (DECL_STATIC_FUNCTION_P (fn)
1369               && DECL_NONSTATIC_MEMBER_FUNCTION_P (decl))
1370             decl_arg_types = TREE_CHAIN (decl_arg_types);
1371
1372           /* Check that the number of function parameters matches.
1373              For example,
1374                template <class T> void f(int i = 0);
1375                template <> void f<int>();
1376              The specialization f<int> is invalid but is not caught
1377              by get_bindings below.  */
1378
1379           fn_arg_types = TYPE_ARG_TYPES (TREE_TYPE (fn));
1380           if (list_length (fn_arg_types) != list_length (decl_arg_types))
1381             continue;
1382
1383           /* For a non-static member function, we need to make sure that
1384              the const qualification is the same. This can be done by
1385              checking the 'this' in the argument list.  */
1386           if (DECL_NONSTATIC_MEMBER_FUNCTION_P (fn)
1387               && !same_type_p (TREE_VALUE (fn_arg_types),
1388                                TREE_VALUE (decl_arg_types)))
1389             continue;
1390
1391           /* In case of explicit specialization, we need to check if
1392              the number of template headers appearing in the specialization
1393              is correct. This is usually done in check_explicit_specialization,
1394              but the check done there cannot be exhaustive when specializing
1395              member functions. Consider the following code:
1396
1397              template <> void A<int>::f(int);
1398              template <> template <> void A<int>::f(int);
1399
1400              Assuming that A<int> is not itself an explicit specialization
1401              already, the first line specializes "f" which is a non-template
1402              member function, whilst the second line specializes "f" which
1403              is a template member function. So both lines are syntactically
1404              correct, and check_explicit_specialization does not reject
1405              them.
1406
1407              Here, we can do better, as we are matching the specialization
1408              against the declarations. We count the number of template
1409              headers, and we check if they match TEMPLATE_COUNT + 1
1410              (TEMPLATE_COUNT is the number of qualifying template classes,
1411              plus there must be another header for the member template
1412              itself).
1413
1414              Notice that if header_count is zero, this is not a
1415              specialization but rather a template instantiation, so there
1416              is no check we can perform here.  */
1417           if (header_count && header_count != template_count + 1)
1418             continue;
1419
1420           /* Check that the number of template arguments at the
1421              innermost level for DECL is the same as for FN.  */
1422           if (current_binding_level->kind == sk_template_parms
1423               && !current_binding_level->explicit_spec_p
1424               && (TREE_VEC_LENGTH (DECL_INNERMOST_TEMPLATE_PARMS (fn))
1425                   != TREE_VEC_LENGTH (TREE_VALUE (current_template_parms))))
1426             continue;
1427
1428           /* See whether this function might be a specialization of this
1429              template.  */
1430           targs = get_bindings (fn, decl, explicit_targs, /*check_ret=*/true);
1431
1432           if (!targs)
1433             /* We cannot deduce template arguments that when used to
1434                specialize TMPL will produce DECL.  */
1435             continue;
1436
1437           /* Save this template, and the arguments deduced.  */
1438           templates = tree_cons (targs, fn, templates);
1439         }
1440       else if (need_member_template)
1441         /* FN is an ordinary member function, and we need a
1442            specialization of a member template.  */
1443         ;
1444       else if (TREE_CODE (fn) != FUNCTION_DECL)
1445         /* We can get IDENTIFIER_NODEs here in certain erroneous
1446            cases.  */
1447         ;
1448       else if (!DECL_FUNCTION_MEMBER_P (fn))
1449         /* This is just an ordinary non-member function.  Nothing can
1450            be a specialization of that.  */
1451         ;
1452       else if (DECL_ARTIFICIAL (fn))
1453         /* Cannot specialize functions that are created implicitly.  */
1454         ;
1455       else
1456         {
1457           tree decl_arg_types;
1458
1459           /* This is an ordinary member function.  However, since
1460              we're here, we can assume it's enclosing class is a
1461              template class.  For example,
1462
1463                template <typename T> struct S { void f(); };
1464                template <> void S<int>::f() {}
1465
1466              Here, S<int>::f is a non-template, but S<int> is a
1467              template class.  If FN has the same type as DECL, we
1468              might be in business.  */
1469
1470           if (!DECL_TEMPLATE_INFO (fn))
1471             /* Its enclosing class is an explicit specialization
1472                of a template class.  This is not a candidate.  */
1473             continue;
1474
1475           if (!same_type_p (TREE_TYPE (TREE_TYPE (decl)),
1476                             TREE_TYPE (TREE_TYPE (fn))))
1477             /* The return types differ.  */
1478             continue;
1479
1480           /* Adjust the type of DECL in case FN is a static member.  */
1481           decl_arg_types = TYPE_ARG_TYPES (TREE_TYPE (decl));
1482           if (DECL_STATIC_FUNCTION_P (fn)
1483               && DECL_NONSTATIC_MEMBER_FUNCTION_P (decl))
1484             decl_arg_types = TREE_CHAIN (decl_arg_types);
1485
1486           if (compparms (TYPE_ARG_TYPES (TREE_TYPE (fn)),
1487                          decl_arg_types))
1488             /* They match!  */
1489             candidates = tree_cons (NULL_TREE, fn, candidates);
1490         }
1491     }
1492
1493   if (templates && TREE_CHAIN (templates))
1494     {
1495       /* We have:
1496
1497            [temp.expl.spec]
1498
1499            It is possible for a specialization with a given function
1500            signature to be instantiated from more than one function
1501            template.  In such cases, explicit specification of the
1502            template arguments must be used to uniquely identify the
1503            function template specialization being specialized.
1504
1505          Note that here, there's no suggestion that we're supposed to
1506          determine which of the candidate templates is most
1507          specialized.  However, we, also have:
1508
1509            [temp.func.order]
1510
1511            Partial ordering of overloaded function template
1512            declarations is used in the following contexts to select
1513            the function template to which a function template
1514            specialization refers:
1515
1516            -- when an explicit specialization refers to a function
1517               template.
1518
1519          So, we do use the partial ordering rules, at least for now.
1520          This extension can only serve to make invalid programs valid,
1521          so it's safe.  And, there is strong anecdotal evidence that
1522          the committee intended the partial ordering rules to apply;
1523          the EDG front-end has that behavior, and John Spicer claims
1524          that the committee simply forgot to delete the wording in
1525          [temp.expl.spec].  */
1526      tree tmpl = most_specialized (templates, decl, explicit_targs);
1527      if (tmpl && tmpl != error_mark_node)
1528        {
1529          targs = get_bindings (tmpl, decl, explicit_targs, /*check_ret=*/true);
1530          templates = tree_cons (targs, tmpl, NULL_TREE);
1531        }
1532     }
1533
1534   if (templates == NULL_TREE && candidates == NULL_TREE)
1535     {
1536       error ("template-id %qD for %q+D does not match any template "
1537              "declaration", template_id, decl);
1538       return error_mark_node;
1539     }
1540   else if ((templates && TREE_CHAIN (templates))
1541            || (candidates && TREE_CHAIN (candidates))
1542            || (templates && candidates))
1543     {
1544       error ("ambiguous template specialization %qD for %q+D",
1545              template_id, decl);
1546       chainon (candidates, templates);
1547       print_candidates (candidates);
1548       return error_mark_node;
1549     }
1550
1551   /* We have one, and exactly one, match.  */
1552   if (candidates)
1553     {
1554       /* It was a specialization of an ordinary member function in a
1555          template class.  */
1556       *targs_out = copy_node (DECL_TI_ARGS (TREE_VALUE (candidates)));
1557       return DECL_TI_TEMPLATE (TREE_VALUE (candidates));
1558     }
1559
1560   /* It was a specialization of a template.  */
1561   targs = DECL_TI_ARGS (DECL_TEMPLATE_RESULT (TREE_VALUE (templates)));
1562   if (TMPL_ARGS_HAVE_MULTIPLE_LEVELS (targs))
1563     {
1564       *targs_out = copy_node (targs);
1565       SET_TMPL_ARGS_LEVEL (*targs_out,
1566                            TMPL_ARGS_DEPTH (*targs_out),
1567                            TREE_PURPOSE (templates));
1568     }
1569   else
1570     *targs_out = TREE_PURPOSE (templates);
1571   return TREE_VALUE (templates);
1572 }
1573
1574 /* Returns a chain of parameter types, exactly like the SPEC_TYPES,
1575    but with the default argument values filled in from those in the
1576    TMPL_TYPES.  */
1577
1578 static tree
1579 copy_default_args_to_explicit_spec_1 (tree spec_types,
1580                                       tree tmpl_types)
1581 {
1582   tree new_spec_types;
1583
1584   if (!spec_types)
1585     return NULL_TREE;
1586
1587   if (spec_types == void_list_node)
1588     return void_list_node;
1589
1590   /* Substitute into the rest of the list.  */
1591   new_spec_types =
1592     copy_default_args_to_explicit_spec_1 (TREE_CHAIN (spec_types),
1593                                           TREE_CHAIN (tmpl_types));
1594
1595   /* Add the default argument for this parameter.  */
1596   return hash_tree_cons (TREE_PURPOSE (tmpl_types),
1597                          TREE_VALUE (spec_types),
1598                          new_spec_types);
1599 }
1600
1601 /* DECL is an explicit specialization.  Replicate default arguments
1602    from the template it specializes.  (That way, code like:
1603
1604      template <class T> void f(T = 3);
1605      template <> void f(double);
1606      void g () { f (); }
1607
1608    works, as required.)  An alternative approach would be to look up
1609    the correct default arguments at the call-site, but this approach
1610    is consistent with how implicit instantiations are handled.  */
1611
1612 static void
1613 copy_default_args_to_explicit_spec (tree decl)
1614 {
1615   tree tmpl;
1616   tree spec_types;
1617   tree tmpl_types;
1618   tree new_spec_types;
1619   tree old_type;
1620   tree new_type;
1621   tree t;
1622   tree object_type = NULL_TREE;
1623   tree in_charge = NULL_TREE;
1624   tree vtt = NULL_TREE;
1625
1626   /* See if there's anything we need to do.  */
1627   tmpl = DECL_TI_TEMPLATE (decl);
1628   tmpl_types = TYPE_ARG_TYPES (TREE_TYPE (DECL_TEMPLATE_RESULT (tmpl)));
1629   for (t = tmpl_types; t; t = TREE_CHAIN (t))
1630     if (TREE_PURPOSE (t))
1631       break;
1632   if (!t)
1633     return;
1634
1635   old_type = TREE_TYPE (decl);
1636   spec_types = TYPE_ARG_TYPES (old_type);
1637
1638   if (DECL_NONSTATIC_MEMBER_FUNCTION_P (decl))
1639     {
1640       /* Remove the this pointer, but remember the object's type for
1641          CV quals.  */
1642       object_type = TREE_TYPE (TREE_VALUE (spec_types));
1643       spec_types = TREE_CHAIN (spec_types);
1644       tmpl_types = TREE_CHAIN (tmpl_types);
1645
1646       if (DECL_HAS_IN_CHARGE_PARM_P (decl))
1647         {
1648           /* DECL may contain more parameters than TMPL due to the extra
1649              in-charge parameter in constructors and destructors.  */
1650           in_charge = spec_types;
1651           spec_types = TREE_CHAIN (spec_types);
1652         }
1653       if (DECL_HAS_VTT_PARM_P (decl))
1654         {
1655           vtt = spec_types;
1656           spec_types = TREE_CHAIN (spec_types);
1657         }
1658     }
1659
1660   /* Compute the merged default arguments.  */
1661   new_spec_types =
1662     copy_default_args_to_explicit_spec_1 (spec_types, tmpl_types);
1663
1664   /* Compute the new FUNCTION_TYPE.  */
1665   if (object_type)
1666     {
1667       if (vtt)
1668         new_spec_types = hash_tree_cons (TREE_PURPOSE (vtt),
1669                                          TREE_VALUE (vtt),
1670                                          new_spec_types);
1671
1672       if (in_charge)
1673         /* Put the in-charge parameter back.  */
1674         new_spec_types = hash_tree_cons (TREE_PURPOSE (in_charge),
1675                                          TREE_VALUE (in_charge),
1676                                          new_spec_types);
1677
1678       new_type = build_method_type_directly (object_type,
1679                                              TREE_TYPE (old_type),
1680                                              new_spec_types);
1681     }
1682   else
1683     new_type = build_function_type (TREE_TYPE (old_type),
1684                                     new_spec_types);
1685   new_type = cp_build_type_attribute_variant (new_type,
1686                                               TYPE_ATTRIBUTES (old_type));
1687   new_type = build_exception_variant (new_type,
1688                                       TYPE_RAISES_EXCEPTIONS (old_type));
1689   TREE_TYPE (decl) = new_type;
1690 }
1691
1692 /* Check to see if the function just declared, as indicated in
1693    DECLARATOR, and in DECL, is a specialization of a function
1694    template.  We may also discover that the declaration is an explicit
1695    instantiation at this point.
1696
1697    Returns DECL, or an equivalent declaration that should be used
1698    instead if all goes well.  Issues an error message if something is
1699    amiss.  Returns error_mark_node if the error is not easily
1700    recoverable.
1701
1702    FLAGS is a bitmask consisting of the following flags:
1703
1704    2: The function has a definition.
1705    4: The function is a friend.
1706
1707    The TEMPLATE_COUNT is the number of references to qualifying
1708    template classes that appeared in the name of the function.  For
1709    example, in
1710
1711      template <class T> struct S { void f(); };
1712      void S<int>::f();
1713
1714    the TEMPLATE_COUNT would be 1.  However, explicitly specialized
1715    classes are not counted in the TEMPLATE_COUNT, so that in
1716
1717      template <class T> struct S {};
1718      template <> struct S<int> { void f(); }
1719      template <> void S<int>::f();
1720
1721    the TEMPLATE_COUNT would be 0.  (Note that this declaration is
1722    invalid; there should be no template <>.)
1723
1724    If the function is a specialization, it is marked as such via
1725    DECL_TEMPLATE_SPECIALIZATION.  Furthermore, its DECL_TEMPLATE_INFO
1726    is set up correctly, and it is added to the list of specializations
1727    for that template.  */
1728
1729 tree
1730 check_explicit_specialization (tree declarator,
1731                                tree decl,
1732                                int template_count,
1733                                int flags)
1734 {
1735   int have_def = flags & 2;
1736   int is_friend = flags & 4;
1737   int specialization = 0;
1738   int explicit_instantiation = 0;
1739   int member_specialization = 0;
1740   tree ctype = DECL_CLASS_CONTEXT (decl);
1741   tree dname = DECL_NAME (decl);
1742   tmpl_spec_kind tsk;
1743
1744   if (is_friend)
1745     {
1746       if (!processing_specialization)
1747         tsk = tsk_none;
1748       else
1749         tsk = tsk_excessive_parms;
1750     }
1751   else
1752     tsk = current_tmpl_spec_kind (template_count);
1753
1754   switch (tsk)
1755     {
1756     case tsk_none:
1757       if (processing_specialization)
1758         {
1759           specialization = 1;
1760           SET_DECL_TEMPLATE_SPECIALIZATION (decl);
1761         }
1762       else if (TREE_CODE (declarator) == TEMPLATE_ID_EXPR)
1763         {
1764           if (is_friend)
1765             /* This could be something like:
1766
1767                template <class T> void f(T);
1768                class S { friend void f<>(int); }  */
1769             specialization = 1;
1770           else
1771             {
1772               /* This case handles bogus declarations like template <>
1773                  template <class T> void f<int>(); */
1774
1775               error ("template-id %qD in declaration of primary template",
1776                      declarator);
1777               return decl;
1778             }
1779         }
1780       break;
1781
1782     case tsk_invalid_member_spec:
1783       /* The error has already been reported in
1784          check_specialization_scope.  */
1785       return error_mark_node;
1786
1787     case tsk_invalid_expl_inst:
1788       error ("template parameter list used in explicit instantiation");
1789
1790       /* Fall through.  */
1791
1792     case tsk_expl_inst:
1793       if (have_def)
1794         error ("definition provided for explicit instantiation");
1795
1796       explicit_instantiation = 1;
1797       break;
1798
1799     case tsk_excessive_parms:
1800     case tsk_insufficient_parms:
1801       if (tsk == tsk_excessive_parms)
1802         error ("too many template parameter lists in declaration of %qD",
1803                decl);
1804       else if (template_header_count)
1805         error("too few template parameter lists in declaration of %qD", decl);
1806       else
1807         error("explicit specialization of %qD must be introduced by "
1808               "%<template <>%>", decl);
1809
1810       /* Fall through.  */
1811     case tsk_expl_spec:
1812       SET_DECL_TEMPLATE_SPECIALIZATION (decl);
1813       if (ctype)
1814         member_specialization = 1;
1815       else
1816         specialization = 1;
1817       break;
1818
1819     case tsk_template:
1820       if (TREE_CODE (declarator) == TEMPLATE_ID_EXPR)
1821         {
1822           /* This case handles bogus declarations like template <>
1823              template <class T> void f<int>(); */
1824
1825           if (uses_template_parms (declarator))
1826             error ("function template partial specialization %qD "
1827                    "is not allowed", declarator);
1828           else
1829             error ("template-id %qD in declaration of primary template",
1830                    declarator);
1831           return decl;
1832         }
1833
1834       if (ctype && CLASSTYPE_TEMPLATE_INSTANTIATION (ctype))
1835         /* This is a specialization of a member template, without
1836            specialization the containing class.  Something like:
1837
1838              template <class T> struct S {
1839                template <class U> void f (U);
1840              };
1841              template <> template <class U> void S<int>::f(U) {}
1842
1843            That's a specialization -- but of the entire template.  */
1844         specialization = 1;
1845       break;
1846
1847     default:
1848       gcc_unreachable ();
1849     }
1850
1851   if (specialization || member_specialization)
1852     {
1853       tree t = TYPE_ARG_TYPES (TREE_TYPE (decl));
1854       for (; t; t = TREE_CHAIN (t))
1855         if (TREE_PURPOSE (t))
1856           {
1857             pedwarn
1858               ("default argument specified in explicit specialization");
1859             break;
1860           }
1861       if (current_lang_name == lang_name_c)
1862         error ("template specialization with C linkage");
1863     }
1864
1865   if (specialization || member_specialization || explicit_instantiation)
1866     {
1867       tree tmpl = NULL_TREE;
1868       tree targs = NULL_TREE;
1869
1870       /* Make sure that the declarator is a TEMPLATE_ID_EXPR.  */
1871       if (TREE_CODE (declarator) != TEMPLATE_ID_EXPR)
1872         {
1873           tree fns;
1874
1875           gcc_assert (TREE_CODE (declarator) == IDENTIFIER_NODE);
1876           if (ctype)
1877             fns = dname;
1878           else
1879             {
1880               /* If there is no class context, the explicit instantiation
1881                  must be at namespace scope.  */
1882               gcc_assert (DECL_NAMESPACE_SCOPE_P (decl));
1883
1884               /* Find the namespace binding, using the declaration
1885                  context.  */
1886               fns = namespace_binding (dname, CP_DECL_CONTEXT (decl));
1887               if (!fns || !is_overloaded_fn (fns))
1888                 {
1889                   error ("%qD is not a template function", dname);
1890                   fns = error_mark_node;
1891                 }
1892             }
1893
1894           declarator = lookup_template_function (fns, NULL_TREE);
1895         }
1896
1897       if (declarator == error_mark_node)
1898         return error_mark_node;
1899
1900       if (ctype != NULL_TREE && TYPE_BEING_DEFINED (ctype))
1901         {
1902           if (!explicit_instantiation)
1903             /* A specialization in class scope.  This is invalid,
1904                but the error will already have been flagged by
1905                check_specialization_scope.  */
1906             return error_mark_node;
1907           else
1908             {
1909               /* It's not valid to write an explicit instantiation in
1910                  class scope, e.g.:
1911
1912                    class C { template void f(); }
1913
1914                    This case is caught by the parser.  However, on
1915                    something like:
1916
1917                    template class C { void f(); };
1918
1919                    (which is invalid) we can get here.  The error will be
1920                    issued later.  */
1921               ;
1922             }
1923
1924           return decl;
1925         }
1926       else if (ctype != NULL_TREE
1927                && (TREE_CODE (TREE_OPERAND (declarator, 0)) ==
1928                    IDENTIFIER_NODE))
1929         {
1930           /* Find the list of functions in ctype that have the same
1931              name as the declared function.  */
1932           tree name = TREE_OPERAND (declarator, 0);
1933           tree fns = NULL_TREE;
1934           int idx;
1935
1936           if (constructor_name_p (name, ctype))
1937             {
1938               int is_constructor = DECL_CONSTRUCTOR_P (decl);
1939
1940               if (is_constructor ? !TYPE_HAS_CONSTRUCTOR (ctype)
1941                   : !CLASSTYPE_DESTRUCTORS (ctype))
1942                 {
1943                   /* From [temp.expl.spec]:
1944
1945                      If such an explicit specialization for the member
1946                      of a class template names an implicitly-declared
1947                      special member function (clause _special_), the
1948                      program is ill-formed.
1949
1950                      Similar language is found in [temp.explicit].  */
1951                   error ("specialization of implicitly-declared special member function");
1952                   return error_mark_node;
1953                 }
1954
1955               name = is_constructor ? ctor_identifier : dtor_identifier;
1956             }
1957
1958           if (!DECL_CONV_FN_P (decl))
1959             {
1960               idx = lookup_fnfields_1 (ctype, name);
1961               if (idx >= 0)
1962                 fns = VEC_index (tree, CLASSTYPE_METHOD_VEC (ctype), idx);
1963             }
1964           else
1965             {
1966               VEC(tree,gc) *methods;
1967               tree ovl;
1968
1969               /* For a type-conversion operator, we cannot do a
1970                  name-based lookup.  We might be looking for `operator
1971                  int' which will be a specialization of `operator T'.
1972                  So, we find *all* the conversion operators, and then
1973                  select from them.  */
1974               fns = NULL_TREE;
1975
1976               methods = CLASSTYPE_METHOD_VEC (ctype);
1977               if (methods)
1978                 for (idx = CLASSTYPE_FIRST_CONVERSION_SLOT;
1979                      VEC_iterate (tree, methods, idx, ovl);
1980                      ++idx)
1981                   {
1982                     if (!DECL_CONV_FN_P (OVL_CURRENT (ovl)))
1983                       /* There are no more conversion functions.  */
1984                       break;
1985
1986                     /* Glue all these conversion functions together
1987                        with those we already have.  */
1988                     for (; ovl; ovl = OVL_NEXT (ovl))
1989                       fns = ovl_cons (OVL_CURRENT (ovl), fns);
1990                   }
1991             }
1992
1993           if (fns == NULL_TREE)
1994             {
1995               error ("no member function %qD declared in %qT", name, ctype);
1996               return error_mark_node;
1997             }
1998           else
1999             TREE_OPERAND (declarator, 0) = fns;
2000         }
2001
2002       /* Figure out what exactly is being specialized at this point.
2003          Note that for an explicit instantiation, even one for a
2004          member function, we cannot tell apriori whether the
2005          instantiation is for a member template, or just a member
2006          function of a template class.  Even if a member template is
2007          being instantiated, the member template arguments may be
2008          elided if they can be deduced from the rest of the
2009          declaration.  */
2010       tmpl = determine_specialization (declarator, decl,
2011                                        &targs,
2012                                        member_specialization,
2013                                        template_count);
2014
2015       if (!tmpl || tmpl == error_mark_node)
2016         /* We couldn't figure out what this declaration was
2017            specializing.  */
2018         return error_mark_node;
2019       else
2020         {
2021           tree gen_tmpl = most_general_template (tmpl);
2022
2023           if (explicit_instantiation)
2024             {
2025               /* We don't set DECL_EXPLICIT_INSTANTIATION here; that
2026                  is done by do_decl_instantiation later.  */
2027
2028               int arg_depth = TMPL_ARGS_DEPTH (targs);
2029               int parm_depth = TMPL_PARMS_DEPTH (DECL_TEMPLATE_PARMS (tmpl));
2030
2031               if (arg_depth > parm_depth)
2032                 {
2033                   /* If TMPL is not the most general template (for
2034                      example, if TMPL is a friend template that is
2035                      injected into namespace scope), then there will
2036                      be too many levels of TARGS.  Remove some of them
2037                      here.  */
2038                   int i;
2039                   tree new_targs;
2040
2041                   new_targs = make_tree_vec (parm_depth);
2042                   for (i = arg_depth - parm_depth; i < arg_depth; ++i)
2043                     TREE_VEC_ELT (new_targs, i - (arg_depth - parm_depth))
2044                       = TREE_VEC_ELT (targs, i);
2045                   targs = new_targs;
2046                 }
2047
2048               return instantiate_template (tmpl, targs, tf_error);
2049             }
2050
2051           /* If we thought that the DECL was a member function, but it
2052              turns out to be specializing a static member function,
2053              make DECL a static member function as well.  */
2054           if (DECL_STATIC_FUNCTION_P (tmpl)
2055               && DECL_NONSTATIC_MEMBER_FUNCTION_P (decl))
2056             revert_static_member_fn (decl);
2057
2058           /* If this is a specialization of a member template of a
2059              template class.  In we want to return the TEMPLATE_DECL,
2060              not the specialization of it.  */
2061           if (tsk == tsk_template)
2062             {
2063               SET_DECL_TEMPLATE_SPECIALIZATION (tmpl);
2064               DECL_INITIAL (DECL_TEMPLATE_RESULT (tmpl)) = NULL_TREE;
2065               if (have_def)
2066                 {
2067                   DECL_SOURCE_LOCATION (tmpl) = DECL_SOURCE_LOCATION (decl);
2068                   DECL_SOURCE_LOCATION (DECL_TEMPLATE_RESULT (tmpl))
2069                     = DECL_SOURCE_LOCATION (decl);
2070                   /* We want to use the argument list specified in the
2071                      definition, not in the original declaration.  */
2072                   DECL_ARGUMENTS (DECL_TEMPLATE_RESULT (tmpl))
2073                     = DECL_ARGUMENTS (decl);
2074                 }
2075               return tmpl;
2076             }
2077
2078           /* Set up the DECL_TEMPLATE_INFO for DECL.  */
2079           DECL_TEMPLATE_INFO (decl) = tree_cons (tmpl, targs, NULL_TREE);
2080
2081           /* Inherit default function arguments from the template
2082              DECL is specializing.  */
2083           copy_default_args_to_explicit_spec (decl);
2084
2085           /* This specialization has the same protection as the
2086              template it specializes.  */
2087           TREE_PRIVATE (decl) = TREE_PRIVATE (gen_tmpl);
2088           TREE_PROTECTED (decl) = TREE_PROTECTED (gen_tmpl);
2089
2090           if (is_friend && !have_def)
2091             /* This is not really a declaration of a specialization.
2092                It's just the name of an instantiation.  But, it's not
2093                a request for an instantiation, either.  */
2094             SET_DECL_IMPLICIT_INSTANTIATION (decl);
2095           else if (DECL_CONSTRUCTOR_P (decl) || DECL_DESTRUCTOR_P (decl))
2096             /* This is indeed a specialization.  In case of constructors
2097                and destructors, we need in-charge and not-in-charge
2098                versions in V3 ABI.  */
2099             clone_function_decl (decl, /*update_method_vec_p=*/0);
2100
2101           /* Register this specialization so that we can find it
2102              again.  */
2103           decl = register_specialization (decl, gen_tmpl, targs);
2104         }
2105     }
2106
2107   return decl;
2108 }
2109
2110 /* Returns 1 iff PARMS1 and PARMS2 are identical sets of template
2111    parameters.  These are represented in the same format used for
2112    DECL_TEMPLATE_PARMS.  */
2113
2114 int
2115 comp_template_parms (tree parms1, tree parms2)
2116 {
2117   tree p1;
2118   tree p2;
2119
2120   if (parms1 == parms2)
2121     return 1;
2122
2123   for (p1 = parms1, p2 = parms2;
2124        p1 != NULL_TREE && p2 != NULL_TREE;
2125        p1 = TREE_CHAIN (p1), p2 = TREE_CHAIN (p2))
2126     {
2127       tree t1 = TREE_VALUE (p1);
2128       tree t2 = TREE_VALUE (p2);
2129       int i;
2130
2131       gcc_assert (TREE_CODE (t1) == TREE_VEC);
2132       gcc_assert (TREE_CODE (t2) == TREE_VEC);
2133
2134       if (TREE_VEC_LENGTH (t1) != TREE_VEC_LENGTH (t2))
2135         return 0;
2136
2137       for (i = 0; i < TREE_VEC_LENGTH (t2); ++i)
2138         {
2139           tree parm1 = TREE_VALUE (TREE_VEC_ELT (t1, i));
2140           tree parm2 = TREE_VALUE (TREE_VEC_ELT (t2, i));
2141
2142           if (TREE_CODE (parm1) != TREE_CODE (parm2))
2143             return 0;
2144
2145           if (TREE_CODE (parm1) == TEMPLATE_TYPE_PARM)
2146             continue;
2147           else if (!same_type_p (TREE_TYPE (parm1), TREE_TYPE (parm2)))
2148             return 0;
2149         }
2150     }
2151
2152   if ((p1 != NULL_TREE) != (p2 != NULL_TREE))
2153     /* One set of parameters has more parameters lists than the
2154        other.  */
2155     return 0;
2156
2157   return 1;
2158 }
2159
2160 /* Complain if DECL shadows a template parameter.
2161
2162    [temp.local]: A template-parameter shall not be redeclared within its
2163    scope (including nested scopes).  */
2164
2165 void
2166 check_template_shadow (tree decl)
2167 {
2168   tree olddecl;
2169
2170   /* If we're not in a template, we can't possibly shadow a template
2171      parameter.  */
2172   if (!current_template_parms)
2173     return;
2174
2175   /* Figure out what we're shadowing.  */
2176   if (TREE_CODE (decl) == OVERLOAD)
2177     decl = OVL_CURRENT (decl);
2178   olddecl = innermost_non_namespace_value (DECL_NAME (decl));
2179
2180   /* If there's no previous binding for this name, we're not shadowing
2181      anything, let alone a template parameter.  */
2182   if (!olddecl)
2183     return;
2184
2185   /* If we're not shadowing a template parameter, we're done.  Note
2186      that OLDDECL might be an OVERLOAD (or perhaps even an
2187      ERROR_MARK), so we can't just blithely assume it to be a _DECL
2188      node.  */
2189   if (!DECL_P (olddecl) || !DECL_TEMPLATE_PARM_P (olddecl))
2190     return;
2191
2192   /* We check for decl != olddecl to avoid bogus errors for using a
2193      name inside a class.  We check TPFI to avoid duplicate errors for
2194      inline member templates.  */
2195   if (decl == olddecl
2196       || TEMPLATE_PARMS_FOR_INLINE (current_template_parms))
2197     return;
2198
2199   error ("declaration of %q+#D", decl);
2200   error (" shadows template parm %q+#D", olddecl);
2201 }
2202
2203 /* Return a new TEMPLATE_PARM_INDEX with the indicated INDEX, LEVEL,
2204    ORIG_LEVEL, DECL, and TYPE.  */
2205
2206 static tree
2207 build_template_parm_index (int index,
2208                            int level,
2209                            int orig_level,
2210                            tree decl,
2211                            tree type)
2212 {
2213   tree t = make_node (TEMPLATE_PARM_INDEX);
2214   TEMPLATE_PARM_IDX (t) = index;
2215   TEMPLATE_PARM_LEVEL (t) = level;
2216   TEMPLATE_PARM_ORIG_LEVEL (t) = orig_level;
2217   TEMPLATE_PARM_DECL (t) = decl;
2218   TREE_TYPE (t) = type;
2219   TREE_CONSTANT (t) = TREE_CONSTANT (decl);
2220   TREE_INVARIANT (t) = TREE_INVARIANT (decl);
2221   TREE_READONLY (t) = TREE_READONLY (decl);
2222
2223   return t;
2224 }
2225
2226 /* Return a TEMPLATE_PARM_INDEX, similar to INDEX, but whose
2227    TEMPLATE_PARM_LEVEL has been decreased by LEVELS.  If such a
2228    TEMPLATE_PARM_INDEX already exists, it is returned; otherwise, a
2229    new one is created.  */
2230
2231 static tree
2232 reduce_template_parm_level (tree index, tree type, int levels)
2233 {
2234   if (TEMPLATE_PARM_DESCENDANTS (index) == NULL_TREE
2235       || (TEMPLATE_PARM_LEVEL (TEMPLATE_PARM_DESCENDANTS (index))
2236           != TEMPLATE_PARM_LEVEL (index) - levels))
2237     {
2238       tree orig_decl = TEMPLATE_PARM_DECL (index);
2239       tree decl, t;
2240
2241       decl = build_decl (TREE_CODE (orig_decl), DECL_NAME (orig_decl), type);
2242       TREE_CONSTANT (decl) = TREE_CONSTANT (orig_decl);
2243       TREE_INVARIANT (decl) = TREE_INVARIANT (orig_decl);
2244       TREE_READONLY (decl) = TREE_READONLY (orig_decl);
2245       DECL_ARTIFICIAL (decl) = 1;
2246       SET_DECL_TEMPLATE_PARM_P (decl);
2247
2248       t = build_template_parm_index (TEMPLATE_PARM_IDX (index),
2249                                      TEMPLATE_PARM_LEVEL (index) - levels,
2250                                      TEMPLATE_PARM_ORIG_LEVEL (index),
2251                                      decl, type);
2252       TEMPLATE_PARM_DESCENDANTS (index) = t;
2253
2254         /* Template template parameters need this.  */
2255       if (TREE_CODE (decl) != CONST_DECL)
2256         DECL_TEMPLATE_PARMS (decl)
2257           = DECL_TEMPLATE_PARMS (TEMPLATE_PARM_DECL (index));
2258     }
2259
2260   return TEMPLATE_PARM_DESCENDANTS (index);
2261 }
2262
2263 /* Process information from new template parameter NEXT and append it to the
2264    LIST being built.  This new parameter is a non-type parameter iff
2265    IS_NON_TYPE is true.  */
2266
2267 tree
2268 process_template_parm (tree list, tree next, bool is_non_type)
2269 {
2270   tree parm;
2271   tree decl = 0;
2272   tree defval;
2273   int idx;
2274
2275   parm = next;
2276   gcc_assert (TREE_CODE (parm) == TREE_LIST);
2277   defval = TREE_PURPOSE (parm);
2278
2279   if (list)
2280     {
2281       tree p = TREE_VALUE (tree_last (list));
2282
2283       if (TREE_CODE (p) == TYPE_DECL || TREE_CODE (p) == TEMPLATE_DECL)
2284         idx = TEMPLATE_TYPE_IDX (TREE_TYPE (p));
2285       else
2286         idx = TEMPLATE_PARM_IDX (DECL_INITIAL (p));
2287       ++idx;
2288     }
2289   else
2290     idx = 0;
2291
2292   if (is_non_type)
2293     {
2294       parm = TREE_VALUE (parm);
2295
2296       SET_DECL_TEMPLATE_PARM_P (parm);
2297
2298       /* [temp.param]
2299
2300          The top-level cv-qualifiers on the template-parameter are
2301          ignored when determining its type.  */
2302       TREE_TYPE (parm) = TYPE_MAIN_VARIANT (TREE_TYPE (parm));
2303
2304       /* A template parameter is not modifiable.  */
2305       TREE_CONSTANT (parm) = 1;
2306       TREE_INVARIANT (parm) = 1;
2307       TREE_READONLY (parm) = 1;
2308       if (invalid_nontype_parm_type_p (TREE_TYPE (parm), 1))
2309         TREE_TYPE (parm) = void_type_node;
2310       decl = build_decl (CONST_DECL, DECL_NAME (parm), TREE_TYPE (parm));
2311       TREE_CONSTANT (decl) = 1;
2312       TREE_INVARIANT (decl) = 1;
2313       TREE_READONLY (decl) = 1;
2314       DECL_INITIAL (parm) = DECL_INITIAL (decl)
2315         = build_template_parm_index (idx, processing_template_decl,
2316                                      processing_template_decl,
2317                                      decl, TREE_TYPE (parm));
2318     }
2319   else
2320     {
2321       tree t;
2322       parm = TREE_VALUE (TREE_VALUE (parm));
2323
2324       if (parm && TREE_CODE (parm) == TEMPLATE_DECL)
2325         {
2326           t = make_aggr_type (TEMPLATE_TEMPLATE_PARM);
2327           /* This is for distinguishing between real templates and template
2328              template parameters */
2329           TREE_TYPE (parm) = t;
2330           TREE_TYPE (DECL_TEMPLATE_RESULT (parm)) = t;
2331           decl = parm;
2332         }
2333       else
2334         {
2335           t = make_aggr_type (TEMPLATE_TYPE_PARM);
2336           /* parm is either IDENTIFIER_NODE or NULL_TREE.  */
2337           decl = build_decl (TYPE_DECL, parm, t);
2338         }
2339
2340       TYPE_NAME (t) = decl;
2341       TYPE_STUB_DECL (t) = decl;
2342       parm = decl;
2343       TEMPLATE_TYPE_PARM_INDEX (t)
2344         = build_template_parm_index (idx, processing_template_decl,
2345                                      processing_template_decl,
2346                                      decl, TREE_TYPE (parm));
2347     }
2348   DECL_ARTIFICIAL (decl) = 1;
2349   SET_DECL_TEMPLATE_PARM_P (decl);
2350   pushdecl (decl);
2351   parm = build_tree_list (defval, parm);
2352   return chainon (list, parm);
2353 }
2354
2355 /* The end of a template parameter list has been reached.  Process the
2356    tree list into a parameter vector, converting each parameter into a more
2357    useful form.  Type parameters are saved as IDENTIFIER_NODEs, and others
2358    as PARM_DECLs.  */
2359
2360 tree
2361 end_template_parm_list (tree parms)
2362 {
2363   int nparms;
2364   tree parm, next;
2365   tree saved_parmlist = make_tree_vec (list_length (parms));
2366
2367   current_template_parms
2368     = tree_cons (size_int (processing_template_decl),
2369                  saved_parmlist, current_template_parms);
2370
2371   for (parm = parms, nparms = 0; parm; parm = next, nparms++)
2372     {
2373       next = TREE_CHAIN (parm);
2374       TREE_VEC_ELT (saved_parmlist, nparms) = parm;
2375       TREE_CHAIN (parm) = NULL_TREE;
2376     }
2377
2378   --processing_template_parmlist;
2379
2380   return saved_parmlist;
2381 }
2382
2383 /* end_template_decl is called after a template declaration is seen.  */
2384
2385 void
2386 end_template_decl (void)
2387 {
2388   reset_specialization ();
2389
2390   if (! processing_template_decl)
2391     return;
2392
2393   /* This matches the pushlevel in begin_template_parm_list.  */
2394   finish_scope ();
2395
2396   --processing_template_decl;
2397   current_template_parms = TREE_CHAIN (current_template_parms);
2398 }
2399
2400 /* Given a template argument vector containing the template PARMS.
2401    The innermost PARMS are given first.  */
2402
2403 tree
2404 current_template_args (void)
2405 {
2406   tree header;
2407   tree args = NULL_TREE;
2408   int length = TMPL_PARMS_DEPTH (current_template_parms);
2409   int l = length;
2410
2411   /* If there is only one level of template parameters, we do not
2412      create a TREE_VEC of TREE_VECs.  Instead, we return a single
2413      TREE_VEC containing the arguments.  */
2414   if (length > 1)
2415     args = make_tree_vec (length);
2416
2417   for (header = current_template_parms; header; header = TREE_CHAIN (header))
2418     {
2419       tree a = copy_node (TREE_VALUE (header));
2420       int i;
2421
2422       TREE_TYPE (a) = NULL_TREE;
2423       for (i = TREE_VEC_LENGTH (a) - 1; i >= 0; --i)
2424         {
2425           tree t = TREE_VEC_ELT (a, i);
2426
2427           /* T will be a list if we are called from within a
2428              begin/end_template_parm_list pair, but a vector directly
2429              if within a begin/end_member_template_processing pair.  */
2430           if (TREE_CODE (t) == TREE_LIST)
2431             {
2432               t = TREE_VALUE (t);
2433
2434               if (TREE_CODE (t) == TYPE_DECL
2435                   || TREE_CODE (t) == TEMPLATE_DECL)
2436                 t = TREE_TYPE (t);
2437               else
2438                 t = DECL_INITIAL (t);
2439               TREE_VEC_ELT (a, i) = t;
2440             }
2441         }
2442
2443       if (length > 1)
2444         TREE_VEC_ELT (args, --l) = a;
2445       else
2446         args = a;
2447     }
2448
2449   return args;
2450 }
2451
2452 /* Return a TEMPLATE_DECL corresponding to DECL, using the indicated
2453    template PARMS.  If MEMBER_TEMPLATE_P is true, the new template is
2454    a member template.  Used by push_template_decl below.  */
2455
2456 static tree
2457 build_template_decl (tree decl, tree parms, bool member_template_p)
2458 {
2459   tree tmpl = build_lang_decl (TEMPLATE_DECL, DECL_NAME (decl), NULL_TREE);
2460   DECL_TEMPLATE_PARMS (tmpl) = parms;
2461   DECL_CONTEXT (tmpl) = DECL_CONTEXT (decl);
2462   DECL_MEMBER_TEMPLATE_P (tmpl) = member_template_p;
2463   if (DECL_LANG_SPECIFIC (decl))
2464     {
2465       DECL_STATIC_FUNCTION_P (tmpl) = DECL_STATIC_FUNCTION_P (decl);
2466       DECL_CONSTRUCTOR_P (tmpl) = DECL_CONSTRUCTOR_P (decl);
2467       DECL_DESTRUCTOR_P (tmpl) = DECL_DESTRUCTOR_P (decl);
2468       DECL_NONCONVERTING_P (tmpl) = DECL_NONCONVERTING_P (decl);
2469       DECL_ASSIGNMENT_OPERATOR_P (tmpl) = DECL_ASSIGNMENT_OPERATOR_P (decl);
2470       if (DECL_OVERLOADED_OPERATOR_P (decl))
2471         SET_OVERLOADED_OPERATOR_CODE (tmpl,
2472                                       DECL_OVERLOADED_OPERATOR_P (decl));
2473     }
2474
2475   return tmpl;
2476 }
2477
2478 struct template_parm_data
2479 {
2480   /* The level of the template parameters we are currently
2481      processing.  */
2482   int level;
2483
2484   /* The index of the specialization argument we are currently
2485      processing.  */
2486   int current_arg;
2487
2488   /* An array whose size is the number of template parameters.  The
2489      elements are nonzero if the parameter has been used in any one
2490      of the arguments processed so far.  */
2491   int* parms;
2492
2493   /* An array whose size is the number of template arguments.  The
2494      elements are nonzero if the argument makes use of template
2495      parameters of this level.  */
2496   int* arg_uses_template_parms;
2497 };
2498
2499 /* Subroutine of push_template_decl used to see if each template
2500    parameter in a partial specialization is used in the explicit
2501    argument list.  If T is of the LEVEL given in DATA (which is
2502    treated as a template_parm_data*), then DATA->PARMS is marked
2503    appropriately.  */
2504
2505 static int
2506 mark_template_parm (tree t, void* data)
2507 {
2508   int level;
2509   int idx;
2510   struct template_parm_data* tpd = (struct template_parm_data*) data;
2511
2512   if (TREE_CODE (t) == TEMPLATE_PARM_INDEX)
2513     {
2514       level = TEMPLATE_PARM_LEVEL (t);
2515       idx = TEMPLATE_PARM_IDX (t);
2516     }
2517   else
2518     {
2519       level = TEMPLATE_TYPE_LEVEL (t);
2520       idx = TEMPLATE_TYPE_IDX (t);
2521     }
2522
2523   if (level == tpd->level)
2524     {
2525       tpd->parms[idx] = 1;
2526       tpd->arg_uses_template_parms[tpd->current_arg] = 1;
2527     }
2528
2529   /* Return zero so that for_each_template_parm will continue the
2530      traversal of the tree; we want to mark *every* template parm.  */
2531   return 0;
2532 }
2533
2534 /* Process the partial specialization DECL.  */
2535
2536 static tree
2537 process_partial_specialization (tree decl)
2538 {
2539   tree type = TREE_TYPE (decl);
2540   tree maintmpl = CLASSTYPE_TI_TEMPLATE (type);
2541   tree specargs = CLASSTYPE_TI_ARGS (type);
2542   tree inner_args = INNERMOST_TEMPLATE_ARGS (specargs);
2543   tree inner_parms = INNERMOST_TEMPLATE_PARMS (current_template_parms);
2544   tree main_inner_parms = DECL_INNERMOST_TEMPLATE_PARMS (maintmpl);
2545   int nargs = TREE_VEC_LENGTH (inner_args);
2546   int ntparms = TREE_VEC_LENGTH (inner_parms);
2547   int  i;
2548   int did_error_intro = 0;
2549   struct template_parm_data tpd;
2550   struct template_parm_data tpd2;
2551
2552   /* We check that each of the template parameters given in the
2553      partial specialization is used in the argument list to the
2554      specialization.  For example:
2555
2556        template <class T> struct S;
2557        template <class T> struct S<T*>;
2558
2559      The second declaration is OK because `T*' uses the template
2560      parameter T, whereas
2561
2562        template <class T> struct S<int>;
2563
2564      is no good.  Even trickier is:
2565
2566        template <class T>
2567        struct S1
2568        {
2569           template <class U>
2570           struct S2;
2571           template <class U>
2572           struct S2<T>;
2573        };
2574
2575      The S2<T> declaration is actually invalid; it is a
2576      full-specialization.  Of course,
2577
2578           template <class U>
2579           struct S2<T (*)(U)>;
2580
2581      or some such would have been OK.  */
2582   tpd.level = TMPL_PARMS_DEPTH (current_template_parms);
2583   tpd.parms = alloca (sizeof (int) * ntparms);
2584   memset (tpd.parms, 0, sizeof (int) * ntparms);
2585
2586   tpd.arg_uses_template_parms = alloca (sizeof (int) * nargs);
2587   memset (tpd.arg_uses_template_parms, 0, sizeof (int) * nargs);
2588   for (i = 0; i < nargs; ++i)
2589     {
2590       tpd.current_arg = i;
2591       for_each_template_parm (TREE_VEC_ELT (inner_args, i),
2592                               &mark_template_parm,
2593                               &tpd,
2594                               NULL);
2595     }
2596   for (i = 0; i < ntparms; ++i)
2597     if (tpd.parms[i] == 0)
2598       {
2599         /* One of the template parms was not used in the
2600            specialization.  */
2601         if (!did_error_intro)
2602           {
2603             error ("template parameters not used in partial specialization:");
2604             did_error_intro = 1;
2605           }
2606
2607         error ("        %qD", TREE_VALUE (TREE_VEC_ELT (inner_parms, i)));
2608       }
2609
2610   /* [temp.class.spec]
2611
2612      The argument list of the specialization shall not be identical to
2613      the implicit argument list of the primary template.  */
2614   if (comp_template_args
2615       (inner_args,
2616        INNERMOST_TEMPLATE_ARGS (CLASSTYPE_TI_ARGS (TREE_TYPE
2617                                                    (maintmpl)))))
2618     error ("partial specialization %qT does not specialize any template arguments", type);
2619
2620   /* [temp.class.spec]
2621
2622      A partially specialized non-type argument expression shall not
2623      involve template parameters of the partial specialization except
2624      when the argument expression is a simple identifier.
2625
2626      The type of a template parameter corresponding to a specialized
2627      non-type argument shall not be dependent on a parameter of the
2628      specialization.  */
2629   gcc_assert (nargs == DECL_NTPARMS (maintmpl));
2630   tpd2.parms = 0;
2631   for (i = 0; i < nargs; ++i)
2632     {
2633       tree arg = TREE_VEC_ELT (inner_args, i);
2634       if (/* These first two lines are the `non-type' bit.  */
2635           !TYPE_P (arg)
2636           && TREE_CODE (arg) != TEMPLATE_DECL
2637           /* This next line is the `argument expression is not just a
2638              simple identifier' condition and also the `specialized
2639              non-type argument' bit.  */
2640           && TREE_CODE (arg) != TEMPLATE_PARM_INDEX)
2641         {
2642           if (tpd.arg_uses_template_parms[i])
2643             error ("template argument %qE involves template parameter(s)", arg);
2644           else
2645             {
2646               /* Look at the corresponding template parameter,
2647                  marking which template parameters its type depends
2648                  upon.  */
2649               tree type =
2650                 TREE_TYPE (TREE_VALUE (TREE_VEC_ELT (main_inner_parms,
2651                                                      i)));
2652
2653               if (!tpd2.parms)
2654                 {
2655                   /* We haven't yet initialized TPD2.  Do so now.  */
2656                   tpd2.arg_uses_template_parms
2657                     = alloca (sizeof (int) * nargs);
2658                   /* The number of parameters here is the number in the
2659                      main template, which, as checked in the assertion
2660                      above, is NARGS.  */
2661                   tpd2.parms = alloca (sizeof (int) * nargs);
2662                   tpd2.level =
2663                     TMPL_PARMS_DEPTH (DECL_TEMPLATE_PARMS (maintmpl));
2664                 }
2665
2666               /* Mark the template parameters.  But this time, we're
2667                  looking for the template parameters of the main
2668                  template, not in the specialization.  */
2669               tpd2.current_arg = i;
2670               tpd2.arg_uses_template_parms[i] = 0;
2671               memset (tpd2.parms, 0, sizeof (int) * nargs);
2672               for_each_template_parm (type,
2673                                       &mark_template_parm,
2674                                       &tpd2,
2675                                       NULL);
2676
2677               if (tpd2.arg_uses_template_parms [i])
2678                 {
2679                   /* The type depended on some template parameters.
2680                      If they are fully specialized in the
2681                      specialization, that's OK.  */
2682                   int j;
2683                   for (j = 0; j < nargs; ++j)
2684                     if (tpd2.parms[j] != 0
2685                         && tpd.arg_uses_template_parms [j])
2686                       {
2687                         error ("type %qT of template argument %qE depends "
2688                                "on template parameter(s)",
2689                                type,
2690                                arg);
2691                         break;
2692                       }
2693                 }
2694             }
2695         }
2696     }
2697
2698   if (retrieve_specialization (maintmpl, specargs,
2699                                /*class_specializations_p=*/true))
2700     /* We've already got this specialization.  */
2701     return decl;
2702
2703   DECL_TEMPLATE_SPECIALIZATIONS (maintmpl)
2704     = tree_cons (inner_args, inner_parms,
2705                  DECL_TEMPLATE_SPECIALIZATIONS (maintmpl));
2706   TREE_TYPE (DECL_TEMPLATE_SPECIALIZATIONS (maintmpl)) = type;
2707   return decl;
2708 }
2709
2710 /* Check that a template declaration's use of default arguments is not
2711    invalid.  Here, PARMS are the template parameters.  IS_PRIMARY is
2712    nonzero if DECL is the thing declared by a primary template.
2713    IS_PARTIAL is nonzero if DECL is a partial specialization.  */
2714
2715 static void
2716 check_default_tmpl_args (tree decl, tree parms, int is_primary, int is_partial)
2717 {
2718   const char *msg;
2719   int last_level_to_check;
2720   tree parm_level;
2721
2722   /* [temp.param]
2723
2724      A default template-argument shall not be specified in a
2725      function template declaration or a function template definition, nor
2726      in the template-parameter-list of the definition of a member of a
2727      class template.  */
2728
2729   if (TREE_CODE (CP_DECL_CONTEXT (decl)) == FUNCTION_DECL)
2730     /* You can't have a function template declaration in a local
2731        scope, nor you can you define a member of a class template in a
2732        local scope.  */
2733     return;
2734
2735   if (current_class_type
2736       && !TYPE_BEING_DEFINED (current_class_type)
2737       && DECL_LANG_SPECIFIC (decl)
2738       /* If this is either a friend defined in the scope of the class
2739          or a member function.  */
2740       && (DECL_FUNCTION_MEMBER_P (decl)
2741           ? same_type_p (DECL_CONTEXT (decl), current_class_type)
2742           : DECL_FRIEND_CONTEXT (decl)
2743           ? same_type_p (DECL_FRIEND_CONTEXT (decl), current_class_type)
2744           : false)
2745       /* And, if it was a member function, it really was defined in
2746          the scope of the class.  */
2747       && (!DECL_FUNCTION_MEMBER_P (decl)
2748           || DECL_INITIALIZED_IN_CLASS_P (decl)))
2749     /* We already checked these parameters when the template was
2750        declared, so there's no need to do it again now.  This function
2751        was defined in class scope, but we're processing it's body now
2752        that the class is complete.  */
2753     return;
2754
2755   /* [temp.param]
2756
2757      If a template-parameter has a default template-argument, all
2758      subsequent template-parameters shall have a default
2759      template-argument supplied.  */
2760   for (parm_level = parms; parm_level; parm_level = TREE_CHAIN (parm_level))
2761     {
2762       tree inner_parms = TREE_VALUE (parm_level);
2763       int ntparms = TREE_VEC_LENGTH (inner_parms);
2764       int seen_def_arg_p = 0;
2765       int i;
2766
2767       for (i = 0; i < ntparms; ++i)
2768         {
2769           tree parm = TREE_VEC_ELT (inner_parms, i);
2770           if (TREE_PURPOSE (parm))
2771             seen_def_arg_p = 1;
2772           else if (seen_def_arg_p)
2773             {
2774               error ("no default argument for %qD", TREE_VALUE (parm));
2775               /* For better subsequent error-recovery, we indicate that
2776                  there should have been a default argument.  */
2777               TREE_PURPOSE (parm) = error_mark_node;
2778             }
2779         }
2780     }
2781
2782   if (TREE_CODE (decl) != TYPE_DECL || is_partial || !is_primary)
2783     /* For an ordinary class template, default template arguments are
2784        allowed at the innermost level, e.g.:
2785          template <class T = int>
2786          struct S {};
2787        but, in a partial specialization, they're not allowed even
2788        there, as we have in [temp.class.spec]:
2789
2790          The template parameter list of a specialization shall not
2791          contain default template argument values.
2792
2793        So, for a partial specialization, or for a function template,
2794        we look at all of them.  */
2795     ;
2796   else
2797     /* But, for a primary class template that is not a partial
2798        specialization we look at all template parameters except the
2799        innermost ones.  */
2800     parms = TREE_CHAIN (parms);
2801
2802   /* Figure out what error message to issue.  */
2803   if (TREE_CODE (decl) == FUNCTION_DECL)
2804     msg = "default template arguments may not be used in function templates";
2805   else if (is_partial)
2806     msg = "default template arguments may not be used in partial specializations";
2807   else
2808     msg = "default argument for template parameter for class enclosing %qD";
2809
2810   if (current_class_type && TYPE_BEING_DEFINED (current_class_type))
2811     /* If we're inside a class definition, there's no need to
2812        examine the parameters to the class itself.  On the one
2813        hand, they will be checked when the class is defined, and,
2814        on the other, default arguments are valid in things like:
2815          template <class T = double>
2816          struct S { template <class U> void f(U); };
2817        Here the default argument for `S' has no bearing on the
2818        declaration of `f'.  */
2819     last_level_to_check = template_class_depth (current_class_type) + 1;
2820   else
2821     /* Check everything.  */
2822     last_level_to_check = 0;
2823
2824   for (parm_level = parms;
2825        parm_level && TMPL_PARMS_DEPTH (parm_level) >= last_level_to_check;
2826        parm_level = TREE_CHAIN (parm_level))
2827     {
2828       tree inner_parms = TREE_VALUE (parm_level);
2829       int i;
2830       int ntparms;
2831
2832       ntparms = TREE_VEC_LENGTH (inner_parms);
2833       for (i = 0; i < ntparms; ++i)
2834         if (TREE_PURPOSE (TREE_VEC_ELT (inner_parms, i)))
2835           {
2836             if (msg)
2837               {
2838                 error (msg, decl);
2839                 msg = 0;
2840               }
2841
2842             /* Clear out the default argument so that we are not
2843                confused later.  */
2844             TREE_PURPOSE (TREE_VEC_ELT (inner_parms, i)) = NULL_TREE;
2845           }
2846
2847       /* At this point, if we're still interested in issuing messages,
2848          they must apply to classes surrounding the object declared.  */
2849       if (msg)
2850         msg = "default argument for template parameter for class enclosing %qD";
2851     }
2852 }
2853
2854 /* Worker for push_template_decl_real, called via
2855    for_each_template_parm.  DATA is really an int, indicating the
2856    level of the parameters we are interested in.  If T is a template
2857    parameter of that level, return nonzero.  */
2858
2859 static int
2860 template_parm_this_level_p (tree t, void* data)
2861 {
2862   int this_level = *(int *)data;
2863   int level;
2864
2865   if (TREE_CODE (t) == TEMPLATE_PARM_INDEX)
2866     level = TEMPLATE_PARM_LEVEL (t);
2867   else
2868     level = TEMPLATE_TYPE_LEVEL (t);
2869   return level == this_level;
2870 }
2871
2872 /* Creates a TEMPLATE_DECL for the indicated DECL using the template
2873    parameters given by current_template_args, or reuses a
2874    previously existing one, if appropriate.  Returns the DECL, or an
2875    equivalent one, if it is replaced via a call to duplicate_decls.
2876
2877    If IS_FRIEND is nonzero, DECL is a friend declaration.  */
2878
2879 tree
2880 push_template_decl_real (tree decl, int is_friend)
2881 {
2882   tree tmpl;
2883   tree args;
2884   tree info;
2885   tree ctx;
2886   int primary;
2887   int is_partial;
2888   int new_template_p = 0;
2889   /* True if the template is a member template, in the sense of
2890      [temp.mem].  */
2891   bool member_template_p = false;
2892
2893   if (decl == error_mark_node)
2894     return decl;
2895
2896   /* See if this is a partial specialization.  */
2897   is_partial = (DECL_IMPLICIT_TYPEDEF_P (decl)
2898                 && TREE_CODE (TREE_TYPE (decl)) != ENUMERAL_TYPE
2899                 && CLASSTYPE_TEMPLATE_SPECIALIZATION (TREE_TYPE (decl)));
2900
2901   is_friend |= (TREE_CODE (decl) == FUNCTION_DECL && DECL_FRIEND_P (decl));
2902
2903   if (is_friend)
2904     /* For a friend, we want the context of the friend function, not
2905        the type of which it is a friend.  */
2906     ctx = DECL_CONTEXT (decl);
2907   else if (CP_DECL_CONTEXT (decl)
2908            && TREE_CODE (CP_DECL_CONTEXT (decl)) != NAMESPACE_DECL)
2909     /* In the case of a virtual function, we want the class in which
2910        it is defined.  */
2911     ctx = CP_DECL_CONTEXT (decl);
2912   else
2913     /* Otherwise, if we're currently defining some class, the DECL
2914        is assumed to be a member of the class.  */
2915     ctx = current_scope ();
2916
2917   if (ctx && TREE_CODE (ctx) == NAMESPACE_DECL)
2918     ctx = NULL_TREE;
2919
2920   if (!DECL_CONTEXT (decl))
2921     DECL_CONTEXT (decl) = FROB_CONTEXT (current_namespace);
2922
2923   /* See if this is a primary template.  */
2924   primary = template_parm_scope_p ();
2925
2926   if (primary)
2927     {
2928       if (DECL_CLASS_SCOPE_P (decl))
2929         member_template_p = true;
2930       if (current_lang_name == lang_name_c)
2931         error ("template with C linkage");
2932       else if (TREE_CODE (decl) == TYPE_DECL
2933                && ANON_AGGRNAME_P (DECL_NAME (decl)))
2934         error ("template class without a name");
2935       else if (TREE_CODE (decl) == FUNCTION_DECL)
2936         {
2937           if (DECL_DESTRUCTOR_P (decl))
2938             {
2939               /* [temp.mem]
2940
2941                  A destructor shall not be a member template.  */
2942               error ("destructor %qD declared as member template", decl);
2943               return error_mark_node;
2944             }
2945           if (NEW_DELETE_OPNAME_P (DECL_NAME (decl))
2946               && (!TYPE_ARG_TYPES (TREE_TYPE (decl))
2947                   || TYPE_ARG_TYPES (TREE_TYPE (decl)) == void_list_node
2948                   || !TREE_CHAIN (TYPE_ARG_TYPES (TREE_TYPE (decl)))
2949                   || (TREE_CHAIN (TYPE_ARG_TYPES ((TREE_TYPE (decl))))
2950                       == void_list_node)))
2951             {
2952               /* [basic.stc.dynamic.allocation]
2953
2954                  An allocation function can be a function
2955                  template. ... Template allocation functions shall
2956                  have two or more parameters.  */
2957               error ("invalid template declaration of %qD", decl);
2958               return decl;
2959             }
2960         }
2961       else if ((DECL_IMPLICIT_TYPEDEF_P (decl)
2962                 && CLASS_TYPE_P (TREE_TYPE (decl)))
2963                || (TREE_CODE (decl) == VAR_DECL && ctx && CLASS_TYPE_P (ctx)))
2964         /* OK */;
2965       else
2966         {
2967           error ("template declaration of %q#D", decl);
2968           return error_mark_node;
2969         }
2970     }
2971
2972   /* Check to see that the rules regarding the use of default
2973      arguments are not being violated.  */
2974   check_default_tmpl_args (decl, current_template_parms,
2975                            primary, is_partial);
2976
2977   if (is_partial)
2978     return process_partial_specialization (decl);
2979
2980   args = current_template_args ();
2981
2982   if (!ctx
2983       || TREE_CODE (ctx) == FUNCTION_DECL
2984       || (CLASS_TYPE_P (ctx) && TYPE_BEING_DEFINED (ctx))
2985       || (is_friend && !DECL_TEMPLATE_INFO (decl)))
2986     {
2987       if (DECL_LANG_SPECIFIC (decl)
2988           && DECL_TEMPLATE_INFO (decl)
2989           && DECL_TI_TEMPLATE (decl))
2990         tmpl = DECL_TI_TEMPLATE (decl);
2991       /* If DECL is a TYPE_DECL for a class-template, then there won't
2992          be DECL_LANG_SPECIFIC.  The information equivalent to
2993          DECL_TEMPLATE_INFO is found in TYPE_TEMPLATE_INFO instead.  */
2994       else if (DECL_IMPLICIT_TYPEDEF_P (decl)
2995                && TYPE_TEMPLATE_INFO (TREE_TYPE (decl))
2996                && TYPE_TI_TEMPLATE (TREE_TYPE (decl)))
2997         {
2998           /* Since a template declaration already existed for this
2999              class-type, we must be redeclaring it here.  Make sure
3000              that the redeclaration is valid.  */
3001           redeclare_class_template (TREE_TYPE (decl),
3002                                     current_template_parms);
3003           /* We don't need to create a new TEMPLATE_DECL; just use the
3004              one we already had.  */
3005           tmpl = TYPE_TI_TEMPLATE (TREE_TYPE (decl));
3006         }
3007       else
3008         {
3009           tmpl = build_template_decl (decl, current_template_parms,
3010                                       member_template_p);
3011           new_template_p = 1;
3012
3013           if (DECL_LANG_SPECIFIC (decl)
3014               && DECL_TEMPLATE_SPECIALIZATION (decl))
3015             {
3016               /* A specialization of a member template of a template
3017                  class.  */
3018               SET_DECL_TEMPLATE_SPECIALIZATION (tmpl);
3019               DECL_TEMPLATE_INFO (tmpl) = DECL_TEMPLATE_INFO (decl);
3020               DECL_TEMPLATE_INFO (decl) = NULL_TREE;
3021             }
3022         }
3023     }
3024   else
3025     {
3026       tree a, t, current, parms;
3027       int i;
3028
3029       if (TREE_CODE (decl) == TYPE_DECL)
3030         {
3031           if ((IS_AGGR_TYPE_CODE (TREE_CODE (TREE_TYPE (decl)))
3032                || TREE_CODE (TREE_TYPE (decl)) == ENUMERAL_TYPE)
3033               && TYPE_TEMPLATE_INFO (TREE_TYPE (decl))
3034               && TYPE_TI_TEMPLATE (TREE_TYPE (decl)))
3035             tmpl = TYPE_TI_TEMPLATE (TREE_TYPE (decl));
3036           else
3037             {
3038               error ("%qD does not declare a template type", decl);
3039               return decl;
3040             }
3041         }
3042       else if (!DECL_LANG_SPECIFIC (decl) || !DECL_TEMPLATE_INFO (decl))
3043         {
3044           error ("template definition of non-template %q#D", decl);
3045           return decl;
3046         }
3047       else
3048         tmpl = DECL_TI_TEMPLATE (decl);
3049
3050       if (DECL_FUNCTION_TEMPLATE_P (tmpl)
3051           && DECL_TEMPLATE_INFO (decl) && DECL_TI_ARGS (decl)
3052           && DECL_TEMPLATE_SPECIALIZATION (decl)
3053           && DECL_MEMBER_TEMPLATE_P (tmpl))
3054         {
3055           tree new_tmpl;
3056
3057           /* The declaration is a specialization of a member
3058              template, declared outside the class.  Therefore, the
3059              innermost template arguments will be NULL, so we
3060              replace them with the arguments determined by the
3061              earlier call to check_explicit_specialization.  */
3062           args = DECL_TI_ARGS (decl);
3063
3064           new_tmpl
3065             = build_template_decl (decl, current_template_parms,
3066                                    member_template_p);
3067           DECL_TEMPLATE_RESULT (new_tmpl) = decl;
3068           TREE_TYPE (new_tmpl) = TREE_TYPE (decl);
3069           DECL_TI_TEMPLATE (decl) = new_tmpl;
3070           SET_DECL_TEMPLATE_SPECIALIZATION (new_tmpl);
3071           DECL_TEMPLATE_INFO (new_tmpl)
3072             = tree_cons (tmpl, args, NULL_TREE);
3073
3074           register_specialization (new_tmpl,
3075                                    most_general_template (tmpl),
3076                                    args);
3077           return decl;
3078         }
3079
3080       /* Make sure the template headers we got make sense.  */
3081
3082       parms = DECL_TEMPLATE_PARMS (tmpl);
3083       i = TMPL_PARMS_DEPTH (parms);
3084       if (TMPL_ARGS_DEPTH (args) != i)
3085         {
3086           error ("expected %d levels of template parms for %q#D, got %d",
3087                  i, decl, TMPL_ARGS_DEPTH (args));
3088         }
3089       else
3090         for (current = decl; i > 0; --i, parms = TREE_CHAIN (parms))
3091           {
3092             a = TMPL_ARGS_LEVEL (args, i);
3093             t = INNERMOST_TEMPLATE_PARMS (parms);
3094
3095             if (TREE_VEC_LENGTH (t) != TREE_VEC_LENGTH (a))
3096               {
3097                 if (current == decl)
3098                   error ("got %d template parameters for %q#D",
3099                          TREE_VEC_LENGTH (a), decl);
3100                 else
3101                   error ("got %d template parameters for %q#T",
3102                          TREE_VEC_LENGTH (a), current);
3103                 error ("  but %d required", TREE_VEC_LENGTH (t));
3104               }
3105
3106             /* Perhaps we should also check that the parms are used in the
3107                appropriate qualifying scopes in the declarator?  */
3108
3109             if (current == decl)
3110               current = ctx;
3111             else
3112               current = TYPE_CONTEXT (current);
3113           }
3114     }
3115
3116   DECL_TEMPLATE_RESULT (tmpl) = decl;
3117   TREE_TYPE (tmpl) = TREE_TYPE (decl);
3118
3119   /* Push template declarations for global functions and types.  Note
3120      that we do not try to push a global template friend declared in a
3121      template class; such a thing may well depend on the template
3122      parameters of the class.  */
3123   if (new_template_p && !ctx
3124       && !(is_friend && template_class_depth (current_class_type) > 0))
3125     {
3126       tmpl = pushdecl_namespace_level (tmpl);
3127       if (tmpl == error_mark_node)
3128         return error_mark_node;
3129
3130       /* Hide template friend classes that haven't been declared yet.  */
3131       if (is_friend && TREE_CODE (decl) == TYPE_DECL)
3132         {
3133           DECL_ANTICIPATED (tmpl) = 1;
3134           DECL_FRIEND_P (tmpl) = 1;
3135         }
3136     }
3137
3138   if (primary)
3139     {
3140       DECL_PRIMARY_TEMPLATE (tmpl) = tmpl;
3141       if (DECL_CONV_FN_P (tmpl))
3142         {
3143           int depth = TMPL_PARMS_DEPTH (DECL_TEMPLATE_PARMS (tmpl));
3144
3145           /* It is a conversion operator. See if the type converted to
3146              depends on innermost template operands.  */
3147
3148           if (uses_template_parms_level (TREE_TYPE (TREE_TYPE (tmpl)),
3149                                          depth))
3150             DECL_TEMPLATE_CONV_FN_P (tmpl) = 1;
3151         }
3152     }
3153
3154   /* The DECL_TI_ARGS of DECL contains full set of arguments referring
3155      back to its most general template.  If TMPL is a specialization,
3156      ARGS may only have the innermost set of arguments.  Add the missing
3157      argument levels if necessary.  */
3158   if (DECL_TEMPLATE_INFO (tmpl))
3159     args = add_outermost_template_args (DECL_TI_ARGS (tmpl), args);
3160
3161   info = tree_cons (tmpl, args, NULL_TREE);
3162
3163   if (DECL_IMPLICIT_TYPEDEF_P (decl))
3164     {
3165       SET_TYPE_TEMPLATE_INFO (TREE_TYPE (tmpl), info);
3166       if ((!ctx || TREE_CODE (ctx) != FUNCTION_DECL)
3167           && TREE_CODE (TREE_TYPE (decl)) != ENUMERAL_TYPE
3168           /* Don't change the name if we've already set it up.  */
3169           && !IDENTIFIER_TEMPLATE (DECL_NAME (decl)))
3170         DECL_NAME (decl) = classtype_mangled_name (TREE_TYPE (decl));
3171     }
3172   else if (DECL_LANG_SPECIFIC (decl))
3173     DECL_TEMPLATE_INFO (decl) = info;
3174
3175   return DECL_TEMPLATE_RESULT (tmpl);
3176 }
3177
3178 tree
3179 push_template_decl (tree decl)
3180 {
3181   return push_template_decl_real (decl, 0);
3182 }
3183
3184 /* Called when a class template TYPE is redeclared with the indicated
3185    template PARMS, e.g.:
3186
3187      template <class T> struct S;
3188      template <class T> struct S {};  */
3189
3190 void
3191 redeclare_class_template (tree type, tree parms)
3192 {
3193   tree tmpl;
3194   tree tmpl_parms;
3195   int i;
3196
3197   if (!TYPE_TEMPLATE_INFO (type))
3198     {
3199       error ("%qT is not a template type", type);
3200       return;
3201     }
3202
3203   tmpl = TYPE_TI_TEMPLATE (type);
3204   if (!PRIMARY_TEMPLATE_P (tmpl))
3205     /* The type is nested in some template class.  Nothing to worry
3206        about here; there are no new template parameters for the nested
3207        type.  */
3208     return;
3209
3210   if (!parms)
3211     {
3212       error ("template specifiers not specified in declaration of %qD",
3213              tmpl);
3214       return;
3215     }
3216
3217   parms = INNERMOST_TEMPLATE_PARMS (parms);
3218   tmpl_parms = DECL_INNERMOST_TEMPLATE_PARMS (tmpl);
3219
3220   if (TREE_VEC_LENGTH (parms) != TREE_VEC_LENGTH (tmpl_parms))
3221     {
3222       error ("previous declaration %q+D", tmpl);
3223       error ("used %d template parameter(s) instead of %d",
3224              TREE_VEC_LENGTH (tmpl_parms),
3225              TREE_VEC_LENGTH (parms));
3226       return;
3227     }
3228
3229   for (i = 0; i < TREE_VEC_LENGTH (tmpl_parms); ++i)
3230     {
3231       tree tmpl_parm = TREE_VALUE (TREE_VEC_ELT (tmpl_parms, i));
3232       tree parm = TREE_VALUE (TREE_VEC_ELT (parms, i));
3233       tree tmpl_default = TREE_PURPOSE (TREE_VEC_ELT (tmpl_parms, i));
3234       tree parm_default = TREE_PURPOSE (TREE_VEC_ELT (parms, i));
3235
3236       /* TMPL_PARM and PARM can be either TYPE_DECL, PARM_DECL, or
3237          TEMPLATE_DECL.  */
3238       if (TREE_CODE (tmpl_parm) != TREE_CODE (parm)
3239           || (TREE_CODE (tmpl_parm) != TYPE_DECL
3240               && !same_type_p (TREE_TYPE (tmpl_parm), TREE_TYPE (parm))))
3241         {
3242           error ("template parameter %q+#D", tmpl_parm);
3243           error ("redeclared here as %q#D", parm);
3244           return;
3245         }
3246
3247       if (tmpl_default != NULL_TREE && parm_default != NULL_TREE)
3248         {
3249           /* We have in [temp.param]:
3250
3251              A template-parameter may not be given default arguments
3252              by two different declarations in the same scope.  */
3253           error ("redefinition of default argument for %q#D", parm);
3254           error ("%J  original definition appeared here", tmpl_parm);
3255           return;
3256         }
3257
3258       if (parm_default != NULL_TREE)
3259         /* Update the previous template parameters (which are the ones
3260            that will really count) with the new default value.  */
3261         TREE_PURPOSE (TREE_VEC_ELT (tmpl_parms, i)) = parm_default;
3262       else if (tmpl_default != NULL_TREE)
3263         /* Update the new parameters, too; they'll be used as the
3264            parameters for any members.  */
3265         TREE_PURPOSE (TREE_VEC_ELT (parms, i)) = tmpl_default;
3266     }
3267 }
3268
3269 /* Simplify EXPR if it is a non-dependent expression.  Returns the
3270    (possibly simplified) expression.  */
3271
3272 tree
3273 fold_non_dependent_expr (tree expr)
3274 {
3275   /* If we're in a template, but EXPR isn't value dependent, simplify
3276      it.  We're supposed to treat:
3277
3278        template <typename T> void f(T[1 + 1]);
3279        template <typename T> void f(T[2]);
3280
3281      as two declarations of the same function, for example.  */
3282   if (processing_template_decl
3283       && !type_dependent_expression_p (expr)
3284       && !value_dependent_expression_p (expr))
3285     {
3286       HOST_WIDE_INT saved_processing_template_decl;
3287
3288       saved_processing_template_decl = processing_template_decl;
3289       processing_template_decl = 0;
3290       expr = tsubst_copy_and_build (expr,
3291                                     /*args=*/NULL_TREE,
3292                                     tf_error,
3293                                     /*in_decl=*/NULL_TREE,
3294                                     /*function_p=*/false);
3295       processing_template_decl = saved_processing_template_decl;
3296     }
3297   return expr;
3298 }
3299
3300 /* EXPR is an expression which is used in a constant-expression context.
3301    For instance, it could be a VAR_DECL with a constant initializer.
3302    Extract the innest constant expression.
3303
3304    This is basically a more powerful version of
3305    integral_constant_value, which can be used also in templates where
3306    initializers can maintain a syntactic rather than semantic form
3307    (even if they are non-dependent, for access-checking purposes).  */
3308
3309 tree
3310 fold_decl_constant_value (tree expr)
3311 {
3312   tree const_expr = expr;
3313   do
3314     {
3315       expr = fold_non_dependent_expr (const_expr);
3316       const_expr = integral_constant_value (expr);
3317     }
3318   while (expr != const_expr);
3319
3320   return expr;
3321 }
3322
3323 /* Subroutine of convert_nontype_argument. Converts EXPR to TYPE, which
3324    must be a function or a pointer-to-function type, as specified
3325    in [temp.arg.nontype]: disambiguate EXPR if it is an overload set,
3326    and check that the resulting function has external linkage.  */
3327
3328 static tree
3329 convert_nontype_argument_function (tree type, tree expr)
3330 {
3331   tree fns = expr;
3332   tree fn, fn_no_ptr;
3333
3334   fn = instantiate_type (type, fns, tf_none);
3335   if (fn == error_mark_node)
3336     return error_mark_node;
3337
3338   fn_no_ptr = fn;
3339   if (TREE_CODE (fn_no_ptr) == ADDR_EXPR)
3340     fn_no_ptr = TREE_OPERAND (fn_no_ptr, 0);
3341
3342   /* [temp.arg.nontype]/1
3343
3344      A template-argument for a non-type, non-template template-parameter
3345      shall be one of:
3346      [...]
3347      -- the address of an object or function with external linkage.  */
3348   if (!DECL_EXTERNAL_LINKAGE_P (fn_no_ptr))
3349     {
3350       error ("%qE is not a valid template argument for type %qT "
3351              "because function %qD has not external linkage",
3352              expr, type, fn_no_ptr);
3353       return NULL_TREE;
3354     }
3355
3356   return fn;
3357 }
3358
3359 /* Attempt to convert the non-type template parameter EXPR to the
3360    indicated TYPE.  If the conversion is successful, return the
3361    converted value.  If the conversion is unsuccessful, return
3362    NULL_TREE if we issued an error message, or error_mark_node if we
3363    did not.  We issue error messages for out-and-out bad template
3364    parameters, but not simply because the conversion failed, since we
3365    might be just trying to do argument deduction.  Both TYPE and EXPR
3366    must be non-dependent.
3367
3368    The conversion follows the special rules described in
3369    [temp.arg.nontype], and it is much more strict than an implicit
3370    conversion.
3371
3372    This function is called twice for each template argument (see
3373    lookup_template_class for a more accurate description of this
3374    problem). This means that we need to handle expressions which
3375    are not valid in a C++ source, but can be created from the
3376    first call (for instance, casts to perform conversions). These
3377    hacks can go away after we fix the double coercion problem.  */
3378
3379 static tree
3380 convert_nontype_argument (tree type, tree expr)
3381 {
3382   tree expr_type;
3383
3384   /* Detect immediately string literals as invalid non-type argument.
3385      This special-case is not needed for correctness (we would easily
3386      catch this later), but only to provide better diagnostic for this
3387      common user mistake. As suggested by DR 100, we do not mention
3388      linkage issues in the diagnostic as this is not the point.  */
3389   if (TREE_CODE (expr) == STRING_CST)
3390     {
3391       error ("%qE is not a valid template argument for type %qT "
3392              "because string literals can never be used in this context",
3393              expr, type);
3394       return NULL_TREE;
3395     }
3396
3397   /* If we are in a template, EXPR may be non-dependent, but still
3398      have a syntactic, rather than semantic, form.  For example, EXPR
3399      might be a SCOPE_REF, rather than the VAR_DECL to which the
3400      SCOPE_REF refers.  Preserving the qualifying scope is necessary
3401      so that access checking can be performed when the template is
3402      instantiated -- but here we need the resolved form so that we can
3403      convert the argument.  */
3404   expr = fold_non_dependent_expr (expr);
3405   expr_type = TREE_TYPE (expr);
3406
3407   /* HACK: Due to double coercion, we can get a
3408      NOP_EXPR<REFERENCE_TYPE>(ADDR_EXPR<POINTER_TYPE> (arg)) here,
3409      which is the tree that we built on the first call (see
3410      below when coercing to reference to object or to reference to
3411      function). We just strip everything and get to the arg.
3412      See g++.old-deja/g++.oliva/template4.C and g++.dg/template/nontype9.C
3413      for examples.  */
3414   if (TREE_CODE (expr) == NOP_EXPR)
3415     {
3416       if (TYPE_REF_OBJ_P (type) || TYPE_REFFN_P (type))
3417         {
3418           /* ??? Maybe we could use convert_from_reference here, but we
3419              would need to relax its constraints because the NOP_EXPR
3420              could actually change the type to something more cv-qualified,
3421              and this is not folded by convert_from_reference.  */
3422           tree addr = TREE_OPERAND (expr, 0);
3423           gcc_assert (TREE_CODE (expr_type) == REFERENCE_TYPE);
3424           gcc_assert (TREE_CODE (addr) == ADDR_EXPR);
3425           gcc_assert (TREE_CODE (TREE_TYPE (addr)) == POINTER_TYPE);
3426           gcc_assert (same_type_ignoring_top_level_qualifiers_p
3427                       (TREE_TYPE (expr_type),
3428                        TREE_TYPE (TREE_TYPE (addr))));
3429
3430           expr = TREE_OPERAND (addr, 0);
3431           expr_type = TREE_TYPE (expr);
3432         }
3433
3434       /* We could also generate a NOP_EXPR(ADDR_EXPR()) when the
3435          parameter is a pointer to object, through decay and
3436          qualification conversion. Let's strip everything.  */
3437       else if (TYPE_PTROBV_P (type))
3438         {
3439           STRIP_NOPS (expr);
3440           gcc_assert (TREE_CODE (expr) == ADDR_EXPR);
3441           gcc_assert (TREE_CODE (TREE_TYPE (expr)) == POINTER_TYPE);
3442           /* Skip the ADDR_EXPR only if it is part of the decay for
3443              an array. Otherwise, it is part of the original argument
3444              in the source code.  */
3445           if (TREE_CODE (TREE_TYPE (TREE_OPERAND (expr, 0))) == ARRAY_TYPE)
3446             expr = TREE_OPERAND (expr, 0);
3447           expr_type = TREE_TYPE (expr);
3448         }
3449     }
3450
3451   /* [temp.arg.nontype]/5, bullet 1
3452
3453      For a non-type template-parameter of integral or enumeration type,
3454      integral promotions (_conv.prom_) and integral conversions
3455      (_conv.integral_) are applied.  */
3456   if (INTEGRAL_TYPE_P (type))
3457     {
3458       if (!INTEGRAL_TYPE_P (expr_type))
3459         return error_mark_node;
3460
3461       expr = fold_decl_constant_value (expr);
3462       /* Notice that there are constant expressions like '4 % 0' which
3463          do not fold into integer constants.  */
3464       if (TREE_CODE (expr) != INTEGER_CST)
3465         {
3466           error ("%qE is not a valid template argument for type %qT "
3467                  "because it is a non-constant expression", expr, type);
3468           return NULL_TREE;
3469         }
3470
3471       /* At this point, an implicit conversion does what we want,
3472          because we already know that the expression is of integral
3473          type.  */
3474       expr = ocp_convert (type, expr, CONV_IMPLICIT, LOOKUP_PROTECT);
3475       if (expr == error_mark_node)
3476         return error_mark_node;
3477
3478       /* Conversion was allowed: fold it to a bare integer constant.  */
3479       expr = fold (expr);
3480     }
3481   /* [temp.arg.nontype]/5, bullet 2
3482
3483      For a non-type template-parameter of type pointer to object,
3484      qualification conversions (_conv.qual_) and the array-to-pointer
3485      conversion (_conv.array_) are applied.  */
3486   else if (TYPE_PTROBV_P (type))
3487     {
3488       /* [temp.arg.nontype]/1  (TC1 version, DR 49):
3489
3490          A template-argument for a non-type, non-template template-parameter
3491          shall be one of: [...]
3492
3493          -- the name of a non-type template-parameter;
3494          -- the address of an object or function with external linkage, [...]
3495             expressed as "& id-expression" where the & is optional if the name
3496             refers to a function or array, or if the corresponding
3497             template-parameter is a reference.
3498
3499         Here, we do not care about functions, as they are invalid anyway
3500         for a parameter of type pointer-to-object.  */
3501       bool constant_address_p =
3502         (TREE_CODE (expr) == ADDR_EXPR
3503          || TREE_CODE (expr_type) == ARRAY_TYPE
3504          || (DECL_P (expr) && DECL_TEMPLATE_PARM_P (expr)));
3505
3506       expr = decay_conversion (expr);
3507       if (expr == error_mark_node)
3508         return error_mark_node;
3509
3510       expr = perform_qualification_conversions (type, expr);
3511       if (expr == error_mark_node)
3512         return error_mark_node;
3513