OSDN Git Service

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