OSDN Git Service

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