OSDN Git Service

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