OSDN Git Service

767c4f6c584255154faaa701f81bf8c6749fc185
[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 ((chain_next ("%h.next"))) 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     pushclass (NULL_TREE);
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     popclass ();
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_NEXT (arg))
1520         val = iterative_hash_template_arg (OVL_CURRENT (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         {
1537           val = iterative_hash_object (DECL_PARM_INDEX (arg), val);
1538           val = iterative_hash_object (DECL_PARM_LEVEL (arg), val);
1539         }
1540       return iterative_hash_template_arg (TREE_TYPE (arg), val);
1541
1542     case TARGET_EXPR:
1543       return iterative_hash_template_arg (TARGET_EXPR_INITIAL (arg), val);
1544
1545     case PTRMEM_CST:
1546       val = iterative_hash_template_arg (PTRMEM_CST_CLASS (arg), val);
1547       return iterative_hash_template_arg (PTRMEM_CST_MEMBER (arg), val);
1548
1549     case TEMPLATE_PARM_INDEX:
1550       val = iterative_hash_template_arg
1551         (TREE_TYPE (TEMPLATE_PARM_DECL (arg)), val);
1552       val = iterative_hash_object (TEMPLATE_PARM_LEVEL (arg), val);
1553       return iterative_hash_object (TEMPLATE_PARM_IDX (arg), val);
1554
1555     case TRAIT_EXPR:
1556       val = iterative_hash_object (TRAIT_EXPR_KIND (arg), val);
1557       val = iterative_hash_template_arg (TRAIT_EXPR_TYPE1 (arg), val);
1558       return iterative_hash_template_arg (TRAIT_EXPR_TYPE2 (arg), val);
1559
1560     case BASELINK:
1561       val = iterative_hash_template_arg (BINFO_TYPE (BASELINK_BINFO (arg)),
1562                                          val);
1563       return iterative_hash_template_arg (DECL_NAME (get_first_fn (arg)),
1564                                           val);
1565
1566     case MODOP_EXPR:
1567       val = iterative_hash_template_arg (TREE_OPERAND (arg, 0), val);
1568       code = TREE_CODE (TREE_OPERAND (arg, 1));
1569       val = iterative_hash_object (code, val);
1570       return iterative_hash_template_arg (TREE_OPERAND (arg, 2), val);
1571
1572     case LAMBDA_EXPR:
1573       /* A lambda can't appear in a template arg, but don't crash on
1574          erroneous input.  */
1575       gcc_assert (seen_error ());
1576       return val;
1577
1578     case CAST_EXPR:
1579     case STATIC_CAST_EXPR:
1580     case REINTERPRET_CAST_EXPR:
1581     case CONST_CAST_EXPR:
1582     case DYNAMIC_CAST_EXPR:
1583     case NEW_EXPR:
1584       val = iterative_hash_template_arg (TREE_TYPE (arg), val);
1585       /* Now hash operands as usual.  */
1586       break;
1587
1588     default:
1589       break;
1590     }
1591
1592   switch (tclass)
1593     {
1594     case tcc_type:
1595       if (TYPE_CANONICAL (arg))
1596         return iterative_hash_object (TYPE_HASH (TYPE_CANONICAL (arg)),
1597                                       val);
1598       else if (TREE_CODE (arg) == DECLTYPE_TYPE)
1599         return iterative_hash_template_arg (DECLTYPE_TYPE_EXPR (arg), val);
1600       /* Otherwise just compare the types during lookup.  */
1601       return val;
1602
1603     case tcc_declaration:
1604     case tcc_constant:
1605       return iterative_hash_expr (arg, val);
1606
1607     default:
1608       gcc_assert (IS_EXPR_CODE_CLASS (tclass));
1609       {
1610         unsigned n = TREE_OPERAND_LENGTH (arg);
1611         for (i = 0; i < n; ++i)
1612           val = iterative_hash_template_arg (TREE_OPERAND (arg, i), val);
1613         return val;
1614       }
1615     }
1616   gcc_unreachable ();
1617   return 0;
1618 }
1619
1620 /* Unregister the specialization SPEC as a specialization of TMPL.
1621    Replace it with NEW_SPEC, if NEW_SPEC is non-NULL.  Returns true
1622    if the SPEC was listed as a specialization of TMPL.
1623
1624    Note that SPEC has been ggc_freed, so we can't look inside it.  */
1625
1626 bool
1627 reregister_specialization (tree spec, tree tinfo, tree new_spec)
1628 {
1629   spec_entry **slot;
1630   spec_entry elt;
1631
1632   elt.tmpl = most_general_template (TI_TEMPLATE (tinfo));
1633   elt.args = TI_ARGS (tinfo);
1634   elt.spec = NULL_TREE;
1635
1636   slot = (spec_entry **) htab_find_slot (decl_specializations, &elt, INSERT);
1637   if (*slot)
1638     {
1639       gcc_assert ((*slot)->spec == spec || (*slot)->spec == new_spec);
1640       gcc_assert (new_spec != NULL_TREE);
1641       (*slot)->spec = new_spec;
1642       return 1;
1643     }
1644
1645   return 0;
1646 }
1647
1648 /* Compare an entry in the local specializations hash table P1 (which
1649    is really a pointer to a TREE_LIST) with P2 (which is really a
1650    DECL).  */
1651
1652 static int
1653 eq_local_specializations (const void *p1, const void *p2)
1654 {
1655   return TREE_VALUE ((const_tree) p1) == (const_tree) p2;
1656 }
1657
1658 /* Hash P1, an entry in the local specializations table.  */
1659
1660 static hashval_t
1661 hash_local_specialization (const void* p1)
1662 {
1663   return htab_hash_pointer (TREE_VALUE ((const_tree) p1));
1664 }
1665
1666 /* Like register_specialization, but for local declarations.  We are
1667    registering SPEC, an instantiation of TMPL.  */
1668
1669 static void
1670 register_local_specialization (tree spec, tree tmpl)
1671 {
1672   void **slot;
1673
1674   slot = htab_find_slot_with_hash (local_specializations, tmpl,
1675                                    htab_hash_pointer (tmpl), INSERT);
1676   *slot = build_tree_list (spec, tmpl);
1677 }
1678
1679 /* TYPE is a class type.  Returns true if TYPE is an explicitly
1680    specialized class.  */
1681
1682 bool
1683 explicit_class_specialization_p (tree type)
1684 {
1685   if (!CLASSTYPE_TEMPLATE_SPECIALIZATION (type))
1686     return false;
1687   return !uses_template_parms (CLASSTYPE_TI_ARGS (type));
1688 }
1689
1690 /* Print the list of functions at FNS, going through all the overloads
1691    for each element of the list.  Alternatively, FNS can not be a
1692    TREE_LIST, in which case it will be printed together with all the
1693    overloads.
1694
1695    MORE and *STR should respectively be FALSE and NULL when the function
1696    is called from the outside.  They are used internally on recursive
1697    calls.  print_candidates manages the two parameters and leaves NULL
1698    in *STR when it ends.  */
1699
1700 static void
1701 print_candidates_1 (tree fns, bool more, const char **str)
1702 {
1703   tree fn, fn2;
1704   char *spaces = NULL;
1705
1706   for (fn = fns; fn; fn = OVL_NEXT (fn))
1707     if (TREE_CODE (fn) == TREE_LIST)
1708       {
1709         for (fn2 = fn; fn2 != NULL_TREE; fn2 = TREE_CHAIN (fn2))
1710           print_candidates_1 (TREE_VALUE (fn2),
1711                               TREE_CHAIN (fn2) || more, str);
1712       }
1713     else
1714       {
1715         if (!*str)
1716           {
1717             /* Pick the prefix string.  */
1718             if (!more && !OVL_NEXT (fns))
1719               {
1720                 error ("candidate is: %+#D", OVL_CURRENT (fn));
1721                 continue;
1722               }
1723
1724             *str = _("candidates are:");
1725             spaces = get_spaces (*str);
1726           }
1727         error ("%s %+#D", *str, OVL_CURRENT (fn));
1728         *str = spaces ? spaces : *str;
1729       }
1730
1731   if (!more)
1732     {
1733       free (spaces);
1734       *str = NULL;
1735     }
1736 }
1737
1738 /* Print the list of candidate FNS in an error message.  FNS can also
1739    be a TREE_LIST of non-functions in the case of an ambiguous lookup.  */
1740
1741 void
1742 print_candidates (tree fns)
1743 {
1744   const char *str = NULL;
1745   print_candidates_1 (fns, false, &str);
1746   gcc_assert (str == NULL);
1747 }
1748
1749 /* Returns the template (one of the functions given by TEMPLATE_ID)
1750    which can be specialized to match the indicated DECL with the
1751    explicit template args given in TEMPLATE_ID.  The DECL may be
1752    NULL_TREE if none is available.  In that case, the functions in
1753    TEMPLATE_ID are non-members.
1754
1755    If NEED_MEMBER_TEMPLATE is nonzero the function is known to be a
1756    specialization of a member template.
1757
1758    The TEMPLATE_COUNT is the number of references to qualifying
1759    template classes that appeared in the name of the function. See
1760    check_explicit_specialization for a more accurate description.
1761
1762    TSK indicates what kind of template declaration (if any) is being
1763    declared.  TSK_TEMPLATE indicates that the declaration given by
1764    DECL, though a FUNCTION_DECL, has template parameters, and is
1765    therefore a template function.
1766
1767    The template args (those explicitly specified and those deduced)
1768    are output in a newly created vector *TARGS_OUT.
1769
1770    If it is impossible to determine the result, an error message is
1771    issued.  The error_mark_node is returned to indicate failure.  */
1772
1773 static tree
1774 determine_specialization (tree template_id,
1775                           tree decl,
1776                           tree* targs_out,
1777                           int need_member_template,
1778                           int template_count,
1779                           tmpl_spec_kind tsk)
1780 {
1781   tree fns;
1782   tree targs;
1783   tree explicit_targs;
1784   tree candidates = NULL_TREE;
1785   /* A TREE_LIST of templates of which DECL may be a specialization.
1786      The TREE_VALUE of each node is a TEMPLATE_DECL.  The
1787      corresponding TREE_PURPOSE is the set of template arguments that,
1788      when used to instantiate the template, would produce a function
1789      with the signature of DECL.  */
1790   tree templates = NULL_TREE;
1791   int header_count;
1792   struct cp_binding_level *b;
1793
1794   *targs_out = NULL_TREE;
1795
1796   if (template_id == error_mark_node || decl == error_mark_node)
1797     return error_mark_node;
1798
1799   fns = TREE_OPERAND (template_id, 0);
1800   explicit_targs = TREE_OPERAND (template_id, 1);
1801
1802   if (fns == error_mark_node)
1803     return error_mark_node;
1804
1805   /* Check for baselinks.  */
1806   if (BASELINK_P (fns))
1807     fns = BASELINK_FUNCTIONS (fns);
1808
1809   if (!is_overloaded_fn (fns))
1810     {
1811       error ("%qD is not a function template", fns);
1812       return error_mark_node;
1813     }
1814
1815   /* Count the number of template headers specified for this
1816      specialization.  */
1817   header_count = 0;
1818   for (b = current_binding_level;
1819        b->kind == sk_template_parms;
1820        b = b->level_chain)
1821     ++header_count;
1822
1823   for (; fns; fns = OVL_NEXT (fns))
1824     {
1825       tree fn = OVL_CURRENT (fns);
1826
1827       if (TREE_CODE (fn) == TEMPLATE_DECL)
1828         {
1829           tree decl_arg_types;
1830           tree fn_arg_types;
1831
1832           /* In case of explicit specialization, we need to check if
1833              the number of template headers appearing in the specialization
1834              is correct. This is usually done in check_explicit_specialization,
1835              but the check done there cannot be exhaustive when specializing
1836              member functions. Consider the following code:
1837
1838              template <> void A<int>::f(int);
1839              template <> template <> void A<int>::f(int);
1840
1841              Assuming that A<int> is not itself an explicit specialization
1842              already, the first line specializes "f" which is a non-template
1843              member function, whilst the second line specializes "f" which
1844              is a template member function. So both lines are syntactically
1845              correct, and check_explicit_specialization does not reject
1846              them.
1847
1848              Here, we can do better, as we are matching the specialization
1849              against the declarations. We count the number of template
1850              headers, and we check if they match TEMPLATE_COUNT + 1
1851              (TEMPLATE_COUNT is the number of qualifying template classes,
1852              plus there must be another header for the member template
1853              itself).
1854
1855              Notice that if header_count is zero, this is not a
1856              specialization but rather a template instantiation, so there
1857              is no check we can perform here.  */
1858           if (header_count && header_count != template_count + 1)
1859             continue;
1860
1861           /* Check that the number of template arguments at the
1862              innermost level for DECL is the same as for FN.  */
1863           if (current_binding_level->kind == sk_template_parms
1864               && !current_binding_level->explicit_spec_p
1865               && (TREE_VEC_LENGTH (DECL_INNERMOST_TEMPLATE_PARMS (fn))
1866                   != TREE_VEC_LENGTH (INNERMOST_TEMPLATE_PARMS
1867                                       (current_template_parms))))
1868             continue;
1869
1870           /* DECL might be a specialization of FN.  */
1871           decl_arg_types = TYPE_ARG_TYPES (TREE_TYPE (decl));
1872           fn_arg_types = TYPE_ARG_TYPES (TREE_TYPE (fn));
1873
1874           /* For a non-static member function, we need to make sure
1875              that the const qualification is the same.  Since
1876              get_bindings does not try to merge the "this" parameter,
1877              we must do the comparison explicitly.  */
1878           if (DECL_NONSTATIC_MEMBER_FUNCTION_P (fn)
1879               && !same_type_p (TREE_VALUE (fn_arg_types),
1880                                TREE_VALUE (decl_arg_types)))
1881             continue;
1882
1883           /* Skip the "this" parameter and, for constructors of
1884              classes with virtual bases, the VTT parameter.  A
1885              full specialization of a constructor will have a VTT
1886              parameter, but a template never will.  */ 
1887           decl_arg_types 
1888             = skip_artificial_parms_for (decl, decl_arg_types);
1889           fn_arg_types 
1890             = skip_artificial_parms_for (fn, fn_arg_types);
1891
1892           /* Check that the number of function parameters matches.
1893              For example,
1894                template <class T> void f(int i = 0);
1895                template <> void f<int>();
1896              The specialization f<int> is invalid but is not caught
1897              by get_bindings below.  */
1898           if (list_length (fn_arg_types) != list_length (decl_arg_types))
1899             continue;
1900
1901           /* Function templates cannot be specializations; there are
1902              no partial specializations of functions.  Therefore, if
1903              the type of DECL does not match FN, there is no
1904              match.  */
1905           if (tsk == tsk_template)
1906             {
1907               if (compparms (fn_arg_types, decl_arg_types))
1908                 candidates = tree_cons (NULL_TREE, fn, candidates);
1909               continue;
1910             }
1911
1912           /* See whether this function might be a specialization of this
1913              template.  */
1914           targs = get_bindings (fn, decl, explicit_targs, /*check_ret=*/true);
1915
1916           if (!targs)
1917             /* We cannot deduce template arguments that when used to
1918                specialize TMPL will produce DECL.  */
1919             continue;
1920
1921           /* Save this template, and the arguments deduced.  */
1922           templates = tree_cons (targs, fn, templates);
1923         }
1924       else if (need_member_template)
1925         /* FN is an ordinary member function, and we need a
1926            specialization of a member template.  */
1927         ;
1928       else if (TREE_CODE (fn) != FUNCTION_DECL)
1929         /* We can get IDENTIFIER_NODEs here in certain erroneous
1930            cases.  */
1931         ;
1932       else if (!DECL_FUNCTION_MEMBER_P (fn))
1933         /* This is just an ordinary non-member function.  Nothing can
1934            be a specialization of that.  */
1935         ;
1936       else if (DECL_ARTIFICIAL (fn))
1937         /* Cannot specialize functions that are created implicitly.  */
1938         ;
1939       else
1940         {
1941           tree decl_arg_types;
1942
1943           /* This is an ordinary member function.  However, since
1944              we're here, we can assume it's enclosing class is a
1945              template class.  For example,
1946
1947                template <typename T> struct S { void f(); };
1948                template <> void S<int>::f() {}
1949
1950              Here, S<int>::f is a non-template, but S<int> is a
1951              template class.  If FN has the same type as DECL, we
1952              might be in business.  */
1953
1954           if (!DECL_TEMPLATE_INFO (fn))
1955             /* Its enclosing class is an explicit specialization
1956                of a template class.  This is not a candidate.  */
1957             continue;
1958
1959           if (!same_type_p (TREE_TYPE (TREE_TYPE (decl)),
1960                             TREE_TYPE (TREE_TYPE (fn))))
1961             /* The return types differ.  */
1962             continue;
1963
1964           /* Adjust the type of DECL in case FN is a static member.  */
1965           decl_arg_types = TYPE_ARG_TYPES (TREE_TYPE (decl));
1966           if (DECL_STATIC_FUNCTION_P (fn)
1967               && DECL_NONSTATIC_MEMBER_FUNCTION_P (decl))
1968             decl_arg_types = TREE_CHAIN (decl_arg_types);
1969
1970           if (compparms (TYPE_ARG_TYPES (TREE_TYPE (fn)),
1971                          decl_arg_types))
1972             /* They match!  */
1973             candidates = tree_cons (NULL_TREE, fn, candidates);
1974         }
1975     }
1976
1977   if (templates && TREE_CHAIN (templates))
1978     {
1979       /* We have:
1980
1981            [temp.expl.spec]
1982
1983            It is possible for a specialization with a given function
1984            signature to be instantiated from more than one function
1985            template.  In such cases, explicit specification of the
1986            template arguments must be used to uniquely identify the
1987            function template specialization being specialized.
1988
1989          Note that here, there's no suggestion that we're supposed to
1990          determine which of the candidate templates is most
1991          specialized.  However, we, also have:
1992
1993            [temp.func.order]
1994
1995            Partial ordering of overloaded function template
1996            declarations is used in the following contexts to select
1997            the function template to which a function template
1998            specialization refers:
1999
2000            -- when an explicit specialization refers to a function
2001               template.
2002
2003          So, we do use the partial ordering rules, at least for now.
2004          This extension can only serve to make invalid programs valid,
2005          so it's safe.  And, there is strong anecdotal evidence that
2006          the committee intended the partial ordering rules to apply;
2007          the EDG front end has that behavior, and John Spicer claims
2008          that the committee simply forgot to delete the wording in
2009          [temp.expl.spec].  */
2010       tree tmpl = most_specialized_instantiation (templates);
2011       if (tmpl != error_mark_node)
2012         {
2013           templates = tmpl;
2014           TREE_CHAIN (templates) = NULL_TREE;
2015         }
2016     }
2017
2018   if (templates == NULL_TREE && candidates == NULL_TREE)
2019     {
2020       error ("template-id %qD for %q+D does not match any template "
2021              "declaration", template_id, decl);
2022       if (header_count && header_count != template_count + 1)
2023         inform (input_location, "saw %d %<template<>%>, need %d for "
2024                 "specializing a member function template",
2025                 header_count, template_count + 1);
2026       return error_mark_node;
2027     }
2028   else if ((templates && TREE_CHAIN (templates))
2029            || (candidates && TREE_CHAIN (candidates))
2030            || (templates && candidates))
2031     {
2032       error ("ambiguous template specialization %qD for %q+D",
2033              template_id, decl);
2034       candidates = chainon (candidates, templates);
2035       print_candidates (candidates);
2036       return error_mark_node;
2037     }
2038
2039   /* We have one, and exactly one, match.  */
2040   if (candidates)
2041     {
2042       tree fn = TREE_VALUE (candidates);
2043       *targs_out = copy_node (DECL_TI_ARGS (fn));
2044       /* DECL is a re-declaration or partial instantiation of a template
2045          function.  */
2046       if (TREE_CODE (fn) == TEMPLATE_DECL)
2047         return fn;
2048       /* It was a specialization of an ordinary member function in a
2049          template class.  */
2050       return DECL_TI_TEMPLATE (fn);
2051     }
2052
2053   /* It was a specialization of a template.  */
2054   targs = DECL_TI_ARGS (DECL_TEMPLATE_RESULT (TREE_VALUE (templates)));
2055   if (TMPL_ARGS_HAVE_MULTIPLE_LEVELS (targs))
2056     {
2057       *targs_out = copy_node (targs);
2058       SET_TMPL_ARGS_LEVEL (*targs_out,
2059                            TMPL_ARGS_DEPTH (*targs_out),
2060                            TREE_PURPOSE (templates));
2061     }
2062   else
2063     *targs_out = TREE_PURPOSE (templates);
2064   return TREE_VALUE (templates);
2065 }
2066
2067 /* Returns a chain of parameter types, exactly like the SPEC_TYPES,
2068    but with the default argument values filled in from those in the
2069    TMPL_TYPES.  */
2070
2071 static tree
2072 copy_default_args_to_explicit_spec_1 (tree spec_types,
2073                                       tree tmpl_types)
2074 {
2075   tree new_spec_types;
2076
2077   if (!spec_types)
2078     return NULL_TREE;
2079
2080   if (spec_types == void_list_node)
2081     return void_list_node;
2082
2083   /* Substitute into the rest of the list.  */
2084   new_spec_types =
2085     copy_default_args_to_explicit_spec_1 (TREE_CHAIN (spec_types),
2086                                           TREE_CHAIN (tmpl_types));
2087
2088   /* Add the default argument for this parameter.  */
2089   return hash_tree_cons (TREE_PURPOSE (tmpl_types),
2090                          TREE_VALUE (spec_types),
2091                          new_spec_types);
2092 }
2093
2094 /* DECL is an explicit specialization.  Replicate default arguments
2095    from the template it specializes.  (That way, code like:
2096
2097      template <class T> void f(T = 3);
2098      template <> void f(double);
2099      void g () { f (); }
2100
2101    works, as required.)  An alternative approach would be to look up
2102    the correct default arguments at the call-site, but this approach
2103    is consistent with how implicit instantiations are handled.  */
2104
2105 static void
2106 copy_default_args_to_explicit_spec (tree decl)
2107 {
2108   tree tmpl;
2109   tree spec_types;
2110   tree tmpl_types;
2111   tree new_spec_types;
2112   tree old_type;
2113   tree new_type;
2114   tree t;
2115   tree object_type = NULL_TREE;
2116   tree in_charge = NULL_TREE;
2117   tree vtt = NULL_TREE;
2118
2119   /* See if there's anything we need to do.  */
2120   tmpl = DECL_TI_TEMPLATE (decl);
2121   tmpl_types = TYPE_ARG_TYPES (TREE_TYPE (DECL_TEMPLATE_RESULT (tmpl)));
2122   for (t = tmpl_types; t; t = TREE_CHAIN (t))
2123     if (TREE_PURPOSE (t))
2124       break;
2125   if (!t)
2126     return;
2127
2128   old_type = TREE_TYPE (decl);
2129   spec_types = TYPE_ARG_TYPES (old_type);
2130
2131   if (DECL_NONSTATIC_MEMBER_FUNCTION_P (decl))
2132     {
2133       /* Remove the this pointer, but remember the object's type for
2134          CV quals.  */
2135       object_type = TREE_TYPE (TREE_VALUE (spec_types));
2136       spec_types = TREE_CHAIN (spec_types);
2137       tmpl_types = TREE_CHAIN (tmpl_types);
2138
2139       if (DECL_HAS_IN_CHARGE_PARM_P (decl))
2140         {
2141           /* DECL may contain more parameters than TMPL due to the extra
2142              in-charge parameter in constructors and destructors.  */
2143           in_charge = spec_types;
2144           spec_types = TREE_CHAIN (spec_types);
2145         }
2146       if (DECL_HAS_VTT_PARM_P (decl))
2147         {
2148           vtt = spec_types;
2149           spec_types = TREE_CHAIN (spec_types);
2150         }
2151     }
2152
2153   /* Compute the merged default arguments.  */
2154   new_spec_types =
2155     copy_default_args_to_explicit_spec_1 (spec_types, tmpl_types);
2156
2157   /* Compute the new FUNCTION_TYPE.  */
2158   if (object_type)
2159     {
2160       if (vtt)
2161         new_spec_types = hash_tree_cons (TREE_PURPOSE (vtt),
2162                                          TREE_VALUE (vtt),
2163                                          new_spec_types);
2164
2165       if (in_charge)
2166         /* Put the in-charge parameter back.  */
2167         new_spec_types = hash_tree_cons (TREE_PURPOSE (in_charge),
2168                                          TREE_VALUE (in_charge),
2169                                          new_spec_types);
2170
2171       new_type = build_method_type_directly (object_type,
2172                                              TREE_TYPE (old_type),
2173                                              new_spec_types);
2174     }
2175   else
2176     new_type = build_function_type (TREE_TYPE (old_type),
2177                                     new_spec_types);
2178   new_type = cp_build_type_attribute_variant (new_type,
2179                                               TYPE_ATTRIBUTES (old_type));
2180   new_type = build_exception_variant (new_type,
2181                                       TYPE_RAISES_EXCEPTIONS (old_type));
2182   TREE_TYPE (decl) = new_type;
2183 }
2184
2185 /* Check to see if the function just declared, as indicated in
2186    DECLARATOR, and in DECL, is a specialization of a function
2187    template.  We may also discover that the declaration is an explicit
2188    instantiation at this point.
2189
2190    Returns DECL, or an equivalent declaration that should be used
2191    instead if all goes well.  Issues an error message if something is
2192    amiss.  Returns error_mark_node if the error is not easily
2193    recoverable.
2194
2195    FLAGS is a bitmask consisting of the following flags:
2196
2197    2: The function has a definition.
2198    4: The function is a friend.
2199
2200    The TEMPLATE_COUNT is the number of references to qualifying
2201    template classes that appeared in the name of the function.  For
2202    example, in
2203
2204      template <class T> struct S { void f(); };
2205      void S<int>::f();
2206
2207    the TEMPLATE_COUNT would be 1.  However, explicitly specialized
2208    classes are not counted in the TEMPLATE_COUNT, so that in
2209
2210      template <class T> struct S {};
2211      template <> struct S<int> { void f(); }
2212      template <> void S<int>::f();
2213
2214    the TEMPLATE_COUNT would be 0.  (Note that this declaration is
2215    invalid; there should be no template <>.)
2216
2217    If the function is a specialization, it is marked as such via
2218    DECL_TEMPLATE_SPECIALIZATION.  Furthermore, its DECL_TEMPLATE_INFO
2219    is set up correctly, and it is added to the list of specializations
2220    for that template.  */
2221
2222 tree
2223 check_explicit_specialization (tree declarator,
2224                                tree decl,
2225                                int template_count,
2226                                int flags)
2227 {
2228   int have_def = flags & 2;
2229   int is_friend = flags & 4;
2230   int specialization = 0;
2231   int explicit_instantiation = 0;
2232   int member_specialization = 0;
2233   tree ctype = DECL_CLASS_CONTEXT (decl);
2234   tree dname = DECL_NAME (decl);
2235   tmpl_spec_kind tsk;
2236
2237   if (is_friend)
2238     {
2239       if (!processing_specialization)
2240         tsk = tsk_none;
2241       else
2242         tsk = tsk_excessive_parms;
2243     }
2244   else
2245     tsk = current_tmpl_spec_kind (template_count);
2246
2247   switch (tsk)
2248     {
2249     case tsk_none:
2250       if (processing_specialization)
2251         {
2252           specialization = 1;
2253           SET_DECL_TEMPLATE_SPECIALIZATION (decl);
2254         }
2255       else if (TREE_CODE (declarator) == TEMPLATE_ID_EXPR)
2256         {
2257           if (is_friend)
2258             /* This could be something like:
2259
2260                template <class T> void f(T);
2261                class S { friend void f<>(int); }  */
2262             specialization = 1;
2263           else
2264             {
2265               /* This case handles bogus declarations like template <>
2266                  template <class T> void f<int>(); */
2267
2268               error ("template-id %qD in declaration of primary template",
2269                      declarator);
2270               return decl;
2271             }
2272         }
2273       break;
2274
2275     case tsk_invalid_member_spec:
2276       /* The error has already been reported in
2277          check_specialization_scope.  */
2278       return error_mark_node;
2279
2280     case tsk_invalid_expl_inst:
2281       error ("template parameter list used in explicit instantiation");
2282
2283       /* Fall through.  */
2284
2285     case tsk_expl_inst:
2286       if (have_def)
2287         error ("definition provided for explicit instantiation");
2288
2289       explicit_instantiation = 1;
2290       break;
2291
2292     case tsk_excessive_parms:
2293     case tsk_insufficient_parms:
2294       if (tsk == tsk_excessive_parms)
2295         error ("too many template parameter lists in declaration of %qD",
2296                decl);
2297       else if (template_header_count)
2298         error("too few template parameter lists in declaration of %qD", decl);
2299       else
2300         error("explicit specialization of %qD must be introduced by "
2301               "%<template <>%>", decl);
2302
2303       /* Fall through.  */
2304     case tsk_expl_spec:
2305       SET_DECL_TEMPLATE_SPECIALIZATION (decl);
2306       if (ctype)
2307         member_specialization = 1;
2308       else
2309         specialization = 1;
2310       break;
2311
2312     case tsk_template:
2313       if (TREE_CODE (declarator) == TEMPLATE_ID_EXPR)
2314         {
2315           /* This case handles bogus declarations like template <>
2316              template <class T> void f<int>(); */
2317
2318           if (uses_template_parms (declarator))
2319             error ("function template partial specialization %qD "
2320                    "is not allowed", declarator);
2321           else
2322             error ("template-id %qD in declaration of primary template",
2323                    declarator);
2324           return decl;
2325         }
2326
2327       if (ctype && CLASSTYPE_TEMPLATE_INSTANTIATION (ctype))
2328         /* This is a specialization of a member template, without
2329            specialization the containing class.  Something like:
2330
2331              template <class T> struct S {
2332                template <class U> void f (U);
2333              };
2334              template <> template <class U> void S<int>::f(U) {}
2335
2336            That's a specialization -- but of the entire template.  */
2337         specialization = 1;
2338       break;
2339
2340     default:
2341       gcc_unreachable ();
2342     }
2343
2344   if (specialization || member_specialization)
2345     {
2346       tree t = TYPE_ARG_TYPES (TREE_TYPE (decl));
2347       for (; t; t = TREE_CHAIN (t))
2348         if (TREE_PURPOSE (t))
2349           {
2350             permerror (input_location, 
2351                        "default argument specified in explicit specialization");
2352             break;
2353           }
2354     }
2355
2356   if (specialization || member_specialization || explicit_instantiation)
2357     {
2358       tree tmpl = NULL_TREE;
2359       tree targs = NULL_TREE;
2360
2361       /* Make sure that the declarator is a TEMPLATE_ID_EXPR.  */
2362       if (TREE_CODE (declarator) != TEMPLATE_ID_EXPR)
2363         {
2364           tree fns;
2365
2366           gcc_assert (TREE_CODE (declarator) == IDENTIFIER_NODE);
2367           if (ctype)
2368             fns = dname;
2369           else
2370             {
2371               /* If there is no class context, the explicit instantiation
2372                  must be at namespace scope.  */
2373               gcc_assert (DECL_NAMESPACE_SCOPE_P (decl));
2374
2375               /* Find the namespace binding, using the declaration
2376                  context.  */
2377               fns = lookup_qualified_name (CP_DECL_CONTEXT (decl), dname,
2378                                            false, true);
2379               if (fns == error_mark_node || !is_overloaded_fn (fns))
2380                 {
2381                   error ("%qD is not a template function", dname);
2382                   fns = error_mark_node;
2383                 }
2384               else
2385                 {
2386                   tree fn = OVL_CURRENT (fns);
2387                   if (!is_associated_namespace (CP_DECL_CONTEXT (decl),
2388                                                 CP_DECL_CONTEXT (fn)))
2389                     error ("%qD is not declared in %qD",
2390                            decl, current_namespace);
2391                 }
2392             }
2393
2394           declarator = lookup_template_function (fns, NULL_TREE);
2395         }
2396
2397       if (declarator == error_mark_node)
2398         return error_mark_node;
2399
2400       if (ctype != NULL_TREE && TYPE_BEING_DEFINED (ctype))
2401         {
2402           if (!explicit_instantiation)
2403             /* A specialization in class scope.  This is invalid,
2404                but the error will already have been flagged by
2405                check_specialization_scope.  */
2406             return error_mark_node;
2407           else
2408             {
2409               /* It's not valid to write an explicit instantiation in
2410                  class scope, e.g.:
2411
2412                    class C { template void f(); }
2413
2414                    This case is caught by the parser.  However, on
2415                    something like:
2416
2417                    template class C { void f(); };
2418
2419                    (which is invalid) we can get here.  The error will be
2420                    issued later.  */
2421               ;
2422             }
2423
2424           return decl;
2425         }
2426       else if (ctype != NULL_TREE
2427                && (TREE_CODE (TREE_OPERAND (declarator, 0)) ==
2428                    IDENTIFIER_NODE))
2429         {
2430           /* Find the list of functions in ctype that have the same
2431              name as the declared function.  */
2432           tree name = TREE_OPERAND (declarator, 0);
2433           tree fns = NULL_TREE;
2434           int idx;
2435
2436           if (constructor_name_p (name, ctype))
2437             {
2438               int is_constructor = DECL_CONSTRUCTOR_P (decl);
2439
2440               if (is_constructor ? !TYPE_HAS_USER_CONSTRUCTOR (ctype)
2441                   : !CLASSTYPE_DESTRUCTORS (ctype))
2442                 {
2443                   /* From [temp.expl.spec]:
2444
2445                      If such an explicit specialization for the member
2446                      of a class template names an implicitly-declared
2447                      special member function (clause _special_), the
2448                      program is ill-formed.
2449
2450                      Similar language is found in [temp.explicit].  */
2451                   error ("specialization of implicitly-declared special member function");
2452                   return error_mark_node;
2453                 }
2454
2455               name = is_constructor ? ctor_identifier : dtor_identifier;
2456             }
2457
2458           if (!DECL_CONV_FN_P (decl))
2459             {
2460               idx = lookup_fnfields_1 (ctype, name);
2461               if (idx >= 0)
2462                 fns = VEC_index (tree, CLASSTYPE_METHOD_VEC (ctype), idx);
2463             }
2464           else
2465             {
2466               VEC(tree,gc) *methods;
2467               tree ovl;
2468
2469               /* For a type-conversion operator, we cannot do a
2470                  name-based lookup.  We might be looking for `operator
2471                  int' which will be a specialization of `operator T'.
2472                  So, we find *all* the conversion operators, and then
2473                  select from them.  */
2474               fns = NULL_TREE;
2475
2476               methods = CLASSTYPE_METHOD_VEC (ctype);
2477               if (methods)
2478                 for (idx = CLASSTYPE_FIRST_CONVERSION_SLOT;
2479                      VEC_iterate (tree, methods, idx, ovl);
2480                      ++idx)
2481                   {
2482                     if (!DECL_CONV_FN_P (OVL_CURRENT (ovl)))
2483                       /* There are no more conversion functions.  */
2484                       break;
2485
2486                     /* Glue all these conversion functions together
2487                        with those we already have.  */
2488                     for (; ovl; ovl = OVL_NEXT (ovl))
2489                       fns = ovl_cons (OVL_CURRENT (ovl), fns);
2490                   }
2491             }
2492
2493           if (fns == NULL_TREE)
2494             {
2495               error ("no member function %qD declared in %qT", name, ctype);
2496               return error_mark_node;
2497             }
2498           else
2499             TREE_OPERAND (declarator, 0) = fns;
2500         }
2501
2502       /* Figure out what exactly is being specialized at this point.
2503          Note that for an explicit instantiation, even one for a
2504          member function, we cannot tell apriori whether the
2505          instantiation is for a member template, or just a member
2506          function of a template class.  Even if a member template is
2507          being instantiated, the member template arguments may be
2508          elided if they can be deduced from the rest of the
2509          declaration.  */
2510       tmpl = determine_specialization (declarator, decl,
2511                                        &targs,
2512                                        member_specialization,
2513                                        template_count,
2514                                        tsk);
2515
2516       if (!tmpl || tmpl == error_mark_node)
2517         /* We couldn't figure out what this declaration was
2518            specializing.  */
2519         return error_mark_node;
2520       else
2521         {
2522           tree gen_tmpl = most_general_template (tmpl);
2523
2524           if (explicit_instantiation)
2525             {
2526               /* We don't set DECL_EXPLICIT_INSTANTIATION here; that
2527                  is done by do_decl_instantiation later.  */
2528
2529               int arg_depth = TMPL_ARGS_DEPTH (targs);
2530               int parm_depth = TMPL_PARMS_DEPTH (DECL_TEMPLATE_PARMS (tmpl));
2531
2532               if (arg_depth > parm_depth)
2533                 {
2534                   /* If TMPL is not the most general template (for
2535                      example, if TMPL is a friend template that is
2536                      injected into namespace scope), then there will
2537                      be too many levels of TARGS.  Remove some of them
2538                      here.  */
2539                   int i;
2540                   tree new_targs;
2541
2542                   new_targs = make_tree_vec (parm_depth);
2543                   for (i = arg_depth - parm_depth; i < arg_depth; ++i)
2544                     TREE_VEC_ELT (new_targs, i - (arg_depth - parm_depth))
2545                       = TREE_VEC_ELT (targs, i);
2546                   targs = new_targs;
2547                 }
2548
2549               return instantiate_template (tmpl, targs, tf_error);
2550             }
2551
2552           /* If we thought that the DECL was a member function, but it
2553              turns out to be specializing a static member function,
2554              make DECL a static member function as well.  */
2555           if (DECL_STATIC_FUNCTION_P (tmpl)
2556               && DECL_NONSTATIC_MEMBER_FUNCTION_P (decl))
2557             revert_static_member_fn (decl);
2558
2559           /* If this is a specialization of a member template of a
2560              template class, we want to return the TEMPLATE_DECL, not
2561              the specialization of it.  */
2562           if (tsk == tsk_template)
2563             {
2564               tree result = DECL_TEMPLATE_RESULT (tmpl);
2565               SET_DECL_TEMPLATE_SPECIALIZATION (tmpl);
2566               DECL_INITIAL (result) = NULL_TREE;
2567               if (have_def)
2568                 {
2569                   tree parm;
2570                   DECL_SOURCE_LOCATION (tmpl) = DECL_SOURCE_LOCATION (decl);
2571                   DECL_SOURCE_LOCATION (result)
2572                     = DECL_SOURCE_LOCATION (decl);
2573                   /* We want to use the argument list specified in the
2574                      definition, not in the original declaration.  */
2575                   DECL_ARGUMENTS (result) = DECL_ARGUMENTS (decl);
2576                   for (parm = DECL_ARGUMENTS (result); parm;
2577                        parm = DECL_CHAIN (parm))
2578                     DECL_CONTEXT (parm) = result;
2579                 }
2580               return register_specialization (tmpl, gen_tmpl, targs,
2581                                               is_friend, 0);
2582             }
2583
2584           /* Set up the DECL_TEMPLATE_INFO for DECL.  */
2585           DECL_TEMPLATE_INFO (decl) = build_template_info (tmpl, targs);
2586
2587           /* Inherit default function arguments from the template
2588              DECL is specializing.  */
2589           copy_default_args_to_explicit_spec (decl);
2590
2591           /* This specialization has the same protection as the
2592              template it specializes.  */
2593           TREE_PRIVATE (decl) = TREE_PRIVATE (gen_tmpl);
2594           TREE_PROTECTED (decl) = TREE_PROTECTED (gen_tmpl);
2595
2596           /* 7.1.1-1 [dcl.stc]
2597
2598              A storage-class-specifier shall not be specified in an
2599              explicit specialization...
2600
2601              The parser rejects these, so unless action is taken here,
2602              explicit function specializations will always appear with
2603              global linkage.
2604
2605              The action recommended by the C++ CWG in response to C++
2606              defect report 605 is to make the storage class and linkage
2607              of the explicit specialization match the templated function:
2608
2609              http://www.open-std.org/jtc1/sc22/wg21/docs/cwg_active.html#605
2610            */
2611           if (tsk == tsk_expl_spec && DECL_FUNCTION_TEMPLATE_P (gen_tmpl))
2612             {
2613               tree tmpl_func = DECL_TEMPLATE_RESULT (gen_tmpl);
2614               gcc_assert (TREE_CODE (tmpl_func) == FUNCTION_DECL);
2615
2616               /* This specialization has the same linkage and visibility as
2617                  the function template it specializes.  */
2618               TREE_PUBLIC (decl) = TREE_PUBLIC (tmpl_func);
2619               if (! TREE_PUBLIC (decl))
2620                 {
2621                   DECL_INTERFACE_KNOWN (decl) = 1;
2622                   DECL_NOT_REALLY_EXTERN (decl) = 1;
2623                 }
2624               DECL_THIS_STATIC (decl) = DECL_THIS_STATIC (tmpl_func);
2625               if (DECL_VISIBILITY_SPECIFIED (tmpl_func))
2626                 {
2627                   DECL_VISIBILITY_SPECIFIED (decl) = 1;
2628                   DECL_VISIBILITY (decl) = DECL_VISIBILITY (tmpl_func);
2629                 }
2630             }
2631
2632           /* If DECL is a friend declaration, declared using an
2633              unqualified name, the namespace associated with DECL may
2634              have been set incorrectly.  For example, in:
2635
2636                template <typename T> void f(T);
2637                namespace N {
2638                  struct S { friend void f<int>(int); }
2639                }
2640
2641              we will have set the DECL_CONTEXT for the friend
2642              declaration to N, rather than to the global namespace.  */
2643           if (DECL_NAMESPACE_SCOPE_P (decl))
2644             DECL_CONTEXT (decl) = DECL_CONTEXT (tmpl);
2645
2646           if (is_friend && !have_def)
2647             /* This is not really a declaration of a specialization.
2648                It's just the name of an instantiation.  But, it's not
2649                a request for an instantiation, either.  */
2650             SET_DECL_IMPLICIT_INSTANTIATION (decl);
2651           else if (DECL_CONSTRUCTOR_P (decl) || DECL_DESTRUCTOR_P (decl))
2652             /* This is indeed a specialization.  In case of constructors
2653                and destructors, we need in-charge and not-in-charge
2654                versions in V3 ABI.  */
2655             clone_function_decl (decl, /*update_method_vec_p=*/0);
2656
2657           /* Register this specialization so that we can find it
2658              again.  */
2659           decl = register_specialization (decl, gen_tmpl, targs, is_friend, 0);
2660         }
2661     }
2662
2663   return decl;
2664 }
2665
2666 /* Returns 1 iff PARMS1 and PARMS2 are identical sets of template
2667    parameters.  These are represented in the same format used for
2668    DECL_TEMPLATE_PARMS.  */
2669
2670 int
2671 comp_template_parms (const_tree parms1, const_tree parms2)
2672 {
2673   const_tree p1;
2674   const_tree p2;
2675
2676   if (parms1 == parms2)
2677     return 1;
2678
2679   for (p1 = parms1, p2 = parms2;
2680        p1 != NULL_TREE && p2 != NULL_TREE;
2681        p1 = TREE_CHAIN (p1), p2 = TREE_CHAIN (p2))
2682     {
2683       tree t1 = TREE_VALUE (p1);
2684       tree t2 = TREE_VALUE (p2);
2685       int i;
2686
2687       gcc_assert (TREE_CODE (t1) == TREE_VEC);
2688       gcc_assert (TREE_CODE (t2) == TREE_VEC);
2689
2690       if (TREE_VEC_LENGTH (t1) != TREE_VEC_LENGTH (t2))
2691         return 0;
2692
2693       for (i = 0; i < TREE_VEC_LENGTH (t2); ++i)
2694         {
2695           tree parm1 = TREE_VALUE (TREE_VEC_ELT (t1, i));
2696           tree parm2 = TREE_VALUE (TREE_VEC_ELT (t2, i));
2697
2698           /* If either of the template parameters are invalid, assume
2699              they match for the sake of error recovery. */
2700           if (parm1 == error_mark_node || parm2 == error_mark_node)
2701             return 1;
2702
2703           if (TREE_CODE (parm1) != TREE_CODE (parm2))
2704             return 0;
2705
2706           if (TREE_CODE (parm1) == TEMPLATE_TYPE_PARM
2707               && (TEMPLATE_TYPE_PARAMETER_PACK (parm1)
2708                   == TEMPLATE_TYPE_PARAMETER_PACK (parm2)))
2709             continue;
2710           else if (!same_type_p (TREE_TYPE (parm1), TREE_TYPE (parm2)))
2711             return 0;
2712         }
2713     }
2714
2715   if ((p1 != NULL_TREE) != (p2 != NULL_TREE))
2716     /* One set of parameters has more parameters lists than the
2717        other.  */
2718     return 0;
2719
2720   return 1;
2721 }
2722
2723 /* Determine whether PARM is a parameter pack.  */
2724
2725 bool 
2726 template_parameter_pack_p (const_tree parm)
2727 {
2728   /* Determine if we have a non-type template parameter pack.  */
2729   if (TREE_CODE (parm) == PARM_DECL)
2730     return (DECL_TEMPLATE_PARM_P (parm) 
2731             && TEMPLATE_PARM_PARAMETER_PACK (DECL_INITIAL (parm)));
2732
2733   /* If this is a list of template parameters, we could get a
2734      TYPE_DECL or a TEMPLATE_DECL.  */ 
2735   if (TREE_CODE (parm) == TYPE_DECL || TREE_CODE (parm) == TEMPLATE_DECL)
2736     parm = TREE_TYPE (parm);
2737
2738   return ((TREE_CODE (parm) == TEMPLATE_TYPE_PARM
2739            || TREE_CODE (parm) == TEMPLATE_TEMPLATE_PARM)
2740           && TEMPLATE_TYPE_PARAMETER_PACK (parm));
2741 }
2742
2743 /* Determine if T is a function parameter pack.  */
2744
2745 bool
2746 function_parameter_pack_p (const_tree t)
2747 {
2748   if (t && TREE_CODE (t) == PARM_DECL)
2749     return FUNCTION_PARAMETER_PACK_P (t);
2750   return false;
2751 }
2752
2753 /* Return the function template declaration of PRIMARY_FUNC_TMPL_INST.
2754    PRIMARY_FUNC_TMPL_INST is a primary function template instantiation.  */
2755
2756 tree
2757 get_function_template_decl (const_tree primary_func_tmpl_inst)
2758 {
2759   if (! primary_func_tmpl_inst
2760       || TREE_CODE (primary_func_tmpl_inst) != FUNCTION_DECL
2761       || ! primary_template_instantiation_p (primary_func_tmpl_inst))
2762     return NULL;
2763
2764   return DECL_TEMPLATE_RESULT (DECL_TI_TEMPLATE (primary_func_tmpl_inst));
2765 }
2766
2767 /* Return true iff the function parameter PARAM_DECL was expanded
2768    from the function parameter pack PACK.  */
2769
2770 bool
2771 function_parameter_expanded_from_pack_p (tree param_decl, tree pack)
2772 {
2773   if (DECL_ARTIFICIAL (param_decl)
2774       || !function_parameter_pack_p (pack))
2775     return false;
2776
2777   /* The parameter pack and its pack arguments have the same
2778      DECL_PARM_INDEX.  */
2779   return DECL_PARM_INDEX (pack) == DECL_PARM_INDEX (param_decl);
2780 }
2781
2782 /* Determine whether ARGS describes a variadic template args list,
2783    i.e., one that is terminated by a template argument pack.  */
2784
2785 static bool 
2786 template_args_variadic_p (tree args)
2787 {
2788   int nargs;
2789   tree last_parm;
2790
2791   if (args == NULL_TREE)
2792     return false;
2793
2794   args = INNERMOST_TEMPLATE_ARGS (args);
2795   nargs = TREE_VEC_LENGTH (args);
2796
2797   if (nargs == 0)
2798     return false;
2799
2800   last_parm = TREE_VEC_ELT (args, nargs - 1);
2801
2802   return ARGUMENT_PACK_P (last_parm);
2803 }
2804
2805 /* Generate a new name for the parameter pack name NAME (an
2806    IDENTIFIER_NODE) that incorporates its */
2807
2808 static tree
2809 make_ith_pack_parameter_name (tree name, int i)
2810 {
2811   /* Munge the name to include the parameter index.  */
2812 #define NUMBUF_LEN 128
2813   char numbuf[NUMBUF_LEN];
2814   char* newname;
2815   int newname_len;
2816
2817   snprintf (numbuf, NUMBUF_LEN, "%i", i);
2818   newname_len = IDENTIFIER_LENGTH (name)
2819                 + strlen (numbuf) + 2;
2820   newname = (char*)alloca (newname_len);
2821   snprintf (newname, newname_len,
2822             "%s#%i", IDENTIFIER_POINTER (name), i);
2823   return get_identifier (newname);
2824 }
2825
2826 /* Return true if T is a primary function
2827    or class template instantiation.  */
2828
2829 bool
2830 primary_template_instantiation_p (const_tree t)
2831 {
2832   if (!t)
2833     return false;
2834
2835   if (TREE_CODE (t) == FUNCTION_DECL)
2836     return DECL_LANG_SPECIFIC (t)
2837            && DECL_TEMPLATE_INSTANTIATION (t)
2838            && PRIMARY_TEMPLATE_P (DECL_TI_TEMPLATE (t));
2839   else if (CLASS_TYPE_P (t))
2840     return CLASSTYPE_TEMPLATE_INSTANTIATION (t)
2841            && PRIMARY_TEMPLATE_P (CLASSTYPE_TI_TEMPLATE (t));
2842   return false;
2843 }
2844
2845 /* Return true if PARM is a template template parameter.  */
2846
2847 bool
2848 template_template_parameter_p (const_tree parm)
2849 {
2850   return DECL_TEMPLATE_TEMPLATE_PARM_P (parm);
2851 }
2852
2853 /* Return the template parameters of T if T is a
2854    primary template instantiation, NULL otherwise.  */
2855
2856 tree
2857 get_primary_template_innermost_parameters (const_tree t)
2858 {
2859   tree parms = NULL, template_info = NULL;
2860
2861   if ((template_info = get_template_info (t))
2862       && primary_template_instantiation_p (t))
2863     parms = INNERMOST_TEMPLATE_PARMS
2864         (DECL_TEMPLATE_PARMS (TI_TEMPLATE (template_info)));
2865
2866   return parms;
2867 }
2868
2869 /* Return the template parameters of the LEVELth level from the full list
2870    of template parameters PARMS.  */
2871
2872 tree
2873 get_template_parms_at_level (tree parms, int level)
2874 {
2875   tree p;
2876   if (!parms
2877       || TREE_CODE (parms) != TREE_LIST
2878       || level > TMPL_PARMS_DEPTH (parms))
2879     return NULL_TREE;
2880
2881   for (p = parms; p; p = TREE_CHAIN (p))
2882     if (TMPL_PARMS_DEPTH (p) == level)
2883       return p;
2884
2885   return NULL_TREE;
2886 }
2887
2888 /* Returns the template arguments of T if T is a template instantiation,
2889    NULL otherwise.  */
2890
2891 tree
2892 get_template_innermost_arguments (const_tree t)
2893 {
2894   tree args = NULL, template_info = NULL;
2895
2896   if ((template_info = get_template_info (t))
2897       && TI_ARGS (template_info))
2898     args = INNERMOST_TEMPLATE_ARGS (TI_ARGS (template_info));
2899
2900   return args;
2901 }
2902
2903 /* Return the argument pack elements of T if T is a template argument pack,
2904    NULL otherwise.  */
2905
2906 tree
2907 get_template_argument_pack_elems (const_tree t)
2908 {
2909   if (TREE_CODE (t) != TYPE_ARGUMENT_PACK
2910       && TREE_CODE (t) != NONTYPE_ARGUMENT_PACK)
2911     return NULL;
2912
2913   return ARGUMENT_PACK_ARGS (t);
2914 }
2915
2916 /* Structure used to track the progress of find_parameter_packs_r.  */
2917 struct find_parameter_pack_data 
2918 {
2919   /* TREE_LIST that will contain all of the parameter packs found by
2920      the traversal.  */
2921   tree* parameter_packs;
2922
2923   /* Set of AST nodes that have been visited by the traversal.  */
2924   struct pointer_set_t *visited;
2925 };
2926
2927 /* Identifies all of the argument packs that occur in a template
2928    argument and appends them to the TREE_LIST inside DATA, which is a
2929    find_parameter_pack_data structure. This is a subroutine of
2930    make_pack_expansion and uses_parameter_packs.  */
2931 static tree
2932 find_parameter_packs_r (tree *tp, int *walk_subtrees, void* data)
2933 {
2934   tree t = *tp;
2935   struct find_parameter_pack_data* ppd = 
2936     (struct find_parameter_pack_data*)data;
2937   bool parameter_pack_p = false;
2938
2939   /* Identify whether this is a parameter pack or not.  */
2940   switch (TREE_CODE (t))
2941     {
2942     case TEMPLATE_PARM_INDEX:
2943       if (TEMPLATE_PARM_PARAMETER_PACK (t))
2944         parameter_pack_p = true;
2945       break;
2946
2947     case TEMPLATE_TYPE_PARM:
2948     case TEMPLATE_TEMPLATE_PARM:
2949       if (TEMPLATE_TYPE_PARAMETER_PACK (t))
2950         parameter_pack_p = true;
2951       break;
2952
2953     case PARM_DECL:
2954       if (FUNCTION_PARAMETER_PACK_P (t))
2955         {
2956           /* We don't want to walk into the type of a PARM_DECL,
2957              because we don't want to see the type parameter pack.  */
2958           *walk_subtrees = 0;
2959           parameter_pack_p = true;
2960         }
2961       break;
2962
2963     default:
2964       /* Not a parameter pack.  */
2965       break;
2966     }
2967
2968   if (parameter_pack_p)
2969     {
2970       /* Add this parameter pack to the list.  */
2971       *ppd->parameter_packs = tree_cons (NULL_TREE, t, *ppd->parameter_packs);
2972     }
2973
2974   if (TYPE_P (t))
2975     cp_walk_tree (&TYPE_CONTEXT (t), 
2976                   &find_parameter_packs_r, ppd, ppd->visited);
2977
2978   /* This switch statement will return immediately if we don't find a
2979      parameter pack.  */
2980   switch (TREE_CODE (t)) 
2981     {
2982     case TEMPLATE_PARM_INDEX:
2983       return NULL_TREE;
2984
2985     case BOUND_TEMPLATE_TEMPLATE_PARM:
2986       /* Check the template itself.  */
2987       cp_walk_tree (&TREE_TYPE (TYPE_TI_TEMPLATE (t)), 
2988                     &find_parameter_packs_r, ppd, ppd->visited);
2989       /* Check the template arguments.  */
2990       cp_walk_tree (&TYPE_TI_ARGS (t), &find_parameter_packs_r, ppd, 
2991                     ppd->visited);
2992       *walk_subtrees = 0;
2993       return NULL_TREE;
2994
2995     case TEMPLATE_TYPE_PARM:
2996     case TEMPLATE_TEMPLATE_PARM:
2997       return NULL_TREE;
2998
2999     case PARM_DECL:
3000       return NULL_TREE;
3001
3002     case RECORD_TYPE:
3003       if (TYPE_PTRMEMFUNC_P (t))
3004         return NULL_TREE;
3005       /* Fall through.  */
3006
3007     case UNION_TYPE:
3008     case ENUMERAL_TYPE:
3009       if (TYPE_TEMPLATE_INFO (t))
3010         cp_walk_tree (&TI_ARGS (TYPE_TEMPLATE_INFO (t)),
3011                       &find_parameter_packs_r, ppd, ppd->visited);
3012
3013       *walk_subtrees = 0;
3014       return NULL_TREE;
3015
3016     case TEMPLATE_DECL:
3017       cp_walk_tree (&TREE_TYPE (t),
3018                     &find_parameter_packs_r, ppd, ppd->visited);
3019       return NULL_TREE;
3020  
3021     case TYPENAME_TYPE:
3022       cp_walk_tree (&TYPENAME_TYPE_FULLNAME (t), &find_parameter_packs_r,
3023                    ppd, ppd->visited);
3024       *walk_subtrees = 0;
3025       return NULL_TREE;
3026       
3027     case TYPE_PACK_EXPANSION:
3028     case EXPR_PACK_EXPANSION:
3029       *walk_subtrees = 0;
3030       return NULL_TREE;
3031
3032     case INTEGER_TYPE:
3033       cp_walk_tree (&TYPE_MAX_VALUE (t), &find_parameter_packs_r, 
3034                     ppd, ppd->visited);
3035       *walk_subtrees = 0;
3036       return NULL_TREE;
3037
3038     case IDENTIFIER_NODE:
3039       cp_walk_tree (&TREE_TYPE (t), &find_parameter_packs_r, ppd, 
3040                     ppd->visited);
3041       *walk_subtrees = 0;
3042       return NULL_TREE;
3043
3044     default:
3045       return NULL_TREE;
3046     }
3047
3048   return NULL_TREE;
3049 }
3050
3051 /* Determines if the expression or type T uses any parameter packs.  */
3052 bool
3053 uses_parameter_packs (tree t)
3054 {
3055   tree parameter_packs = NULL_TREE;
3056   struct find_parameter_pack_data ppd;
3057   ppd.parameter_packs = &parameter_packs;
3058   ppd.visited = pointer_set_create ();
3059   cp_walk_tree (&t, &find_parameter_packs_r, &ppd, ppd.visited);
3060   pointer_set_destroy (ppd.visited);
3061   return parameter_packs != NULL_TREE;
3062 }
3063
3064 /* Turn ARG, which may be an expression, type, or a TREE_LIST
3065    representation a base-class initializer into a parameter pack
3066    expansion. If all goes well, the resulting node will be an
3067    EXPR_PACK_EXPANSION, TYPE_PACK_EXPANSION, or TREE_LIST,
3068    respectively.  */
3069 tree 
3070 make_pack_expansion (tree arg)
3071 {
3072   tree result;
3073   tree parameter_packs = NULL_TREE;
3074   bool for_types = false;
3075   struct find_parameter_pack_data ppd;
3076
3077   if (!arg || arg == error_mark_node)
3078     return arg;
3079
3080   if (TREE_CODE (arg) == TREE_LIST)
3081     {
3082       /* The only time we will see a TREE_LIST here is for a base
3083          class initializer.  In this case, the TREE_PURPOSE will be a
3084          _TYPE node (representing the base class expansion we're
3085          initializing) and the TREE_VALUE will be a TREE_LIST
3086          containing the initialization arguments. 
3087
3088          The resulting expansion looks somewhat different from most
3089          expansions. Rather than returning just one _EXPANSION, we
3090          return a TREE_LIST whose TREE_PURPOSE is a
3091          TYPE_PACK_EXPANSION containing the bases that will be
3092          initialized.  The TREE_VALUE will be identical to the
3093          original TREE_VALUE, which is a list of arguments that will
3094          be passed to each base.  We do not introduce any new pack
3095          expansion nodes into the TREE_VALUE (although it is possible
3096          that some already exist), because the TREE_PURPOSE and
3097          TREE_VALUE all need to be expanded together with the same
3098          _EXPANSION node.  Note that the TYPE_PACK_EXPANSION in the
3099          resulting TREE_PURPOSE will mention the parameter packs in
3100          both the bases and the arguments to the bases.  */
3101       tree purpose;
3102       tree value;
3103       tree parameter_packs = NULL_TREE;
3104
3105       /* Determine which parameter packs will be used by the base
3106          class expansion.  */
3107       ppd.visited = pointer_set_create ();
3108       ppd.parameter_packs = &parameter_packs;
3109       cp_walk_tree (&TREE_PURPOSE (arg), &find_parameter_packs_r, 
3110                     &ppd, ppd.visited);
3111
3112       if (parameter_packs == NULL_TREE)
3113         {
3114           error ("base initializer expansion %<%T%> contains no parameter packs", arg);
3115           pointer_set_destroy (ppd.visited);
3116           return error_mark_node;
3117         }
3118
3119       if (TREE_VALUE (arg) != void_type_node)
3120         {
3121           /* Collect the sets of parameter packs used in each of the
3122              initialization arguments.  */
3123           for (value = TREE_VALUE (arg); value; value = TREE_CHAIN (value))
3124             {
3125               /* Determine which parameter packs will be expanded in this
3126                  argument.  */
3127               cp_walk_tree (&TREE_VALUE (value), &find_parameter_packs_r, 
3128                             &ppd, ppd.visited);
3129             }
3130         }
3131
3132       pointer_set_destroy (ppd.visited);
3133
3134       /* Create the pack expansion type for the base type.  */
3135       purpose = cxx_make_type (TYPE_PACK_EXPANSION);
3136       SET_PACK_EXPANSION_PATTERN (purpose, TREE_PURPOSE (arg));
3137       PACK_EXPANSION_PARAMETER_PACKS (purpose) = parameter_packs;
3138
3139       /* Just use structural equality for these TYPE_PACK_EXPANSIONS;
3140          they will rarely be compared to anything.  */
3141       SET_TYPE_STRUCTURAL_EQUALITY (purpose);
3142
3143       return tree_cons (purpose, TREE_VALUE (arg), NULL_TREE);
3144     }
3145
3146   if (TYPE_P (arg) || TREE_CODE (arg) == TEMPLATE_DECL)
3147     for_types = true;
3148
3149   /* Build the PACK_EXPANSION_* node.  */
3150   result = for_types
3151      ? cxx_make_type (TYPE_PACK_EXPANSION)
3152      : make_node (EXPR_PACK_EXPANSION);
3153   SET_PACK_EXPANSION_PATTERN (result, arg);
3154   if (TREE_CODE (result) == EXPR_PACK_EXPANSION)
3155     {
3156       /* Propagate type and const-expression information.  */
3157       TREE_TYPE (result) = TREE_TYPE (arg);
3158       TREE_CONSTANT (result) = TREE_CONSTANT (arg);
3159     }
3160   else
3161     /* Just use structural equality for these TYPE_PACK_EXPANSIONS;
3162        they will rarely be compared to anything.  */
3163     SET_TYPE_STRUCTURAL_EQUALITY (result);
3164
3165   /* Determine which parameter packs will be expanded.  */
3166   ppd.parameter_packs = &parameter_packs;
3167   ppd.visited = pointer_set_create ();
3168   cp_walk_tree (&arg, &find_parameter_packs_r, &ppd, ppd.visited);
3169   pointer_set_destroy (ppd.visited);
3170
3171   /* Make sure we found some parameter packs.  */
3172   if (parameter_packs == NULL_TREE)
3173     {
3174       if (TYPE_P (arg))
3175         error ("expansion pattern %<%T%> contains no argument packs", arg);
3176       else
3177         error ("expansion pattern %<%E%> contains no argument packs", arg);
3178       return error_mark_node;
3179     }
3180   PACK_EXPANSION_PARAMETER_PACKS (result) = parameter_packs;
3181
3182   return result;
3183 }
3184
3185 /* Checks T for any "bare" parameter packs, which have not yet been
3186    expanded, and issues an error if any are found. This operation can
3187    only be done on full expressions or types (e.g., an expression
3188    statement, "if" condition, etc.), because we could have expressions like:
3189
3190      foo(f(g(h(args)))...)
3191
3192    where "args" is a parameter pack. check_for_bare_parameter_packs
3193    should not be called for the subexpressions args, h(args),
3194    g(h(args)), or f(g(h(args))), because we would produce erroneous
3195    error messages. 
3196
3197    Returns TRUE and emits an error if there were bare parameter packs,
3198    returns FALSE otherwise.  */
3199 bool 
3200 check_for_bare_parameter_packs (tree t)
3201 {
3202   tree parameter_packs = NULL_TREE;
3203   struct find_parameter_pack_data ppd;
3204
3205   if (!processing_template_decl || !t || t == error_mark_node)
3206     return false;
3207
3208   if (TREE_CODE (t) == TYPE_DECL)
3209     t = TREE_TYPE (t);
3210
3211   ppd.parameter_packs = &parameter_packs;
3212   ppd.visited = pointer_set_create ();
3213   cp_walk_tree (&t, &find_parameter_packs_r, &ppd, ppd.visited);
3214   pointer_set_destroy (ppd.visited);
3215
3216   if (parameter_packs) 
3217     {
3218       error ("parameter packs not expanded with %<...%>:");
3219       while (parameter_packs)
3220         {
3221           tree pack = TREE_VALUE (parameter_packs);
3222           tree name = NULL_TREE;
3223
3224           if (TREE_CODE (pack) == TEMPLATE_TYPE_PARM
3225               || TREE_CODE (pack) == TEMPLATE_TEMPLATE_PARM)
3226             name = TYPE_NAME (pack);
3227           else if (TREE_CODE (pack) == TEMPLATE_PARM_INDEX)
3228             name = DECL_NAME (TEMPLATE_PARM_DECL (pack));
3229           else
3230             name = DECL_NAME (pack);
3231
3232           if (name)
3233             inform (input_location, "        %qD", name);
3234           else
3235             inform (input_location, "        <anonymous>");
3236
3237           parameter_packs = TREE_CHAIN (parameter_packs);
3238         }
3239
3240       return true;
3241     }
3242
3243   return false;
3244 }
3245
3246 /* Expand any parameter packs that occur in the template arguments in
3247    ARGS.  */
3248 tree
3249 expand_template_argument_pack (tree args)
3250 {
3251   tree result_args = NULL_TREE;
3252   int in_arg, out_arg = 0, nargs = args ? TREE_VEC_LENGTH (args) : 0;
3253   int num_result_args = -1;
3254   int non_default_args_count = -1;
3255
3256   /* First, determine if we need to expand anything, and the number of
3257      slots we'll need.  */
3258   for (in_arg = 0; in_arg < nargs; ++in_arg)
3259     {
3260       tree arg = TREE_VEC_ELT (args, in_arg);
3261       if (arg == NULL_TREE)
3262         return args;
3263       if (ARGUMENT_PACK_P (arg))
3264         {
3265           int num_packed = TREE_VEC_LENGTH (ARGUMENT_PACK_ARGS (arg));
3266           if (num_result_args < 0)
3267             num_result_args = in_arg + num_packed;
3268           else
3269             num_result_args += num_packed;
3270         }
3271       else
3272         {
3273           if (num_result_args >= 0)
3274             num_result_args++;
3275         }
3276     }
3277
3278   /* If no expansion is necessary, we're done.  */
3279   if (num_result_args < 0)
3280     return args;
3281
3282   /* Expand arguments.  */
3283   result_args = make_tree_vec (num_result_args);
3284   if (NON_DEFAULT_TEMPLATE_ARGS_COUNT (args))
3285     non_default_args_count =
3286       GET_NON_DEFAULT_TEMPLATE_ARGS_COUNT (args);
3287   for (in_arg = 0; in_arg < nargs; ++in_arg)
3288     {
3289       tree arg = TREE_VEC_ELT (args, in_arg);
3290       if (ARGUMENT_PACK_P (arg))
3291         {
3292           tree packed = ARGUMENT_PACK_ARGS (arg);
3293           int i, num_packed = TREE_VEC_LENGTH (packed);
3294           for (i = 0; i < num_packed; ++i, ++out_arg)
3295             TREE_VEC_ELT (result_args, out_arg) = TREE_VEC_ELT(packed, i);
3296           if (non_default_args_count > 0)
3297             non_default_args_count += num_packed;
3298         }
3299       else
3300         {
3301           TREE_VEC_ELT (result_args, out_arg) = arg;
3302           ++out_arg;
3303         }
3304     }
3305   if (non_default_args_count >= 0)
3306     SET_NON_DEFAULT_TEMPLATE_ARGS_COUNT (result_args, non_default_args_count);
3307   return result_args;
3308 }
3309
3310 /* Checks if DECL shadows a template parameter.
3311
3312    [temp.local]: A template-parameter shall not be redeclared within its
3313    scope (including nested scopes).
3314
3315    Emits an error and returns TRUE if the DECL shadows a parameter,
3316    returns FALSE otherwise.  */
3317
3318 bool
3319 check_template_shadow (tree decl)
3320 {
3321   tree olddecl;
3322
3323   /* If we're not in a template, we can't possibly shadow a template
3324      parameter.  */
3325   if (!current_template_parms)
3326     return true;
3327
3328   /* Figure out what we're shadowing.  */
3329   if (TREE_CODE (decl) == OVERLOAD)
3330     decl = OVL_CURRENT (decl);
3331   olddecl = innermost_non_namespace_value (DECL_NAME (decl));
3332
3333   /* If there's no previous binding for this name, we're not shadowing
3334      anything, let alone a template parameter.  */
3335   if (!olddecl)
3336     return true;
3337
3338   /* If we're not shadowing a template parameter, we're done.  Note
3339      that OLDDECL might be an OVERLOAD (or perhaps even an
3340      ERROR_MARK), so we can't just blithely assume it to be a _DECL
3341      node.  */
3342   if (!DECL_P (olddecl) || !DECL_TEMPLATE_PARM_P (olddecl))
3343     return true;
3344
3345   /* We check for decl != olddecl to avoid bogus errors for using a
3346      name inside a class.  We check TPFI to avoid duplicate errors for
3347      inline member templates.  */
3348   if (decl == olddecl
3349       || TEMPLATE_PARMS_FOR_INLINE (current_template_parms))
3350     return true;
3351
3352   error ("declaration of %q+#D", decl);
3353   error (" shadows template parm %q+#D", olddecl);
3354   return false;
3355 }
3356
3357 /* Return a new TEMPLATE_PARM_INDEX with the indicated INDEX, LEVEL,
3358    ORIG_LEVEL, DECL, and TYPE.  NUM_SIBLINGS is the total number of
3359    template parameters.  */
3360
3361 static tree
3362 build_template_parm_index (int index,
3363                            int level,
3364                            int orig_level,
3365                            int num_siblings,
3366                            tree decl,
3367                            tree type)
3368 {
3369   tree t = make_node (TEMPLATE_PARM_INDEX);
3370   TEMPLATE_PARM_IDX (t) = index;
3371   TEMPLATE_PARM_LEVEL (t) = level;
3372   TEMPLATE_PARM_ORIG_LEVEL (t) = orig_level;
3373   TEMPLATE_PARM_NUM_SIBLINGS (t) = num_siblings;
3374   TEMPLATE_PARM_DECL (t) = decl;
3375   TREE_TYPE (t) = type;
3376   TREE_CONSTANT (t) = TREE_CONSTANT (decl);
3377   TREE_READONLY (t) = TREE_READONLY (decl);
3378
3379   return t;
3380 }
3381
3382 /* Find the canonical type parameter for the given template type
3383    parameter.  Returns the canonical type parameter, which may be TYPE
3384    if no such parameter existed.  */
3385
3386 static tree
3387 canonical_type_parameter (tree type)
3388 {
3389   tree list;
3390   int idx = TEMPLATE_TYPE_IDX (type);
3391   if (!canonical_template_parms)
3392     canonical_template_parms = VEC_alloc (tree, gc, idx+1);
3393
3394   while (VEC_length (tree, canonical_template_parms) <= (unsigned)idx)
3395     VEC_safe_push (tree, gc, canonical_template_parms, NULL_TREE);
3396
3397   list = VEC_index (tree, canonical_template_parms, idx);
3398   while (list && !comptypes (type, TREE_VALUE (list), COMPARE_STRUCTURAL))
3399     list = TREE_CHAIN (list);
3400
3401   if (list)
3402     return TREE_VALUE (list);
3403   else
3404     {
3405       VEC_replace(tree, canonical_template_parms, idx,
3406                   tree_cons (NULL_TREE, type, 
3407                              VEC_index (tree, canonical_template_parms, idx)));
3408       return type;
3409     }
3410 }
3411
3412 /* Return a TEMPLATE_PARM_INDEX, similar to INDEX, but whose
3413    TEMPLATE_PARM_LEVEL has been decreased by LEVELS.  If such a
3414    TEMPLATE_PARM_INDEX already exists, it is returned; otherwise, a
3415    new one is created.  */
3416
3417 static tree
3418 reduce_template_parm_level (tree index, tree type, int levels, tree args,
3419                             tsubst_flags_t complain)
3420 {
3421   if (TEMPLATE_PARM_DESCENDANTS (index) == NULL_TREE
3422       || (TEMPLATE_PARM_LEVEL (TEMPLATE_PARM_DESCENDANTS (index))
3423           != TEMPLATE_PARM_LEVEL (index) - levels)
3424       || !same_type_p (type, TREE_TYPE (TEMPLATE_PARM_DESCENDANTS (index))))
3425     {
3426       tree orig_decl = TEMPLATE_PARM_DECL (index);
3427       tree decl, t;
3428
3429       decl = build_decl (DECL_SOURCE_LOCATION (orig_decl),
3430                          TREE_CODE (orig_decl), DECL_NAME (orig_decl), type);
3431       TREE_CONSTANT (decl) = TREE_CONSTANT (orig_decl);
3432       TREE_READONLY (decl) = TREE_READONLY (orig_decl);
3433       DECL_ARTIFICIAL (decl) = 1;
3434       SET_DECL_TEMPLATE_PARM_P (decl);
3435
3436       t = build_template_parm_index (TEMPLATE_PARM_IDX (index),
3437                                      TEMPLATE_PARM_LEVEL (index) - levels,
3438                                      TEMPLATE_PARM_ORIG_LEVEL (index),
3439                                      TEMPLATE_PARM_NUM_SIBLINGS (index),
3440                                      decl, type);
3441       TEMPLATE_PARM_DESCENDANTS (index) = t;
3442       TEMPLATE_PARM_PARAMETER_PACK (t) 
3443         = TEMPLATE_PARM_PARAMETER_PACK (index);
3444
3445         /* Template template parameters need this.  */
3446       if (TREE_CODE (decl) == TEMPLATE_DECL)
3447         DECL_TEMPLATE_PARMS (decl) = tsubst_template_parms
3448           (DECL_TEMPLATE_PARMS (TEMPLATE_PARM_DECL (index)),
3449            args, complain);
3450     }
3451
3452   return TEMPLATE_PARM_DESCENDANTS (index);
3453 }
3454
3455 /* Process information from new template parameter PARM and append it
3456    to the LIST being built.  This new parameter is a non-type
3457    parameter iff IS_NON_TYPE is true. This new parameter is a
3458    parameter pack iff IS_PARAMETER_PACK is true.  The location of PARM
3459    is in PARM_LOC. NUM_TEMPLATE_PARMS is the size of the template
3460    parameter list PARM belongs to. This is used used to create a
3461    proper canonical type for the type of PARM that is to be created,
3462    iff PARM is a type.  If the size is not known, this parameter shall
3463    be set to 0.  */
3464
3465 tree
3466 process_template_parm (tree list, location_t parm_loc, tree parm,
3467                        bool is_non_type, bool is_parameter_pack,
3468                        unsigned num_template_parms)
3469 {
3470   tree decl = 0;
3471   tree defval;
3472   tree err_parm_list;
3473   int idx = 0;
3474
3475   gcc_assert (TREE_CODE (parm) == TREE_LIST);
3476   defval = TREE_PURPOSE (parm);
3477
3478   if (list)
3479     {
3480       tree p = tree_last (list);
3481
3482       if (p && TREE_VALUE (p) != error_mark_node)
3483         {
3484           p = TREE_VALUE (p);
3485           if (TREE_CODE (p) == TYPE_DECL || TREE_CODE (p) == TEMPLATE_DECL)
3486             idx = TEMPLATE_TYPE_IDX (TREE_TYPE (p));
3487           else
3488             idx = TEMPLATE_PARM_IDX (DECL_INITIAL (p));
3489         }
3490
3491       ++idx;
3492     }
3493   else
3494     idx = 0;
3495
3496   if (is_non_type)
3497     {
3498       parm = TREE_VALUE (parm);
3499
3500       SET_DECL_TEMPLATE_PARM_P (parm);
3501
3502       if (TREE_TYPE (parm) == error_mark_node)
3503         {
3504           err_parm_list = build_tree_list (defval, parm);
3505           TREE_VALUE (err_parm_list) = error_mark_node;
3506            return chainon (list, err_parm_list);
3507         }
3508       else
3509       {
3510         /* [temp.param]
3511
3512            The top-level cv-qualifiers on the template-parameter are
3513            ignored when determining its type.  */
3514         TREE_TYPE (parm) = TYPE_MAIN_VARIANT (TREE_TYPE (parm));
3515         if (invalid_nontype_parm_type_p (TREE_TYPE (parm), 1))
3516           {
3517             err_parm_list = build_tree_list (defval, parm);
3518             TREE_VALUE (err_parm_list) = error_mark_node;
3519              return chainon (list, err_parm_list);
3520           }
3521
3522         if (uses_parameter_packs (TREE_TYPE (parm)) && !is_parameter_pack)
3523           {
3524             /* This template parameter is not a parameter pack, but it
3525                should be. Complain about "bare" parameter packs.  */
3526             check_for_bare_parameter_packs (TREE_TYPE (parm));
3527             
3528             /* Recover by calling this a parameter pack.  */
3529             is_parameter_pack = true;
3530           }
3531       }
3532
3533       /* A template parameter is not modifiable.  */
3534       TREE_CONSTANT (parm) = 1;
3535       TREE_READONLY (parm) = 1;
3536       decl = build_decl (parm_loc,
3537                          CONST_DECL, DECL_NAME (parm), TREE_TYPE (parm));
3538       TREE_CONSTANT (decl) = 1;
3539       TREE_READONLY (decl) = 1;
3540       DECL_INITIAL (parm) = DECL_INITIAL (decl)
3541         = build_template_parm_index (idx, processing_template_decl,
3542                                      processing_template_decl,
3543                                      num_template_parms,
3544                                      decl, TREE_TYPE (parm));
3545
3546       TEMPLATE_PARM_PARAMETER_PACK (DECL_INITIAL (parm)) 
3547         = is_parameter_pack;
3548     }
3549   else
3550     {
3551       tree t;
3552       parm = TREE_VALUE (TREE_VALUE (parm));
3553
3554       if (parm && TREE_CODE (parm) == TEMPLATE_DECL)
3555         {
3556           t = cxx_make_type (TEMPLATE_TEMPLATE_PARM);
3557           /* This is for distinguishing between real templates and template
3558              template parameters */
3559           TREE_TYPE (parm) = t;
3560           TREE_TYPE (DECL_TEMPLATE_RESULT (parm)) = t;
3561           decl = parm;
3562         }
3563       else
3564         {
3565           t = cxx_make_type (TEMPLATE_TYPE_PARM);
3566           /* parm is either IDENTIFIER_NODE or NULL_TREE.  */
3567           decl = build_decl (parm_loc,
3568                              TYPE_DECL, parm, t);
3569         }
3570
3571       TYPE_NAME (t) = decl;
3572       TYPE_STUB_DECL (t) = decl;
3573       parm = decl;
3574       TEMPLATE_TYPE_PARM_INDEX (t)
3575         = build_template_parm_index (idx, processing_template_decl,
3576                                      processing_template_decl,
3577                                      num_template_parms,
3578                                      decl, TREE_TYPE (parm));
3579       TEMPLATE_TYPE_PARAMETER_PACK (t) = is_parameter_pack;
3580       TYPE_CANONICAL (t) = canonical_type_parameter (t);
3581     }
3582   DECL_ARTIFICIAL (decl) = 1;
3583   SET_DECL_TEMPLATE_PARM_P (decl);
3584   pushdecl (decl);
3585   parm = build_tree_list (defval, parm);
3586   return chainon (list, parm);
3587 }
3588
3589 /* The end of a template parameter list has been reached.  Process the
3590    tree list into a parameter vector, converting each parameter into a more
3591    useful form.  Type parameters are saved as IDENTIFIER_NODEs, and others
3592    as PARM_DECLs.  */
3593
3594 tree
3595 end_template_parm_list (tree parms)
3596 {
3597   int nparms;
3598   tree parm, next;
3599   tree saved_parmlist = make_tree_vec (list_length (parms));
3600
3601   current_template_parms
3602     = tree_cons (size_int (processing_template_decl),
3603                  saved_parmlist, current_template_parms);
3604
3605   for (parm = parms, nparms = 0; parm; parm = next, nparms++)
3606     {
3607       next = TREE_CHAIN (parm);
3608       TREE_VEC_ELT (saved_parmlist, nparms) = parm;
3609       TREE_CHAIN (parm) = NULL_TREE;
3610     }
3611
3612   --processing_template_parmlist;
3613
3614   return saved_parmlist;
3615 }
3616
3617 /* Create a new type almost identical to TYPE but which has the
3618    following differences:
3619
3620      1/ T has a new TEMPLATE_PARM_INDEX that carries the new number of
3621      template sibling parameters of T.
3622
3623      2/ T has a new canonical type that matches the new number
3624      of sibling parms.
3625
3626      3/ From now on, T is going to be what lookups referring to the
3627      name of TYPE will return. No lookup should return TYPE anymore.
3628
3629    NUM_PARMS is the new number of sibling parms TYPE belongs to.
3630
3631    This is a subroutine of fixup_template_parms.  */
3632
3633 static tree
3634 fixup_template_type_parm_type (tree type, int num_parms)
3635 {
3636   tree orig_idx = TEMPLATE_TYPE_PARM_INDEX (type), idx;
3637   tree t;
3638   /* This is the decl which name is inserted into the symbol table for
3639      the template parm type. So whenever we lookup the type name, this
3640      is the DECL we get.  */
3641   tree decl;
3642
3643   /* Do not fix up the type twice.  */
3644   if (orig_idx && TEMPLATE_PARM_NUM_SIBLINGS (orig_idx) != 0)
3645     return type;
3646
3647   t = copy_type (type);
3648   decl = TYPE_NAME (t);
3649
3650   TYPE_MAIN_VARIANT (t) = t;
3651   TYPE_NEXT_VARIANT (t)= NULL_TREE;
3652   TYPE_POINTER_TO (t) = 0;
3653   TYPE_REFERENCE_TO (t) = 0;
3654
3655   idx = build_template_parm_index (TEMPLATE_PARM_IDX (orig_idx),
3656                                    TEMPLATE_PARM_LEVEL (orig_idx),
3657                                    TEMPLATE_PARM_ORIG_LEVEL (orig_idx),
3658                                    num_parms,
3659                                    decl, t);
3660   TEMPLATE_PARM_DESCENDANTS (idx) = TEMPLATE_PARM_DESCENDANTS (orig_idx);
3661   TEMPLATE_PARM_PARAMETER_PACK (idx) = TEMPLATE_PARM_PARAMETER_PACK (orig_idx);
3662   TEMPLATE_TYPE_PARM_INDEX (t) = idx;
3663
3664   TYPE_STUB_DECL (t) = decl;
3665   TEMPLATE_TYPE_DECL (t) = decl;
3666   if (TREE_CODE (type) == TEMPLATE_TEMPLATE_PARM)
3667     TREE_TYPE (DECL_TEMPLATE_RESULT  (decl)) = t;
3668
3669   /* Update the type associated to the type name stored in the symbol
3670      table. Now, whenever the type name is looked up, the resulting
3671      type is properly fixed up.  */
3672   TREE_TYPE (decl) = t;
3673
3674   TYPE_CANONICAL (t) = canonical_type_parameter (t);
3675
3676   return t;
3677 }
3678
3679 /* Create and return a new TEMPLATE_PARM_INDEX that is almost
3680    identical to I, but that is fixed up as to:
3681
3682    1/ carry the number of sibling parms (NUM_PARMS) of the template
3683    parm represented by I.
3684
3685    2/ replace all references to template parm types declared before I
3686    (in the same template parm list as I) by references to template
3687    parm types contained in ARGS. ARGS should contain the list of
3688    template parms that have been fixed up so far, in a form suitable
3689    to be passed to tsubst.
3690
3691    This is a subroutine of fixup_template_parms.  */
3692
3693 static tree
3694 fixup_template_parm_index (tree i, tree args, int num_parms)
3695 {
3696   tree index, decl, type;
3697
3698   if (i == NULL_TREE
3699       || TREE_CODE (i) != TEMPLATE_PARM_INDEX
3700       /* Do not fix up the index twice.  */
3701       || (TEMPLATE_PARM_NUM_SIBLINGS (i) != 0))
3702     return i;
3703
3704   decl = TEMPLATE_PARM_DECL (i);
3705   type = TREE_TYPE (decl);
3706
3707   index = build_template_parm_index (TEMPLATE_PARM_IDX (i),
3708                                      TEMPLATE_PARM_LEVEL (i),
3709                                      TEMPLATE_PARM_ORIG_LEVEL (i),
3710                                      num_parms,
3711                                      decl, type);
3712
3713   TEMPLATE_PARM_DESCENDANTS (index) = TEMPLATE_PARM_DESCENDANTS (i);
3714   TEMPLATE_PARM_PARAMETER_PACK (index) = TEMPLATE_PARM_PARAMETER_PACK (i);
3715
3716   type = tsubst (type, args, tf_none, NULL_TREE);
3717   
3718   TREE_TYPE (decl) = type;
3719   TREE_TYPE (index) = type;
3720
3721   return index;
3722 }
3723
3724 /* 
3725    This is a subroutine of fixup_template_parms.
3726
3727    It computes the canonical type of the type of the template
3728    parameter PARM_DESC and update all references to that type so that
3729    they use the newly computed canonical type. No access check is
3730    performed during the fixup. PARM_DESC is a TREE_LIST which
3731    TREE_VALUE is the template parameter and its TREE_PURPOSE is the
3732    default argument of the template parm if any. IDX is the index of
3733    the template parameter, starting at 0. NUM_PARMS is the number of
3734    template parameters in the set PARM_DESC belongs to. ARGLIST is a
3735    TREE_VEC containing the full set of template parameters in a form
3736    suitable to be passed to substs functions as their ARGS
3737    argument. This is what current_template_args returns for a given
3738    template. The innermost vector of args in ARGLIST is the set of
3739    template parms that have been fixed up so far. This function adds
3740    the fixed up parameter into that vector.  */
3741
3742 static void
3743 fixup_template_parm (tree parm_desc,
3744                      int idx,
3745                      int num_parms,
3746                      tree arglist)
3747 {
3748   tree parm = TREE_VALUE (parm_desc);
3749   tree fixedup_args = INNERMOST_TEMPLATE_ARGS (arglist);
3750
3751   push_deferring_access_checks (dk_no_check);
3752
3753   if (TREE_CODE (parm) == TYPE_DECL)
3754     {
3755       /* PARM is a template type parameter. Fix up its type, add
3756          the fixed-up template parm to the vector of fixed-up
3757          template parms so far, and substitute the fixed-up
3758          template parms into the default argument of this
3759          parameter.  */
3760       tree t =
3761         fixup_template_type_parm_type (TREE_TYPE (parm), num_parms);
3762       TREE_TYPE (parm) = t;
3763
3764       TREE_VEC_ELT (fixedup_args, idx) = template_parm_to_arg (parm_desc);
3765     }
3766   else if (TREE_CODE (parm) == TEMPLATE_DECL)
3767     {
3768       /* PARM is a template template parameter. This is going to
3769          be interesting.  */
3770       tree tparms, targs, innermost_args, t;
3771       int j;
3772
3773       /* First, fix up the parms of the template template parm
3774          because the parms are involved in defining the new canonical
3775          type of the template template parm.  */
3776
3777       /* So we need to substitute the template parm types that have
3778          been fixed up so far into the template parms of this template
3779          template parm. E.g, consider this:
3780
3781          template<class T, template<T u> class TT> class S;
3782
3783          In this case we want to substitute T into the
3784          template parameters of TT.
3785
3786          So let's walk the template parms of PARM here, and
3787          tsubst ARGLIST into into each of the template
3788          parms.   */
3789
3790       /* For this substitution we need to build the full set of
3791          template parameters and use that as arguments for the
3792          tsubsting function.  */
3793       tparms = INNERMOST_TEMPLATE_PARMS (DECL_TEMPLATE_PARMS (parm));
3794
3795       /* This will contain the innermost parms of PARM into which
3796          we have substituted so far.  */
3797       innermost_args = make_tree_vec (TREE_VEC_LENGTH (tparms));
3798       targs = add_to_template_args (arglist, innermost_args);
3799       for (j = 0; j < TREE_VEC_LENGTH (tparms); ++j)
3800         {
3801           tree parameter;
3802
3803           parameter = TREE_VEC_ELT (tparms, j);
3804
3805           /* INNERMOST_ARGS needs to have at least the same number
3806              of elements as the index PARAMETER, ortherwise
3807              tsubsting into PARAMETER will result in partially
3808              instantiating it, reducing its tempate parm
3809              level. Let's tactically fill INNERMOST_ARGS for that
3810              purpose.  */
3811           TREE_VEC_ELT (innermost_args, j) =
3812             template_parm_to_arg (parameter);
3813
3814           fixup_template_parm (parameter, j,
3815                                TREE_VEC_LENGTH (tparms),
3816                                targs);
3817         }
3818
3819       /* Now fix up the type of the template template parm.  */
3820
3821       t = fixup_template_type_parm_type (TREE_TYPE (parm), num_parms);
3822       TREE_TYPE (parm) = t;
3823
3824       TREE_VEC_ELT (fixedup_args, idx) =
3825         template_parm_to_arg (parm_desc);
3826     }
3827   else if (TREE_CODE (parm) == PARM_DECL)
3828     {
3829       /* PARM is a non-type template parameter. We need to:
3830
3831        * Fix up its TEMPLATE_PARM_INDEX to make it carry the
3832        proper number of sibling parameters.
3833
3834        * Make lookups of the template parameter return a reference
3835        to the fixed-up index. No lookup should return references
3836        to the former index anymore.
3837
3838        * Substitute the template parms that got fixed up so far
3839
3840        * into the type of PARM.  */
3841
3842       tree index = DECL_INITIAL (parm);
3843
3844       /* PUSHED_DECL is the decl added to the symbol table with
3845          the name of the parameter. E,g:
3846              
3847          template<class T, T u> //#0
3848          auto my_function(T t) -> decltype(u); //#1
3849
3850          Here, when looking up u at //#1, we get the decl of u
3851          resulting from the declaration in #0. This is what
3852          PUSHED_DECL is. We need to replace the reference to the
3853          old TEMPLATE_PARM_INDEX carried by PUSHED_DECL by the
3854          fixed-up TEMPLATE_PARM_INDEX.  */
3855       tree pushed_decl = TEMPLATE_PARM_DECL (index);
3856
3857       /* Let's fix up the TEMPLATE_PARM_INDEX then. Note that we must
3858          fixup the type of PUSHED_DECL as well and luckily
3859          fixup_template_parm_index does it for us too.  */
3860       tree fixed_up_index =
3861         fixup_template_parm_index (index, arglist, num_parms);
3862
3863       DECL_INITIAL (pushed_decl) = DECL_INITIAL (parm) = fixed_up_index;
3864
3865       /* Add this fixed up PARM to the template parms we've fixed
3866          up so far and use that to substitute the fixed-up
3867          template parms into the type of PARM.  */
3868       TREE_VEC_ELT (fixedup_args, idx) =
3869         template_parm_to_arg (parm_desc);
3870       TREE_TYPE (parm) = tsubst (TREE_TYPE (parm), arglist,
3871                                  tf_none, NULL_TREE);
3872     }
3873
3874   TREE_PURPOSE (parm_desc) =
3875     tsubst_template_arg (TREE_PURPOSE (parm_desc),
3876                          arglist, tf_none, parm);
3877
3878   pop_deferring_access_checks ();
3879 }
3880
3881 /* Walk the current template parms and properly compute the canonical
3882    types of the dependent types created during
3883    cp_parser_template_parameter_list.  */
3884
3885 void
3886 fixup_template_parms (void)
3887 {
3888   tree arglist;
3889   tree parameter_vec;
3890   tree fixedup_args;
3891   int i, num_parms;
3892
3893   parameter_vec = INNERMOST_TEMPLATE_PARMS (current_template_parms);
3894   if (parameter_vec == NULL_TREE)
3895     return;
3896
3897   num_parms = TREE_VEC_LENGTH (parameter_vec);
3898
3899   /* This vector contains the current innermost template parms that
3900      have been fixed up so far.  The form of FIXEDUP_ARGS is suitable
3901      to be passed to tsubst* functions as their ARGS argument.  */
3902   fixedup_args = make_tree_vec (num_parms);
3903
3904   /* This vector contains the full set of template parms in a form
3905      suitable to be passed to substs functions as their ARGS
3906      argument.  */
3907   arglist = current_template_args ();
3908   arglist = add_outermost_template_args (arglist, fixedup_args);
3909
3910   /* Let's do the proper fixup now.  */
3911   for (i = 0; i < num_parms; ++i)
3912     fixup_template_parm (TREE_VEC_ELT (parameter_vec, i),
3913                          i, num_parms, arglist);
3914 }
3915
3916 /* end_template_decl is called after a template declaration is seen.  */
3917
3918 void
3919 end_template_decl (void)
3920 {
3921   reset_specialization ();
3922
3923   if (! processing_template_decl)
3924     return;
3925
3926   /* This matches the pushlevel in begin_template_parm_list.  */
3927   finish_scope ();
3928
3929   --processing_template_decl;
3930   current_template_parms = TREE_CHAIN (current_template_parms);
3931 }
3932
3933 /* Takes a TREE_LIST representing a template parameter and convert it
3934    into an argument suitable to be passed to the type substitution
3935    functions.  Note that If the TREE_LIST contains an error_mark
3936    node, the returned argument is error_mark_node.  */
3937
3938 static tree
3939 template_parm_to_arg (tree t)
3940 {
3941
3942   if (t == NULL_TREE
3943       || TREE_CODE (t) != TREE_LIST)
3944     return t;
3945
3946   if (error_operand_p (TREE_VALUE (t)))
3947     return error_mark_node;
3948
3949   t = TREE_VALUE (t);
3950
3951   if (TREE_CODE (t) == TYPE_DECL
3952       || TREE_CODE (t) == TEMPLATE_DECL)
3953     {
3954       t = TREE_TYPE (t);
3955
3956       if (TEMPLATE_TYPE_PARAMETER_PACK (t))
3957         {
3958           /* Turn this argument into a TYPE_ARGUMENT_PACK
3959              with a single element, which expands T.  */
3960           tree vec = make_tree_vec (1);
3961 #ifdef ENABLE_CHECKING
3962           SET_NON_DEFAULT_TEMPLATE_ARGS_COUNT
3963             (vec, TREE_VEC_LENGTH (vec));
3964 #endif
3965           TREE_VEC_ELT (vec, 0) = make_pack_expansion (t);
3966
3967           t = cxx_make_type (TYPE_ARGUMENT_PACK);
3968           SET_ARGUMENT_PACK_ARGS (t, vec);
3969         }
3970     }
3971   else
3972     {
3973       t = DECL_INITIAL (t);
3974
3975       if (TEMPLATE_PARM_PARAMETER_PACK (t))
3976         {
3977           /* Turn this argument into a NONTYPE_ARGUMENT_PACK
3978              with a single element, which expands T.  */
3979           tree vec = make_tree_vec (1);
3980           tree type = TREE_TYPE (TEMPLATE_PARM_DECL (t));
3981 #ifdef ENABLE_CHECKING
3982           SET_NON_DEFAULT_TEMPLATE_ARGS_COUNT
3983             (vec, TREE_VEC_LENGTH (vec));
3984 #endif
3985           TREE_VEC_ELT (vec, 0) = make_pack_expansion (t);
3986
3987           t  = make_node (NONTYPE_ARGUMENT_PACK);
3988           SET_ARGUMENT_PACK_ARGS (t, vec);
3989           TREE_TYPE (t) = type;
3990         }
3991     }
3992   return t;
3993 }
3994
3995 /* Within the declaration of a template, return all levels of template
3996    parameters that apply.  The template parameters are represented as
3997    a TREE_VEC, in the form documented in cp-tree.h for template
3998    arguments.  */
3999
4000 static tree
4001 current_template_args (void)
4002 {
4003   tree header;
4004   tree args = NULL_TREE;
4005   int length = TMPL_PARMS_DEPTH (current_template_parms);
4006   int l = length;
4007
4008   /* If there is only one level of template parameters, we do not
4009      create a TREE_VEC of TREE_VECs.  Instead, we return a single
4010      TREE_VEC containing the arguments.  */
4011   if (length > 1)
4012     args = make_tree_vec (length);
4013
4014   for (header = current_template_parms; header; header = TREE_CHAIN (header))
4015     {
4016       tree a = copy_node (TREE_VALUE (header));
4017       int i;
4018
4019       TREE_TYPE (a) = NULL_TREE;
4020       for (i = TREE_VEC_LENGTH (a) - 1; i >= 0; --i)
4021         TREE_VEC_ELT (a, i) = template_parm_to_arg (TREE_VEC_ELT (a, i));
4022
4023 #ifdef ENABLE_CHECKING
4024       SET_NON_DEFAULT_TEMPLATE_ARGS_COUNT (a, TREE_VEC_LENGTH (a));
4025 #endif
4026
4027       if (length > 1)
4028         TREE_VEC_ELT (args, --l) = a;
4029       else
4030         args = a;
4031     }
4032
4033     if (length > 1 && TREE_VEC_ELT (args, 0) == NULL_TREE)
4034       /* This can happen for template parms of a template template
4035          parameter, e.g:
4036
4037          template<template<class T, class U> class TT> struct S;
4038
4039          Consider the level of the parms of TT; T and U both have
4040          level 2; TT has no template parm of level 1. So in this case
4041          the first element of full_template_args is NULL_TREE. If we
4042          leave it like this TMPL_ARG_DEPTH on args returns 1 instead
4043          of 2. This will make tsubst wrongly consider that T and U
4044          have level 1. Instead, let's create a dummy vector as the
4045          first element of full_template_args so that TMPL_ARG_DEPTH
4046          returns the correct depth for args.  */
4047       TREE_VEC_ELT (args, 0) = make_tree_vec (1);
4048   return args;
4049 }
4050
4051 /* Update the declared TYPE by doing any lookups which were thought to be
4052    dependent, but are not now that we know the SCOPE of the declarator.  */
4053
4054 tree
4055 maybe_update_decl_type (tree orig_type, tree scope)
4056 {
4057   tree type = orig_type;
4058
4059   if (type == NULL_TREE)
4060     return type;
4061
4062   if (TREE_CODE (orig_type) == TYPE_DECL)
4063     type = TREE_TYPE (type);
4064
4065   if (scope && TYPE_P (scope) && dependent_type_p (scope)
4066       && dependent_type_p (type)
4067       /* Don't bother building up the args in this case.  */
4068       && TREE_CODE (type) != TEMPLATE_TYPE_PARM)
4069     {
4070       /* tsubst in the args corresponding to the template parameters,
4071          including auto if present.  Most things will be unchanged, but
4072          make_typename_type and tsubst_qualified_id will resolve
4073          TYPENAME_TYPEs and SCOPE_REFs that were previously dependent.  */
4074       tree args = current_template_args ();
4075       tree auto_node = type_uses_auto (type);
4076       tree pushed;
4077       if (auto_node)
4078         {
4079           tree auto_vec = make_tree_vec (1);
4080           TREE_VEC_ELT (auto_vec, 0) = auto_node;
4081           args = add_to_template_args (args, auto_vec);
4082         }
4083       pushed = push_scope (scope);
4084       type = tsubst (type, args, tf_warning_or_error, NULL_TREE);
4085       if (pushed)
4086         pop_scope (scope);
4087     }
4088
4089   if (type == error_mark_node)
4090     return orig_type;
4091
4092   if (TREE_CODE (orig_type) == TYPE_DECL)
4093     {
4094       if (same_type_p (type, TREE_TYPE (orig_type)))
4095         type = orig_type;
4096       else
4097         type = TYPE_NAME (type);
4098     }
4099   return type;
4100 }
4101
4102 /* Return a TEMPLATE_DECL corresponding to DECL, using the indicated
4103    template PARMS.  If MEMBER_TEMPLATE_P is true, the new template is
4104    a member template.  Used by push_template_decl below.  */
4105
4106 static tree
4107 build_template_decl (tree decl, tree parms, bool member_template_p)
4108 {
4109   tree tmpl = build_lang_decl (TEMPLATE_DECL, DECL_NAME (decl), NULL_TREE);
4110   DECL_TEMPLATE_PARMS (tmpl) = parms;
4111   DECL_CONTEXT (tmpl) = DECL_CONTEXT (decl);
4112   DECL_MEMBER_TEMPLATE_P (tmpl) = member_template_p;
4113
4114   return tmpl;
4115 }
4116
4117 struct template_parm_data
4118 {
4119   /* The level of the template parameters we are currently
4120      processing.  */
4121   int level;
4122
4123   /* The index of the specialization argument we are currently
4124      processing.  */
4125   int current_arg;
4126
4127   /* An array whose size is the number of template parameters.  The
4128      elements are nonzero if the parameter has been used in any one
4129      of the arguments processed so far.  */
4130   int* parms;
4131
4132   /* An array whose size is the number of template arguments.  The
4133      elements are nonzero if the argument makes use of template
4134      parameters of this level.  */
4135   int* arg_uses_template_parms;
4136 };
4137
4138 /* Subroutine of push_template_decl used to see if each template
4139    parameter in a partial specialization is used in the explicit
4140    argument list.  If T is of the LEVEL given in DATA (which is
4141    treated as a template_parm_data*), then DATA->PARMS is marked
4142    appropriately.  */
4143
4144 static int
4145 mark_template_parm (tree t, void* data)
4146 {
4147   int level;
4148   int idx;
4149   struct template_parm_data* tpd = (struct template_parm_data*) data;
4150
4151   if (TREE_CODE (t) == TEMPLATE_PARM_INDEX)
4152     {
4153       level = TEMPLATE_PARM_LEVEL (t);
4154       idx = TEMPLATE_PARM_IDX (t);
4155     }
4156   else
4157     {
4158       level = TEMPLATE_TYPE_LEVEL (t);
4159       idx = TEMPLATE_TYPE_IDX (t);
4160     }
4161
4162   if (level == tpd->level)
4163     {
4164       tpd->parms[idx] = 1;
4165       tpd->arg_uses_template_parms[tpd->current_arg] = 1;
4166     }
4167
4168   /* Return zero so that for_each_template_parm will continue the
4169      traversal of the tree; we want to mark *every* template parm.  */
4170   return 0;
4171 }
4172
4173 /* Process the partial specialization DECL.  */
4174
4175 static tree
4176 process_partial_specialization (tree decl)
4177 {
4178   tree type = TREE_TYPE (decl);
4179   tree maintmpl = CLASSTYPE_TI_TEMPLATE (type);
4180   tree specargs = CLASSTYPE_TI_ARGS (type);
4181   tree inner_args = INNERMOST_TEMPLATE_ARGS (specargs);
4182   tree main_inner_parms = DECL_INNERMOST_TEMPLATE_PARMS (maintmpl);
4183   tree inner_parms;
4184   tree inst;
4185   int nargs = TREE_VEC_LENGTH (inner_args);
4186   int ntparms;
4187   int  i;
4188   bool did_error_intro = false;
4189   struct template_parm_data tpd;
4190   struct template_parm_data tpd2;
4191
4192   gcc_assert (current_template_parms);
4193
4194   inner_parms = INNERMOST_TEMPLATE_PARMS (current_template_parms);
4195   ntparms = TREE_VEC_LENGTH (inner_parms);
4196
4197   /* We check that each of the template parameters given in the
4198      partial specialization is used in the argument list to the
4199      specialization.  For example:
4200
4201        template <class T> struct S;
4202        template <class T> struct S<T*>;
4203
4204      The second declaration is OK because `T*' uses the template
4205      parameter T, whereas
4206
4207        template <class T> struct S<int>;
4208
4209      is no good.  Even trickier is: