OSDN Git Service

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