OSDN Git Service

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