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